HashMap死循环的成因(JDK1.8之前)

hashMap在resize期间由于并发存在死循环的可能,怀着对其形成原因的好奇,笔者翻阅了很多博文,虽然最终大致懂了原因,但是理解的过程很痛苦,一定有一种更容易理解的方式.这也是写作本文的动力

map的内部存储结构

map内部存储着一个数组

数组中存储着Node,其结构如下

  static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
}

这就是人们常说的, Map内部实现是数组,数组中的每个元素又是一个链表

死循环的成因

就直接盗图了,根本原因就是扩容重建时链表中形成了环,导致后续get时在环里打转造成死循环

重建核心代码如下:

/**
     * Transfers all entries from current table to newTable.
     */
    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;        // 1
                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;
            } 
 
        }
    }

为什么会形成环?
table这个Entry数组是线程共享的,而next,e是线程私有的.现在假设线程2在运行完1后挂起了,然后线程1也去做重建并且完成了,那么Entry的状态变化如下图

总结

什么是线程不安全?
线程的操作数据时会先从主存复制一份到线它的局部存储中,后续的操作都是对本地存储进行操作,只在必要时才会刷新会主存,这样多个线程并发操作时就会出现数据不一致问题

由于程序运行的随机性,线程不安全的程序出现问题的可能性很多,去探究其原因并不是很有意义,关键是要理解其根本原因.