咱们好，JDK1.7 HashMap在并发履行put操作时会引起死循环，导致CPU利用率挨近100%，这个是八股文内容之一，想必各位小伙伴也知道；在问到此问题的时分，或许有些面试官也会让咱们讲讲这个死循环产生的进程，工匠之前在面试某杭州电商的时分，也被问到过；假如回答不好，或许会被扣分。今天我就带咱们一起整理一下，这个问题是如何产生的。
本篇文章，工匠会先从JDK1.7 HashMap底层数据结构，put()流程，然后通过图解演示的办法给咱们解说死循环的产生进程。
1.HahsMap数据结构
HashMap内部保护了一个数组table，每个元素是一个链表的头结点。链表中存储了具有相同hash值的键值对。在JDK1.7中，HashMap中的键值对运用Entry类表明。Entry类包含四个特点： key, value, hash 值和用于单向链表的next。
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
// 省略特点的拜访get/set办法
}
2.PUT流程及扩容机制
整体来说，put办法的完成比较复杂，涉及到哈希值的核算、扩容、索引的核算、链表的遍历和修改等多个操作；为了便于理解，工匠先将整个逻辑用流程图的办法给咱们出现出来，然后逐行剖析源码，源码剖析的地方或许比较长，咱们可通过先记流程图，然后看源码解析部分：
2.1 put
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> 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);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
咱们逐行解析这个办法：
- 假如当时
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
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
这个办法会将 table 数组扩容到指定大小。首要调用 roundUpToPowerOf2 办法将 toSize 扩容到最挨近的 2 的幂次方。然后核算新的阈值 threshold，并依据新的 capacity 创建一个新的 table 数组。终究，假如需要的话，会调用 initHashSeedAsNeeded 办法来初始化哈希种子
2.1.2 putForNullKey
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
这个办法用于添加键为 null 的键值对。它会遍历 table[0] 链表，查找是否现已存在键为 null 的键值对。假如找到了，就将其 value 值替换为新值，并回来旧值。假如没有找到，就将新的键值对添加到链表头部，并回来 null。
终究，假如没有找到已存在的键值对，就会在 modCount 中添加 1，表明对 HashMap 进行了修改操作。这是 HashMap 用于完成 fail-fast 机制的一部分
2.1.3 hash
static int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这个办法用于核算键的哈希值。假如键为 null，则哈希值为 0；否则，将核算出的哈希值右移 16 位，并将其与原始哈希值进行异或运算，以削减哈希碰撞的概率。
2.1.4 indexFor
static int indexFor(int h, int length) {
return h & (length-1);
}
indexFor这个办法用于核算键值对在table 数组中的索引方位。因为 table 的长度必须是 2 的幂次方，所以能够用位运算来代替取模运算，进步性能。看到这个办法，小伙伴应该知道，hashMap为要设置长度为2的幂次方了吧
2.1.5 addEntry
void addEntry(int hash, K key, V value, int bucketIndex) {
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);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(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 办法的完成如下：
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);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
void transfer(Entry[] newTable) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while (null != e) {
Entry<K,V> next = e.next;
int i = 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：
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办法代码剖析：
void transfer(Entry[] newTable) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while (null != e) {
Entry<K,V> next = e.next;
int i = 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关键字来确保线程安全，这样能够防止多个线程一起对同一个桶进行操作，从而防止链表构成环形结构。
