关于java:高并发下的HashMap为什么会死循环

前言

  HashMap 并发状况下的死循环问题在 jdk 1.7 及之前版本存在的，jdk 1.8 通过减少 loHead 和 loTail 进行了修复，尽管进行了修复，然而如果波及到并发状况下，个别倡议应用 CurrentHashMap 代替 HashMap 来确保不会呈现线程平安问题。

  在 jdk 1.7 及之前 HashMap 在并发状况下产生的循环问题，该循环问题将以致服务器的 cpu 飙升至 100%，为了解答这个纳闷，那么明天就来理解一下线程不平安的 HashMap 在高并发的状况下是如何造成死循环的，要探索 hashmap 死循环的起因那就要从 hashmap 的源码开始进行剖析，这样能力从根本上对 hashmap 进行了解。在剖析之前咱们要晓得在 jdk 1.7 版本及之前 HashMap 采纳的是数组 + 链表的数据结构，而在 jdk 1.8 则是采纳数组 + 链表 + 红黑树的数据结构以进一步升高 hash 抵触后带来的查问损耗。

注释

首先 hashmap 进行元素的插入这里会调用 put 办法

public V put(K key, V value) {if (table == EMPTY_TABLE) {inflateTable(threshold);// 调配数组空间
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);// 对 key 的 hashcode 进一步计算，确保散列平均
        int i = indexFor(hash, table.length);// 获取在 table 中的理论地位
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {...}
        modCount++;// 保障并发拜访时，若 HashMap 内部结构发生变化，疾速响应失败
        
        // 重点关注这个 addEntry 减少元素的办法
        addEntry(hash, key, value, i);
        return null;
    }

紧接着咱们来看这个 addEntry 办法，外面调用的 resize() 扩容办法是明天的配角

void addEntry(int hash, K key, V value, int bucketIndex) {if ((size >= threshold) && (null != table[bucketIndex])) {resize(2 * table.length);// 当 size 超过临界阈值 threshold，并且行将产生哈希抵触时进行扩容，扩容后新容量为旧容量的 2 倍
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);// 扩容后从新计算插入的地位下标
        }

        // 把元素放入 HashMap 的桶的对应地位
        createEntry(hash, key, value, bucketIndex);
    }

上面咱们进入到 resize() 法中，再揭开外面的 transfer() 办法的面纱，这个办法也是造成死循环的罪魁祸首

// 按新的容量扩容 Hash 表  
    void resize(int newCapacity) {Entry[] oldTable = table;// 旧数据  
        int oldCapacity = oldTable.length;// 获取旧的容量值  
        if (oldCapacity == MAXIMUM_CAPACITY) {// 旧的容量值曾经到了最大容量值  
            threshold = Integer.MAX_VALUE;// 批改扩容阀值  
            return;  
        }  
        // 新的构造  
        Entry[] newTable = new Entry[newCapacity];  
        
        // 将老的表中的数据拷贝到新的构造中
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;// 批改 HashMap 的底层数组  
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);// 批改阀值  
    }  

最初一起来仔细分析这个 transfer() 办法

// 将老的表中的数据拷贝到新的构造中  
    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) {// 如果是从新 Hash，则须要从新计算 hash 值  
                    e.hash = null == e.key ? 0 : hash(e.key);  
                }  
                int i = indexFor(e.hash, newCapacity);// 定位 Hash 桶  
                e.next = newTable[i];// 元素连贯到桶中, 这里相当于单链表的插入，总是插入在最后面
                newTable[i] = e;//newTable[i] 的值总是最新插入的值
                e = next;// 持续下一个元素  
            }  
        }  
    }

增加元素达到阀值后对 hashmap 进行扩容，走 reaize 办法，在对 HashMap 进行扩容时，又会调用一个 transfer() 对旧的 hashmap 中的元素进行转移, 那么咱们明天要探索的死循环问题 就是产生在这个办法里的，在进行元素转移时 transfer 办法里会调用上面四行代码

Entry<K,V> next = e.next; 
e.next = newTable[i];
newTable[i] = e;
e = next;

把元素插入新的 HashMap 中，粗略的看下这四行代码仿佛并没有什么问题, 元素进行转移的图如下 (线程不抵触的状况下)

那么咱们让线程 A、B 同时拜访我这段代码，当现 A 线程执行到以下代码时

Entry<k,v> next = e.next;

线程 A 交出工夫片，线程 B 这时候接手转移并且实现了元素的转移，这个时候线程 A 又拿到工夫片并接着执行代码

执行后代码如图，当 e = a 时，这时候这时候再执行

e.next = newTable[i];// a 元素指向了 b 元素，产生了循环

  在链表就就产生了循环后，当 get() 办法获取元素的时候正好落在这个循环的链表上时，线程会始终在环了遍历，无奈跳出，从而导致 cpu 飙升 100%！

总结

在多线程状况下尽量不要用 HashMap，能够用线程平安的 hash 表来代替如 ConcurrentHashMap、HashTable、Collections.synchronizedMap()。来防止产生多线程平安问题。

/ 感激反对 /

以上便是本次分享的全部内容，心愿对你有所帮忙 ^_^

喜爱的话别忘了 分享、点赞、珍藏 三连哦~

欢送关注公众号 程序员巴士，一辆乏味、有范儿、有温度的程序员巴士，涉猎大厂面经、程序员生存、实战教程、技术前沿等内容，关注我，交个敌人吧！