Q:讲讲扩容机制吧?注意要说说 JDK8 时做的优化哦

> 作为 HashMap 面试必问题,这题我自然也把源码认真研究了好久!

当 HashMap 的数组已经无法再添加新元素时，就需要扩大数组.而Java的数组是无法动态扩容的，唯一方法就是使用一个新的数组来代替原先的小数组，就像用一个小桶装不下更多水时，要想装更多的水，就得换大水桶,可惜你只搬得了一个水桶,得把小桶里的水都倒进大桶里.

我们先看 JDK7 的源码

resize - JDK7

void resize(int newCapacity) {
     // 暂存扩容前的 Entry 数组引用
     Entry[] oldTable = table;    
     int oldCapacity = oldTable.length;
     // 若旧数组大小已达最大容量 - 2^30      
     if (oldCapacity == MAXIMUM_CAPACITY) {  
         // 修改阈值为int的最大值(2^31 - 1),这样就不可能再达得到阈值了,也就不会再触发扩容
         threshold = Integer.MAX_VALUE;
         return;
     }
     // 创建一个新 Entry 数组
     Entry[] newTable = new Entry[newCapacity];  
     // 将数据转移到新 Entry 数组
     transfer(newTable); 
     // HashMap的table 属性引用绑定到新的 Entry 数组                        
     table = newTable;
     // 更新阈值                           
     threshold = (int)(newCapacity * loadFactor);
}

看其中的 transfer()方法:

transfer - JDK7

void transfer(Entry[] newTable) {
    // 暂存旧数组引用
    Entry[] src = table; 
    // 获取新数组长度                  
    int newCapacity = newTable.length;
    // 遍历旧数组
    for (int j = 0; j < src.length; j++) { 
        // 获取旧数组的第一个元素
        Entry<K,V> e = src[j];            
        if (e != null) {
            // 将旧数组的对象引用都置null,循环完后,旧数组将不再引用任何对象,加速 gc.
            src[j] = null;
            // 遍历链中元素
            do {
                Entry<K,V> next = e.next;
                // 重新计算每个元素在新数组中的位置
                int i = indexFor(e.hash, newCapacity); 
                // JDK7 中头插法的核心代码
                e.next = newTable[i];
                // 将新数组的各个对象引用指向元素
                newTable[i] = e;    
                // 获取下一个链元素  
                e = next;             
             } while (e != null);
         }
     }
 }

newTable[i] 的引用赋给了e.next，即单链表的头插方式，即转移到数组同一索引的新元素会被放在链表的头部(靠近数组那端).
这里和JDK8有区别.在旧数组中的同一条 Entry 链上的元素，通过重新计算索引位置后，有可能就被放到了新数组的不同位置.

图解JDK7扩容示例

如下图显示,假定 hash 算法为:

key % table.length

table 数组的 size=2
当 key = 3、7、5时，put 顺序依次为5、7、3
mod 2后都冲突在了 table[1].
假设 loadFactor=1，即当键值对的实际大小 size > table的实际大小时进行扩容.
接下来的三个步骤是数组 resize 扩容为4，然后所有节点 rehash.

不过注意,在 JDK7 中的 HashMap 在 resize 时容易死循环

HashMap 的死循环分析

假设 table 数组容量为 2,已有一个元素的 key=5.
此时

• 线程 T1添加元素 key=3,value=a
• 线程 T2 添加元素 key=7,value=b

至此,两个元素都添加到 HashMap.

do {
    Entry<K,V> next = e.next; // 假设线程 T1 执行到这,被突然调度挂起
    int i = indexFor(e.hash, newCapacity);
    e.next = newTable[i];
    newTable[i] = e;
    e = next;
} while (e != null);

而线程 T2 执行完成了.
此时 T1 的 e 指向的是 key=3,value=a,而 next 指向 key=7,value=b
之后,T2 在 rehash 后链表的顺序又被反转变成 5=>7=>3

T1 被调度回来继续执行。

• 先执行 newTalbe[i] = e,key=3,value=a 的 next 设为了 key=7,value=b
• 然后是 e = next，导致 e 指向 key=7,value=b
• 而下一次循环的 next = e.next 导致了 next 指向 key=3,value=a

就形成了 key=3,value=a 和 key=7,value=b的死循环引用.
> 历史上有人向 Sun 提交过这个 bug:
https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6423457

JDK8 的优化

resize - JDK8

    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;
            }
            // 扩大为原来容量的2倍,但不能超过最大容量
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // 双倍阈值的快乐
        }
        // 旧数组没有数据
        else if (oldThr > 0) // 初始容量被阈值替代