HashMap是怎么扩容的？

HashMap中的扩容主要分为两个步骤。

第一，对数组大小进行扩容。那么HashMap在什么情况下会触发扩容呢？HashMap中定义了一个扩容的阈值，该阈值的计算公式为 : threshold = capacity * loadFactor,其中capacity为数组的长度，默认是16。loadFactor为负载因子，默认为0.75。threshold为该阈值，默认是16 * 0.75 = 12。达到的效果就是HashMap中元素数量超过了阈值，会进行扩容操作，扩容后的数组大小为原来的2倍。这个步骤上，1.7和1.8没有区别

//扩容数组长度核心代码
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) {
            //当目前数组大小 >= 最大临界值，阈值设置为Integer.MAX_VALUE
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 否则的话，新数组大小为原来数组的2倍，新阈值也为老阈值的2倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) 
            newCap = oldThr;
        else {               
            //HashMap采用延迟加载的方式，只有当put操作的时候才开始初始化数组。默认大小为16，默认阈值为 12.
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        ...
}

第二，重新存放数据位置。因为数组大小有变化，所以数据的下标需要重新计算，将数组放到新计算的下标位置。

在JDK1.7中，链表数据的添加采用的是头插法，这是一种类似于栈的先进后出特点的添加方式，所以在扩容时，有点类似于数据从一个栈转移到另一个栈，转移后的顺序会反转过来（这里用栈来举例是为了方便理解，链表和栈是不同的数据结构）。这里在多个线程同时扩容时，会出现环形链表问题。

void transfer(Entry[] newTable, boolean rehash) {
　　int newCapacity = newTable.length;
　　for (Entry<K,V> e : table) {
　　　　while(null != e) {
　　　　　　Entry<K,V> next = e.next;
　　　　　　if (rehash) {
　　　　　　　　e.hash = null == e.key ? 0 : hash(e.key);
　　　　　　}
　　　　　　//因为数组大小有变化，所以需要重新计算存放下标位置
　　　　　　int i = indexFor(e.hash, newCapacity);
          //这里就是顺序反转的核心算法啦，是不是有点像某个面试题，给数组中的两个元素调换位置？
　　　　　　e.next = newTable[i];
　　　　　　newTable[i] = e;
　　　　　　e = next;
　　　　}
　　}
}

在JDK1.8中，链表数据添加采用的是尾插法。所以并不存在顺序反转，相应的也不会出现环形链表问题。

final Node<K,V>[] resize() {
        ...
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        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)
                        //没有hash冲突，即链表只有一个元素，直接计算下标位置存放即可。
                        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;
                          /*   hash & 旧数组大小
                            * 这里以原数组大小为16举例，那么新数组的大小就是32
                            * 原数组下标计算用的是15（0000...1111）新数组下标计算用的是31（0000...11111）
                            * 不难发现，影响下标计算结果的其实就只有一个最高位的1
                            * 所以这里我们用hash先与16(0000...10000)进行与运算，目的就是提前区分开hash值在最高位的不同，根据在最高位是1还是0，将原链表拆分成两个不同的链表。
                            */
                            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) {
                            //在新数组下标中最高位的值如果为0，直接存放到原下标位置
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            //在新数组下标中最高位的值如果为1，存放下标位置为：原下标 + 旧数组大小
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }