高并发下的HashMap为什么会死循环 java后端

前言 ??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 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 e : table) { //遍历所有桶 while(null != e) {//遍历桶中所有元素（是一个链表） Entry 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 next = e.next; e.next = newTable[i]; newTable[i] = e; e = next;

把元素插入新的HashMap中，粗略的看下这四行代码似乎并没有什么问题,元素进行转移的图如下(线程不冲突的情况下)

文章图片

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

文章图片

Entry next = e.next;

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

文章图片

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

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

文章图片

??在链表就就产生了循环后，当get()方法获取元素的时候正好落在这个循环的链表上时，线程会一直在环了遍历，无法跳出，从而导致cpu飙升100%！
总结在多线程情况下尽量不要用HashMap，可以用线程安全的hash表来代替如ConcurrentHashMap、HashTable、Collections.synchronizedMap()。来避免产生多线程安全问题。
/ 感谢支持 / 以上便是本次分享的全部内容，希望对你有所帮助^_^
喜欢的话别忘了分享、点赞、收藏三连哦~
【高并发下的HashMap为什么会死循环】欢迎关注公众号程序员巴士，一辆有趣、有范儿、有温度的程序员巴士，涉猎大厂面经、程序员生活、实战教程、技术前沿等内容，关注我，交个朋友吧！