2021-10-20 15:16 已编辑水滴_基础架构_Java开发工程师

关注

Java集合详解以及底层源码分析和部分面试题

集合

对象的容器，实现了对对象常用的操作

和数组的区别

数组长度固定，集合长度不固定
数组可以存储基本类型和引用类型，集合只能存储引用类型

位置

java.util.*;

Collection体系

Collection 父接口

特点：代表一组任意类型的对象，无序、无下标、不能重复。

创建集合 Collection collection = new ArrayList();

常用方法

添加元素 collection.add();
删除元素

collection.remove();

collection.clear();

遍历元素（重点）

使用增强for（因为无下标）

for(Object object : collection){ }

使用迭代器

//haNext(); 有没有下一个元素
//next(); 获取下一个元素
//remove(); 删除当前元素
Iterator it = collection.iterator();
while(it.hasNext()){
  String object = (String)it.next(); //强转
  // 可以使用it.remove(); 进行移除元素
  // collection.remove(); 不能用collection其他方***报并发修改异常
}

判断 collection.contains(); collection.isEmpty();

List 子接口

特点：有序、有下标、元素可重复

创建集合对象 List list = new ArrayList<>( );

常用方法

添加元素 list.add( ); 会对基本类型进行自动装箱
删除元素可以用索引 list.remove(0)

当删除数字与索引矛盾时对数字强转

list.remove((Object) 10) 或 list.remove(new Integer(10))

遍历

使用for遍历

for(int i = 0; i < lise.size(); i++){
  sout(list.get(i)); 
}

使用增强for
```
for(Object list: collection){ }
```

使用迭代器

Iterator it = collection.iterator();
while(it.hasNext()){
  String object = (String)it.next(); //强转
  // 可以使用it.remove(); 进行移除元素
  // collection.remove(); 不能用collection其他方***报并发修改异常
}

使用列表迭代器（注意和迭代器区别）

ListIterator li = list.listIterator();
while(li.hasNext()){
  System.out.println(li.nextIndex() + ":" + li.next()); //从前往后遍历
}

while(li.hasPrevious()){
  System.out.println(li.previousIndex() + ":" + li.previous()); //从后往前遍历
}

获取 list.indexOf( );

返回子集合 sublist(x, y); 左闭右开



List subList = list.subList(1, 3);// 返回索引 1、2

List实现类

ArrayList 【重点】
- 数组结构实现，必须要连续空间，查询快、增删慢
- jdk1.2版本，运行效率块、线程不安全
Vector
- 数组结构实现，查询快、增删慢
- jdk1.0版本，运行效率慢，线程安全。
LinkedList
- 双向链表结构实现，无需连续空间，增删快，查询慢

ArrayList

创建集合 ArrayList arrayList = new ArrayList<>();

添加元素 arrayList.add();
删除元素 arrayList.remove(new Student("name", 10));

这里重写了 equals(this == obj) 方法


public boolean equals(Object obj){
  //1 判断是不是同一个对象
  if(this == obj){
    return true;
  }
  //2 判断是否为空
  if(obj == null){
    return false;
  }
  //3 判断是否是Student类型(判断Obj是不是Student的一个实例)
  if(obj instanceof Student){
    Student s== (Student)obj;
    //4 比较属性
    if(this.name.equals(s.getName()) && this.age == s.getAge()){
      return true;
    }
  }
  //5 不满足条件返回false
  return false;
}

遍历元素【重点】

使用迭代器


Iterator it = arrayList.iterator();
while(it.hasNext()){
  Student s = (Student)it.next(); //强转
}

列表迭代器

ListIterator li = arrayList.listIterator();
while(li.hasNext()){
  Student s = (Student)li.next(); //从前往后遍历
}

while(li.hasPrevious()){
  Student s = (Student)li.previous();//从后往前遍历
}

判断

arrayList.contains(); 和 arrayList.isEmpty();
查找

arrayList.indexof();

Arraylist源码分析

在JDK1.8中，如果通过无参构造的话，初始数组容量为0，
当真正对数组进行添加时候（即添加第一个元素时），
才真正分配容量，默认分配容量为10；
当容量不足时（容量为size，添加第一个size+1个元素时），
先判断按照1.5倍（位运算）的比例扩容能否满足最低容量要求，
若能，则以1.5倍扩容，否则以最低容量要求进行扩容。

DEFAULT_CAPACITY = 10; //默认容量
//注意：如果没有向集合中添加任何元素时，容量0，添加一个后，容量为10
//每次扩容是原来的1.5倍
elementData存放元素的数组
size 实际元素个数

空的Arraylist执行ArrayList.add()方法时的源码解析：
按照以下顺序来解读：42351


//    1）
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!! （增长容量），刚开始，空的arrylist容量为0，即size=0
    elementData[size++] = e;//把元素放在索引为0的位置
    return true;
}
//    2）
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//    3）
private void ensureExplicitCapacity(int minCapacity) {//由第四段代码可知此时的minCapcity为10
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)// 10-0>0?      成立  执行grow()方法，只有增长容量大于最大容量的时候才会扩容
        grow(minCapacity);
}
//    4）
private static int calculateCapacity(Object[] elementData, int minCapacity) {//DEFAULTCAPACITY_EMPTY_ELEMENTDATA=NULL
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//刚开始都是空，所以相等
        return Math.max(DEFAULT_CAPACITY, minCapacity);//刚开始（10，1）比较，肯定是10大，就变成10了
    }
    return minCapacity;
}
//    5）        数组扩容的代码
private void grow(int minCapacity) { //刚开始是10
    // overflow-conscious code
    int oldCapacity = elementData.length;//  0
    int newCapacity = oldCapacity + (oldCapacity >> 1);// ？=0+0>>1（>>右移，是位运算），0=0+0；   右移一位相当于除以2
    if (newCapacity - minCapacity < 0)// 0-10=-10，-10<0,所以newCapacity=10,即：容量变成10
        newCapacity = minCapacity;//newCapacity = 10
    if (newCapacity - MAX_ARRAY_SIZE > 0)//10-MAX_ARRAY_SIZE<0,不执行，因为MAX_ARRAY_SIZE非常大
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);//扩容   
}

//原容量为10的Arraylist添加第11个元素，执行ArrayList.add()方法时的源码解析：
//可以得出结论：Arraylist的扩容机制：
//注意：如果没有向集合中添加任何元素时，容量0，添加一个后，容量为10
//每次扩容是原来的1.5倍
//按照以下顺序来解读：12435

//    1）
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!! （增长容量），arrylist容量为100，即size=11
    elementData[size++] = e;//把元素放在索引为11的位置
    return true;
}


//    2）
private void ensureCapacityInternal(int minCapacity) { //  minCapacity=11
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}


//    3）
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)// 11-10>0  成立  执行grow()方法，只有增长容量大于最大容量的时候才会扩容
        grow(minCapacity);

}


// 4）
private static int calculateCapacity(Object[] elementData, int minCapacity) {//DEFAULTCAPACITY_EMPTY_ELEMENTDATA=NULL
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//有数据，且不为空，不成立，不执行
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;//  minCapacity=11
}


//    5）        数组扩容的代码
private void grow(int minCapacity) { //minCapacity=11
    // overflow-conscious code
    int oldCapacity = elementData.length;//  10
    int newCapacity = oldCapacity + (oldCapacity >> 1);// ？=10+10>>1（>>右移，是位运算），15=10+5；   右移一位相当于除以2
    if (newCapacity - minCapacity < 0)//15-11=-10>0,不执行
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)//10-MAX_ARRAY_SIZE<0,不执行，因为MAX_ARRAY_SIZE非常大，好几亿
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);//扩容   
}

Vector

创建集合 Vector vector = new Vector<>();

增加、删除、判断同上

遍历中枚举器遍历

Enumeration en = vector.elements(); //把vector集合赋给枚举器
while(en.hasMoreElements()){
  String o = (String)en.nextElement();
  sout(o);
}

LinkedList

创建链表集合LinkedList li = new LinkedList<>();

常用方法与List一致

双向链表

LinkedList源码解析

LinkedList的三个属性

transient int size = 0;//集合大小
transient Node<E> first;//指向第一个元素
transient Node<E> last;//指向最后一个元素

LinkedList.add()方法

// 1）
public boolean add(E e) {
    linkLast(e);//链接到最后一个位置，起关键作用的代码
    return true;
}
// 2）
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);Node(l,e,null),l指的是prev，e是元素,null是next
    last = newNode;
    if (l == null)
        first = newNode;//添加第一个元素的时候，刚开始一个节点都没有，
                        //此时，newnode的last和next都是null，因为l==null，所以把newnode指向第一个元素，first和last都指向它
    else                //添加第二个元素时，l指向第一个元素，非空，执行else，第二个元素连在第一个元素后边，
                            //此时newnode的prev是第一个元素，last指向第二个元素
        l.next = newNode;
    size++;
    modCount++;
}
// 3）
private static class Node<E> {
    E item;//当前元素，实际数据
    Node<E> next;//下一个节点
    Node<E> prev;//上一个节点

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Arraylist和Linkedlist的区别

泛型

本质是参数化类型，把类型作为参数传递
常见形式有泛型类、泛型接口、泛型方法
语法 T成为类型占位符，表示一种引用类型，可以写多个逗号隔开
好处 1. 提高代码重用性 2. 防止类型转换异常，提高代码安全性

泛型类

// 写一个泛型类
public class MyGeneric<T>{
  //使用泛型T
  //1 创建变量
  T t;
  //2 泛型作为方法的参数
  public void show(T t){
    sout(t);
  }
  //3 泛型作为方法的返回值
  public T getT(){
    return t;
  }
}

// 使用泛型类
public class TestGeneric{
  public static void main(String[] args){
    //使用泛型类创建对象
    // 注意： 1. 泛型只能使用引用类型
    //			 2. 不用泛型类型对象之间不能相互赋值
    MyGeneric<String> myGeneric = new MyGeneric<String>();
    myGeneric.t = "hello";
    myGeneric.show("hello world!");
    String string = myGeneric.getT();
    
    MyGeneric<Integer> myGeneric2 = new MyGeneric<Integer>();
    myGeneric2.t = 100;
    myGeneric2.show(200);
    Integer integer = myGeneric2.getT();
    
  }
}

泛型接口

语法：接口名

注意：不能泛型静态常量

泛型方法

语法：返回值类型

public class MyGenericMethod{
  //泛型方法
  public <T> T show(T t){
    sout("泛型方法" + t);
    return t;
  }
}

//调用
MyGenericMethod myGenericMethod = new MyGenericMethod();
myGenericMethod.show("字符串");// 自动类型为字符串
myGenericMethod.show(200);// integer类型
myGenericMethod.show(3.14);// double类型

泛型集合

概念：参数化类型、类型安全的集合，强制集合元素的类型必须一致

特点：

编译时即可检查，而非运行时抛出异常
访问时，不必类型转换（拆箱）
不同泛型之间应用不能相互赋值，泛型不存在多态

Set集合

特点：无序、无下标、元素不可重复

方法：全部继承自Collection中的方法

增、删、遍历、判断与collection一致

HashSet 【重点】

存储结构：哈希表（数组+链表(单向)+红黑树）

存储过程（重复依据）

根据hashCode计算保存的位置，如果位置为空，直接保存，若不为空，进行第二步
再执行equals方法，如果equals为true，则认为是重复，否则形成链表

特点

基于HashCode计算元素存放位置
- 利用31这个质数，减少散列冲突
  - 31提高执行效率 31 * i = (i << 5) - i 转为移位操作
- 当存入元素的哈希码相同时，会调用equals进行确认，如果结果为true，则拒绝后者存入

新建集合 HashSet<String> hashSet = new HashSet<String>();

添加元素 hashSet.add( );

删除元素 hashSet.remove( );

遍历操作

1. 增强for for( type type : hashSet)

2. 迭代器 Iterator<String> it = hashSet.iterator( );

判断 hashSet.contains( ); hashSet.isEmpty();

/*
存储过程：1.根据hashcode计算保存的位置，如果此位置为空，则直接保存，如果不为空
         2.再执行equals方法，如果equals方法为true，则认为是重复，否则，形成链表
*/
public class demo3 {
    public static void main(String[] args) {
        HashSet<Person> persons=new HashSet<>();

        Person p1=new Person("刘德华",20);
        Person p2=new Person("周文豪",21);
        Person p3=new Person("闫守建",22);
        Person p4=new Person("侯明明",23);

        persons.add(p1);
        persons.add(p2);
        persons.add(p3);
        persons.add(p4);

        persons.add(new Person("刘德华",20));//new 的这个没有变量名，不是同一个对象，所以能添加进去
                                            //如果想实现只要有一个属性值相同就禁止添加，需要重写Person类的hashCode方法和equals方法
        System.out.println("元素个数："+persons.size());
        System.out.println(persons.toString());
        
        System.out.println(persons.contains(new Person("刘德华",20)));//new 的这个没有变量名，不是同一个对象，所以判断为不包含，也就是false
                                             //如果想实现以上方法判断包含，需要重写Person类的hashCode方法和equals方法
     }
}
    //重写Person类的 hashcode()方法
    @Override
    public int hashCode() {
        int n1=this.name.hashCode();
        int n2=this.age;

        return n1+n2;
    }
    //重写Person类的 equals()方法
    @Override
    public boolean equals(Object obj) {
        if(this==obj){          //如果相等 执行下一步
            return true;
        }
        if (this==null){ 
            return false;      //如果为空，返回false
        }
        if(obj instanceof Person){   //判断其左边对象是否为其右边类的实例，如果是，执行
            Person p=(Person) obj;   
            if(this.name.equals(p.getName())&&this.age==p.getAge()){
                return true;
            }
        }
        return false;
    }

//重写之后就不能使用以上方法重复添加了
//如何快速重写这两个方法
//操作如下：在代码区域按 alt + enter 或 右键 Generate选项

快速重写后的代码解析

public static int hashCode(Object a[]) {
    if (a == null)
        return 0;

    int result = 1;

    for (Object element : a)
        result = 31 * result + (element == null ? 0 : element.hashCode());//该对象的各个属性均加31
                                                /*基于HashCode计算元素存放位置
                                                  - 利用31这个质数，减少散列冲突
                                                  -   31提高执行效率 `31 * i = (i << 5) - i` 转为移位操作
                                                 - 当存入元素的哈希码相同时，会调用equals进行确认，如果结果为true，则拒绝后者存入
                                                */
    return result;
}

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (!(o instanceof Person)) return false;
    Person person = (Person) o;
    return age == person.age &&
            Objects.equals(name, person.name);
}

TreeSet

特点

基于排列顺序实现元素不重复
实现SortedSet接口，对集合元素自动排序
元素对象的类型必须实现Comparable接口，指定排序规则
通过CompareTo方法确定是否为重复元素

存储结构：红黑树

红黑树是一种二叉查找树，要求根节点必须为黑色，
所有的null节点都是黑的，为什么使用红黑来标记，为了保持树的平衡，避免一边重一边轻

创建集合 TreeSet<String> treeSet = new TreeSet<>()

添加元素 treeSet.add();

删除元素 treeSet.remove();

遍历 1. 增强for 2. 迭代器

判断 treeSet.contains();

补充：TreeSet集合的使用

如果对象元素不实现Comparable接口，并重写compareTo方法，添加元素的时候会报错
Exception in thread "main" java.lang.ClassCastException: test.Person cannot be cast to java.lang.Comparable
没有比较法则，不知道该怎么存储，因为红黑树是一个二叉查找树，小的放左边，大的放右边

public class Person implements Comparable<Person>

// 重写compareTo
@Override//先按姓名比，再按年龄比
public int compareTo(Person o){
   int n1=this.getName().compareTo(o.getName());
   int n2=this.age-o.getAge();
   return n1==0?n2:n1;//如果n1==0也就是名字相同，再比较年龄
}
 Person p5=new Person("周文豪",18);
 treeSet.add(p5);
 //treeSet.remove(p5);
treeSet.remove(new Person("周文豪",18));//因为重写了Person类的compareTo()方法，所以比较后是相同的，可以删掉

Comparator 实现定制比较（比较器）

//元素不一定非要实现Comparable接口，也可以在main方法的实现TreeSet时，使用Comparator比较器
public class Demo6 {
    public static void main(String[] args) {
        //创建集合并指定比较规则
        TreeSet<Person> treeSet=new TreeSet<>(new Comparator<Person>() {
            @Override
            public int compare(Person o1, Person o2) {
                int n1 = o1.getAge()-o2.getAge();
                int n2 = o1.getName().compareTo(o2.getName());
                return n1 == 0 ? n2 : n1;//如果n1==0也就是年龄相同，再比较姓名
            }
        });
        //创建对象
        //添加元素
        //打印
    }
}

Comparable 可比较的

Map集合

Map接口的特点

1. 用于存储任意键值对（key - value）
2. 键：无序、无下标、不允许重复（唯一）
3. 值：无序、无下标、允许重复

方法：

1. V put(K key, V value) 将对象存到集合中，关联键值。 key重复则覆盖原值
2. Object get(Object key) 根据键获得对应的值
3. keySet() 返回所有的Key
4. Collection<V> values() 返回包含所有值的Collection集合
5. Set<Map.Entry<K, V>> 键值匹配的Set集合

Map接口的使用

//创建Map集合
Map<String, String> map = new HashMap<>();
// 1. 添加元素
map.put("cn", "中国");
map.put("uk", "英国");
map.put("cn", "zhongguo"); // 会替换第一个 
// 2. 删除
map.remove("uk");
// 3. 遍历
// 3.1 使用KeySet()
//Set<String> keyset = map.keySet(); // 所有Key的set集合
for(String key : map.keyset){
  sout(key + "---" + map.get(key));
}
// 3.2 使用entrySet() //映射对（键值对），把Map集合里边的key和value封装成了一个个Entry对象
//Set<Map.Entry<String, String>> entries = map.entrySet(); // Map.entry<String,String>是一个内部接口
for(Map.Entry<String, String> entry : map.entrySet()){
  sout(entry.getKey() + "---" + entry.getValue();
}
//注意：使用entrySet()遍历，效率要高于KeySet();

HashMap 【重点】

存储结构：哈希表（数组+链表(单向)+红黑树）

HashMap存取实现

2.1：存储

这里HashMap用了一个算法。

//存储时候：

int hash=key.hashCode(); //获取key的hashCode，这个值是一个固定的int值

int index=hash%Entry[].length。//获取数组下标：key的hash值对Entry数组长度进行取余

Entry[index]=value。

 

注意：假设两个key通过hash%Entry[].length得到的index同样。会不会覆盖？

是不会的。Entry类有一个next属性，作用是指向下一个Entry。打个例如， 第一个键值对A进来。通过计算其key的hash得到的

index=0。记做:Entry[0] = A。一会后又进来一个键值对B，通过计算其index也等于0，如今怎么办？HashMap会这样做:B.next =

 A,Entry[0] = B,假设又进来C,index也等于0,那么C.next = B,Entry[0] = C；这样我们发现index=0的地方事实上存取了A,B,C三个键值对,他

们通过next这个属性链接在一起。

所以疑问不用操心。

也就是说Entry[]数组中存储的是最后插入的数据

	 public V put(K key, V value) {
	        if (key == null)
	            return putForNullKey(value); //null总是放在数组的第一个链表中
	        int hash = hash(key.hashCode());
	        int i = indexFor(hash, table.length);
	        //遍历链表
	        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
	            Object k;
	            //假设key在链表中已存在，则替换为新value
	            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
	                V oldValue = e.value;
	                e.value = value;
	                e.recordAccess(this);
	                return oldValue;
	            }
	        }
	        modCount++;
	        addEntry(hash, key, value, i);
	        return null;
	    }
	 
	void addEntry(int hash, K key, V value, int bucketIndex) {
	    Entry<K,V> e = table[bucketIndex];
	    table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //參数e, 是Entry.next
	    //假设size超过threshold，则扩充table大小。再散列
	    if (size++ >= threshold)
	            resize(2 * table.length);
	}

2.2:取值

 获取key的hashcode指，通过hash值去hash%Entry[].length  获取Entry[hash%Entry[].length]，定位到该数组元素之后，再遍历该元

素处的链表。

//取值时候：

int hash=key.hashCode();

int index =hash%Entry[].length;

return Entry[index];

     public V get(Object key) {
	        if (key == null)
	            return getForNullKey();
	        int hash = hash(key.hashCode());
	        //先定位到数组元素。再遍历该元素处的链表
	        for (Entry<K,V> e = table[indexFor(hash, table.length)];
	             e != null;
	             e = e.next) {
	            Object k;
	            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
	                return e.value;
	        }
	        return null;
	}
/*
当哈希表的容量超过默认容量时，必需要调整table的大小。

当容量达到最大值时，该方法Integer.MAX_VALUE返回。这时。就需要创建

一张表，将原来的表映射到新表中。
*/

3、HashMap、HashTable和ConcurrentHashMap的线程安全问题

HashMap：线程不安全的。
HashTable：锁住整张hash表，让线程独占。hashMap同意为空。

通过分析Hashtable就知道，synchronized是针对整张Hash表的，即每次锁住整张表

让线程独占。安全的背后是巨大的浪费。

ConcurrentHashMap:一个更快的hashmap，它提供了好得多的并发性。多个读操作差点儿总能够并发地运行。

他是锁段（默认：把hash表分为16个

段），在get，put，remove等操作中，ConcurrentHashMap仅仅锁定当前须要用到的段，仅仅有在求size的时候才锁定整张hash表。

使用key可使hashcode和equals作为重复

增、删、遍历、判断与上述一致

students.put(new Student("沙和尚",102),"杭州");//如果不重写hashcode和equals方法重复的对象还是可以添加进去，因为这是一个没有名字的新对象

原码分析总结：

1. HashMap刚创建时，table是null，节省空间，当添加第一个元素时，table容量调整为16

2. 当元素个数大于阈值（16*0.75 = 12）时，会进行扩容，扩容后的大小为原来的两倍，目的是减少调整元素的个数

3. jdk1.8 当每个链表长度 >8 ，并且数组元素个数 ≥64时，会调整成红黑树，目的是提高效率

4. jdk1.8 当链表长度 <6 时调整成链表 5. jdk1.8 以前，链表时头插入，之后为尾插入

源码：

//进入HashMap类

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 默认初始容量大小，1左移4位，也就是2^4=16

static final int MAXIMUM_CAPACITY = 1 << 30;//最大的容量大小 2^30

static final float DEFAULT_LOAD_FACTOR = 0.75f;//默认的加载因子 也就是如果元素个数大于阀值(容量的75%),开始扩容

static final int TREEIFY_THRESHOLD = 8; //当每个链表长度 >8 ，并且数组元素个数 ≥64时，会调整成红黑树，目的是提高效率

static final int UNTREEIFY_THRESHOLD = 6;//当链表长度 <6 时 调整成链表

static final int MIN_TREEIFY_CAPACITY = 64;//当每个链表长度 >8 ，并且数组元素个数 ≥64时，会调整成红黑树，目的是提高效率

transient Node<K,V>[] table;//哈希表中的数组

transient int size //元素个数
    
    
//HashMap刚创建时
 public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // 只赋值了一个加载因子，其他的都没操作，没有创建数组，table是null，size是0；
}

//进入map.put()方法
 public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
 }
//进入hash()方法，作用：用来计算位置的，产生哈希值得一个东西
 static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }
//进入putVal()方法
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;//创建数组，创建node..变量;
        if ((tab = table) == null || (n = tab.length) == 0)//在没放数据之前table=null，成立执行方法
            n = (tab = resize()).length;   //resize()重新调整大小，n=16
        if ((p = tab[i = (n - 1) & hash]) == null)//找位置，看位置有没有元素，如果没有，放在该位置
            tab[i] = newNode(hash, key, value, null);//创建一个新的node对象，放在table某一个位置里边
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) 
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) {
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)//当元素个数大于阀值  16*0.75=12
            resize();//开始调整大小，每次都是原来容量的2倍，详情见resize()方法 注释处
        afterNodeInsertion(evict);
        return null;
    }
//进入resize()方法（只需看我注释的代码即可）
final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;//刚开始oldTab=null,所以oldCap=0；
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {//如果大于初始定义的最大容量
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && //大于阀值调整大小resize方法解析：
                     oldCap >= DEFAULT_INITIAL_CAPACITY) //newCap=oldCap左移一位，也就是乘2
                newThr = oldThr << 1; 
        }
    else if (oldThr > 0) 
            newCap = oldThr;
        else {               
            newCap = DEFAULT_INITIAL_CAPACITY;//因为最初oldCap=0，执行else，newCap的大小为16
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//创建一个新的数组，大小为16
        table = newTab;      //把新的数组给table
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { 
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

为什么扩容两倍？

int index =key.hashCode()&(length-1);

hahmap每次扩容都是以 2的整数次幂进行扩容

因为是将二进制进行按位于，(16-1) 是 1111,末位是1，这样也能保证计算后的index既可以是奇数也可以是偶数，

并且只要传进来的key足够分散，均匀那么按位于的时候获得的index就会减少重复，这样也就减少了hash的碰撞以及hashMap的查询效率。

为什么加载因子是0.75？0.5或者1不行吗？

0.75是趋于内存和访问效率上折中取的

根据HashMap的扩容机制，他会保证容量(capacity)的值永远都是2的幂 
为了保证负载因子x容量的结果是一个整数，这个值是0.75(4/3)比较合理，
因为这个数和任何2的次幂乘积结果都是整数。

理论上来讲，负载因子越大，导致哈希冲突的概率也就越大，
负载因子越小，费的空间也就越大,这是一个无法避免的利弊关系，
所以通过一个简单的数学推理，可以测算出这个数值在0.75左右是比较合理的

为啥HashMap中初始化大小为什么是16呢？

hahmap每次扩容都是以 2的整数次幂进行扩容

因为是将二进制进行按位于，(16-1) 是 1111,末位是1，
这样也能保证计算后的index既可以是奇数也可以是偶数，
并且只要传进来的key足够分散，均匀那么按位于的时候获得的index就会减少重复，
这样也就减少了hash的碰撞以及hashMap的查询效率。

因为是8或者4的话很容易导致map扩容影响性能，如果分配的太大的话又会浪费资源，所以就使用16作为初始大小。

HashMap和HashSet的关系：

//HashSet里边用的就是HashMap
//HashSet的add方法实际上就是用的hashmap的put方法，hashset就是用hashmap的key来保存元素
   public boolean add(E e) {
        return map.put(e, PRESENT)==null;
   }

Hashtable（现在不用了)

线程安全，运行效率慢；不允许null作为key或是value

Properties

hashtable的子类，要求key和value都是string，通常用于配置文件的读取

TreeMap

存储结构：红黑树

实现了SortedMap接口（是map的子接口），可以对key自动排序

增删遍历同HashMap，以及实现Comparable接口重写compareTo方法或使用Comparator比较器解决类型存储问题都一样

TreeSet和TreeMap的关系

在TreeSet里边用的就是TreeMap

当使用TreeSet添加数据的时候，用的就是TreeMap的put方法，用TreeMap的key来保存元素

//进入TreeSet类里
private transient NavigableMap<E,Object> m;
TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
}
//TreeSet里的构造方法
public TreeSet() {
    this(new TreeMap<E,Object>());//在TreeSet里边用的就是TreeMap
}
//当使用TreeSet添加数据的时候，用的就是TreeMap的put方法，用TreeMap的key来保存元素
public boolean add(E e) {
        return m.put(e, PRESENT)==null;
}

Collections工具类

概念：集合工具类，定义了除了存取以外的集合常用方法

直接二分查找int i = Collections.binarySearch(list, x); 成功返回索引

方法：sort 排序、binarySearch二分查找、

其他方法： copy复制、reverse反转、shuffle随机打乱

复制方法要求两个集合的大小必须相同，不然会报错，如果想复制，

解决方法：先用for循环让集合用0填充，再复制

List<Integer> list=new ArrayList<>();
        List<Integer> dest=new ArrayList<>();
        list.add(20);
        list.add(5);
        list.add(10);
        list.add(17);
        list.add(25);
        list.add(2);
//复制
for(int i=0;i<list.size();i++){
    dest.add(0);
}
Collections.copy(dest,list);

补充：

// list转成数组
Integer[] arr = list.toArray(new Integer[10]);//如果转成数组的过程中，定义的数组大小超过长度，多出来的会用null填充
sout(arr.length);
sout(Array.toString(arr));

// 数组转成集合
// 此时为受限集合，不能 添加和删除！
//原因：因为数组长度固定了，转成集合之后要求长度也是固定的
String[] names = {"张三","李四","王五"};
List<String> list2 = Arrays.asList(names);

// 把基本类型数组转为集合时，需要修改为包装类
Integer[] nums = {100, 200, 300, 400, 500};
List<Integer> list3 = Arrays.asList(nums);

总结

集合的概念：
          对象的容器，和数组类似，定义了对多个对象进行操作的常用方法。
List集合：
          有序、有下标、元素可以重复。(ArrayList、LinkedList、Vector)
Set集合 ：
          无序、无下标、元素不可重复。(HashSet、TreeSet)
Map集合 ：
          存储一对数据，无序，无下标，键不可重复，值可重复。重复键会把值覆盖。(HashMap、HashTable、TreeMap)
Collections:
          集合工具类，定义了除了存取外的集合的常用方法。