赤坎网站建设公司,网站后台传照片 c windows temp 拒绝访问,网站建设p,html界面设计作者 | tech-bus.七十一来源 | 程序员巴士前言HashMap并发情况下产生的死循环问题在JDK 1.7及之前版本是存在的#xff0c;JDK 1.8 通过增加loHead头节点和loTail尾节点进行了修复#xff0c;虽然进行了修复#xff0c;但是如果涉及到并发情况下需要使用hash表#xff0c;建… 作者 | tech-bus.七十一来源 | 程序员巴士前言 HashMap并发情况下产生的死循环问题在JDK 1.7及之前版本是存在的JDK 1.8 通过增加loHead头节点和loTail尾节点进行了修复虽然进行了修复但是如果涉及到并发情况下需要使用hash表建议使用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 (EntryK,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 (EntryK,V e : table) { //遍历所有桶while(null ! e) { //遍历桶中所有元素是一个链表EntryK,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()方法里会调用下面四行代码EntryK,V next e.next;
e.next newTable[i];
newTable[i] e;
e next;把元素插入新的HashMap中粗略的看下这四行代码似乎并没有什么问题,元素进行转移的图如下(线程不冲突的情况下)那么我们让线程A、B同时访问我这段代码当现A线程执行到以下代码时Entryk,v next e.next;线程A交出时间片线程B这时候接手转移并且完成了元素的转移这个时候线程A又拿到时间片并接着执行后续的代码执行后代码如图当e a时这时候这时候再执行e.next newTable[i];// a元素指向了b元素产生了循环 在链表产生了循环后当get()方法获取元素的时候正好落在这个循环的链表上时线程会一直在环里遍历无法跳出从而导致CPU飙升至100%总结在多线程情况下尽量不要用HashMap可以用线程安全的hash表来代替例如使用下面这些oncurrentHashMap、HashTable、Collections.synchronizedMap() 来避免产生多线程安全问题。往期推荐云计算到底是谁发明的长跑11年腾讯开源的变与不变低代码发展专访系列之一低代码平台产品的使用者都是谁内容整理志愿者招募了点分享点收藏点点赞点在看
