JDK1.7 HashMap在并发执行put操作时会引起死循环，导致CPU利用率接近100%，这个是八股文内容之一，想必各位小伙伴也知道；在问到此问题的时候，可能有些面试官也会让我们讲讲这个死循环发生的过程，之前在面试某杭州电商的时候，也被问到过；如果回答不好，可能会被扣分。今天我就带大家一起梳理一下，这个问题是如何产生的。
本篇文章，会先从JDK1.7 HashMap底层数据结构，put()流程，然后通过图解演示的方式给大家讲解死循环的发生过程。
1.HahsMap数据结构
HashMap内部维护了一个数组table，每个元素是一个链表的头结点。链表中存储了具有相同hash值的键值对。在JDK1.7中，HashMap中的键值对使用Entry类表示。Entry类包含四个属性： key, value, hash 值和用于单向链表的next。
staticclassEntryimplementsMap.Entry {finalK key; V value; Entry next;inthash; Entry(inth, K k, V v, Entry n) { value = v; next = n; key = k; hash = h; }// 省略属性的访问get/set方法}复制代码
2.PUT流程及扩容机制
总体来说，put方法的实现比较复杂，涉及到哈希值的计算、扩容、索引的计算、链表的遍历和修改等多个操作；为了便于理解，工匠先将整个逻辑用流程图的方式给大家呈现出来，然后逐行分析源码，源码分析的地方可能比较长，大家可通过先记流程图，然后看源码解析部分：
2.1 put
publicVput(K key, Vvalue){if(table == EMPTY_TABLE) { inflateTable(threshold); }if(key ==null)returnputForNullKey(value);inthash = hash(key);inti = indexFor(hash, table.length);for(Entry e = table[i]; e !=null; e = e.next) { Object k;if(e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value=value; e.recordAccess(this);returnoldValue; } } modCount++; addEntry(hash, key,value, i);returnnull;}复制代码
我们逐行解析这个方法：
如果当前 table 为空，则调用 inflateTable 方法创建 table 数组；
如果 key 为 null，则调用 putForNullKey 方法添加该键值对，该方法单独处理；
通过调用hash()方法计算 key 的哈希值 hash，以及该键值对在 table 数组中的位置 i，索引 i 的定位通过调用方法indexFor；
遍历 table[i] 链表，如果找到已存在的键值对，则将其 value 值替换为新值，并返回旧值；
如果没有找到已存在的键值对，则将新的键值对添加到链表的头部，并返回 null
下面我们再依次讲解inflateTable、putForNullKey、hash、indexFor、addEntry等方法的源码：
2.1.1 inflateTable
privatevoidinflateTable(inttoSize){// Find a power of 2 >= toSizeintcapacity = roundUpToPowerOf2(toSize); threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY +1); table =newEntry[capacity]; initHashSeedAsNeeded(capacity);}复制代码
这个方法会将 table 数组扩容到指定大小。首先调用 roundUpToPowerOf2 方法将 toSize 扩容到最接近的 2 的幂次方。然后计算新的阈值 threshold，并根据新的 capacity 创建一个新的 table 数组。最后，如果需要的话，会调用 initHashSeedAsNeeded 方法来初始化哈希种子
2.1.2 putForNullKey
privateVputForNullKey(Vvalue){for(Entry e = table[0]; e !=null; e = e.next) {if(e.key ==null) { V oldValue = e.value; e.value=value; e.recordAccess(this);returnoldValue; } } modCount++; addEntry(0,null,value,0);returnnull;}复制代码
这个方法用于添加键为 null 的键值对。它会遍历 table[0] 链表，查找是否已经存在键为 null 的键值对。如果找到了，就将其 value 值替换为新值，并返回旧值。如果没有找到，就将新的键值对添加到链表头部，并返回 null。
最后，如果没有找到已存在的键值对，就会在 modCount 中增加 1，表示对 HashMap 进行了修改操作。这是 HashMap 用于实现 fail-fast 机制的一部分
2.1.3 hash
staticinthash(Object key){inth;return(key ==null) ?0: (h = key.hashCode()) ^ (h >>>16);}复制代码
这个方法用于计算键的哈希值。如果键为 null，则哈希值为 0；否则，将计算出的哈希值右移 16 位，并将其与原始哈希值进行异或运算，以减少哈希碰撞的概率。
2.1.4 indexFor
staticintindexFor(inth,intlength){returnh & (length-1);}复制代码
indexFor这个方法用于计算键值对在table 数组中的索引位置。因为 table 的长度必须是 2 的幂次方，所以可以用位运算来代替取模运算，提高性能。看到这个方法，小伙伴应该知道，hashMap为要设置长度为2的幂次方了吧
2.1.5 addEntry
voidaddEntry(inthash, K key, Vvalue,intbucketIndex){if((size >= threshold) && (null!= table[bucketIndex])) { resize(2* table.length); hash = (null!= key) ? hash(key) :0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key,value, bucketIndex);}voidcreateEntry(inthash, K key, Vvalue,intbucketIndex){ Entry e = table[bucketIndex]; table[bucketIndex] =newEntry(hash, key,value, e); size++;}复制代码
addEntry 方法用于在 table 中添加新的键值对。如果 size 大于等于 threshold，则表示 table 数组已经达到了负载因子，需要对 table 进行扩容，这里是调用 resize 方法进行扩容。然后再计算一次 hash 值和 bucketIndex 的值。接下来是调用 createEntry 方法创建一个新的键值对，并将其添加到 table[bucketIndex] 的头部，最后将 size 加 1
梳理了新的键值对添加过程，我们再看看resize方法扩容逻辑
2.1.5.1 resize -扩容
resize 方法的实现如下：
voidresize(intnewCapacity){ Entry[] oldTable = table;intoldCapacity = oldTable.length;if(oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE;return; } Entry[] newTable =newEntry[newCapacity]; transfer(newTable); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY +1);}voidtransfer(Entry[] newTable){intnewCapacity = newTable.length;for(Entry e : table) {while(null!= e) { Entry next = e.next;inti = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } }}复制代码
resize方法首先将旧的 table 数组和阈值 threshold 存储起来，以便在扩容后使用。如果旧的 table 数组已经达到了最大容量 MAXIMUM_CAPACITY，就将阈值设置为 Integer.MAX_VALUE，表示不能再进行扩容。然后创建一个新的 Entry 数组 newTable，并调用 transfer 方法将旧的 Entry 对象复制到新的数组中。最后将 table 数组引用指向新的 Entry 数组，并重新计算阈值 threshold。
transfer该方法的作用是将HashMap对象的所有元素转移到新的哈希表数组中；具体的逻辑：
对于每个非空桶：会将旧表中当前桶的引用设置为null，会通过一个循环处理当前桶中的所有元素。在循环内部，它使用indexFor方法计算每个元素在新表中应该插入的位置。
然后，它将当前元素的next指针保存到一个临时变量next中，以便在循环的下一次迭代中访问它。接下来，它将当前元素的next指针设置为新表中对应桶的头部。最后，它将新表中对应桶的头部设置为当前元素，将当前元素插入到新表中
因为transfer逻辑是理解死循环的重要流程，下面我再通过图解方式描述一下该方法逻辑：假设数据有三条，key分别是20,28,36：
原链表的顺序为：20 -> 28 -> 36； 在经过transfer将数据转移到新的table之和，链表顺序为： 36 -> 28 -> 20
总结下来：在转移链表数据的过程中，采用的是头插法。既待插入的entry都放到数组tab[i]的位置，然后将待插入的entry的next指针指向之前放入到tab[i]位置的 entry。
3.并发条件下的死循环
乍一看，上面transfer方法转移链表数据的过程，没啥毛病啊，采用头插法，代码理解起来也贼容易，而且代码量也不多；当然，单线程环境下的确没啥毛病，那么我们来看看在并发环境下的过程：
假设初始状态下：HashMap有两个元素A,B，如下：
假设有Thread1和Thread2两个线程向HashMap中添加数据，Thread1首先获取执行权，向HashMap插入数据的时候开始扩容，当创建一个新的数组，还没来得及转移旧的数据的时候，Thread2此时获得执行权；那么，对于Thread1而言，此时的HashMap结构如下，链表结构：A -> B
假如thread2开始执行之后，添加数据的时候又开始扩容，并完成了扩容操作，则此时的HashMap结构如下，链表结果 B->A
当Thread2 执行结束之后，放弃CPU执行权，Thread1继续之前未完成的扩容操作，在上面我们说过，对于Thread1而言，其链表结构是：A->B。此处，我们再拿transfer方法代码分析：
voidtransfer(Entry[] newTable){intnewCapacity = newTable.length;for(Entry e : table) {while(null!= e) { Entry next = e.next;inti = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } }}复制代码
我们假设Thread1是执行到代码newTable[i] = e挂起的，从哪里挂起，就从哪里执行；那么当Thread1再次获取到执行权的时候，此时e就是A；执行下一步e=next，此时next为B，继续执行循环内容，但是此时因为Thread2的扩容，B.next已经指向了A，最终遍历e不为null，然后循环继续。此处就一直无限循环下去。
4.总结
在JDK1.7中，HashMap扩容死循环的根本原因是由于在并发情况下，多个线程同时对同一个桶进行操作时，可能会导致链表形成环形结构。解决这个问题的方法有以下2种：
使用线程安全的HashMap实现，例如ConcurrentHashMap，这些实现使用了锁或其他同步机制来保证线程安全。
在put操作时使用synchronized关键字来保证线程安全，这样可以避免多个线程同时对同一个桶进行操作，从而避免链表形成环形结构。
