HashMap的扩容机制

HashMap主要成员变量：

1. capacity:entry数组的长度，也是hashmap的容量，默认值为16（1<<4）

2. loadFactory:负载因子，默认值为0.75f

3. threshold:阈值，它的值等于capacity*loadFactory，当hashmap中entry的数量大于threshold时，会执行resize()方法对hashmap扩容

4. table:entry数组

5. size:hashmap中entry的总个数

   什么时候扩容：当向容器添加元素的时候，会判断当前容器的元素个数，如果大于等于阈值(知道这个阈字怎么念吗？不念fa值，念yu值四声)---即当前数组的长度乘以加载因子的值的时候，就要自动扩容啦。

   扩容(resize)就是重新计算容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组，就像我们用一个小桶装水，如果想装更多的水，就得换大水桶。

源码分析

     final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;//原来的容量
        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 &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; //将hashmap容量和阈值同时扩大1倍
        }
        else if (oldThr > 0) // 当初始化capacity作为threshold
            newCap = oldThr;
        else {               // 表示使用默认构造函数初始化hashmap
            newCap = DEFAULT_INITIAL_CAPACITY;//初始化容量为默认值16
//初始化阈值为DEFAULT_INITIAL_CAPACITY*DEFAULT_INITIAL_CAPACITY（16*0.75）
            newThr = (int)(DEFAULT_LOAD_FACTOR *DEFAULT_INITIAL_CAPACITY);
        }
// 当初始化capacity作为threshold时要重新初始化阈值threshold
        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];
        table = newTab;//entry数组完成扩容
        if (oldTab != null) {//将原来的entry数组中的值赋值到新的数组中
            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 { // preserve order
                        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;//完成扩容，返回新的entry数组
    }