HashMap 成环问题

在 JDK 1.7 的实现中，使用头插法来实现元素的插入和数组扩容。

扩容的 Resize 包含扩容和 Rehash 两个步骤，Rehash 在并发的情况下可能会形成链表环。

Sun 认为这不是一个 Bug，因为 HashMap 本来就不支持并发，要并发就用 ConcurrentHashMap。

这个问题只存在于 JDK1.7 中，在 JDK1.8 中使用了不同的扩容实现方式，不会出现这种情况。

成环原因

map 初始化为一个长度为 2 的数组，loadFactor=0.75，threshold=2*0.75=1，也就是说当 put 第二个 key 的时候，map 就需要进行 resize。

public class HashMapInfiniteLoop {  
    private static HashMap<Integer,String> map = new HashMap<Integer,String>(2，0.75f);  
    public static void main(String[] args) {  
        map.put(5， "C");  

        new Thread("Thread1") {  
            public void run() {  
                map.put(7, "B");  
                System.out.println(map);  
            };  
        }.start();  
        new Thread("Thread2") {  
            public void run() {  
                map.put(3, "A);  
                System.out.println(map);  
            };  
        }.start();        
    }  
} 

线程一调度挂起

两个线程，用红色和浅蓝色标注。扩容时复制数据元素的 transfer 函数核心逻辑如下：

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

• 循环一轮，e 所指向的节点会被摘出到新的数组中作为头节点
• 线程一执行到 Entry<K,V> next = e.next; 时被调度挂起
• 线程二正常执行结束，完成扩容

线程一的 e 指向了 key(3)，而 next 指向了 key(7)，其在线程二 rehash 后，指向了线程二重组后的链表。可以看到链表的顺序被反转。

线程一调度运行

• 先是执行 newTalbe[i] = e，key(3) 被线程一的数组指向
• 然后是 e = next，导致 e 指向了 key(7)
• 下一次执行到 Entry<K,V> next = e.next;，next 指向了 key(3)

一轮循环后，把 e 指向的 key(7) 摘下来，放到 newTable[i] 的作为头节点，然后把 e 和 next 往后移。

成环

如上图 e 指向 key(3)。接下来，在线程一的最后一轮循环中，e 被摘出作为数据 newTable[i] 的头节点，然后 e 向后移到达 null 结束循环。

此时，由于 key(7) 指向 key(3)，而 key(3) 被摘出作为头节点也指向了 key(7)，环形链表就这样出现了。

总结

HashMap 链表成环的主要原因是：

• 使用头插法导致在新数组中的链表顺序被反转
• 多线程在调度挂起前持有了旧的链表顺序关系（e 和 next 关系）

Sun 认为这不是一个 Bug，因为 HashMap 本来就不支持并发，要并发就用 ConcurrentHashMap。

这个问题只存在于 JDK1.7 中，在 JDK1.8 中使用了不同的扩容实现方式，不会出现这种情况。

引用

1. Java 8 系列之重新认识 HashMap
2. JDK1.7 HashMap 导致循环链表