共计 4416 个字符，预计需要花费 12 分钟才能阅读完成。
jdk1.7 hashmap 的循环依赖问题是面试常常被问到的问题，如何答复不好，可能会被扣分。明天我就带大家一下梳理一下，这个问题是如何产生的，以及如何解决这个问题。
一、hashmap 的数据结构
先一起看看 jdk1.7 hashmap 的数据结构
数组 + 链表
hashmap 会给每个元素的 key 生成一个 hash 值，而后依据这个 hash 值计算一个在数组中的地位 i。i 不同的元素放在数组的不同地位，i 雷同的元素放在链表上，最新的数据放在链表的头部。
往 hashmap 中保留元素会调用 put 办法，获取元素会调用 get 办法。接下来，咱们重点看看 put 办法。
二、put 办法
重点看看 put 办法
public V put(K key, V value) {if (table == EMPTY_TABLE) {inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
// 依据 key 获取 hash
int hash = hash(key);
// 计算在数组中的下表
int i = indexFor(hash, table.length);
// 变量汇合查问雷同 key 的数据，如果曾经存在则更新数据
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++;
// 如果不存在雷同 key 的元素，则增加新元素
addEntry(hash, key, value, i);
return null;
}再看看 addEntry 办法
void addEntry(int hash, K key, V value, int bucketIndex) {
// 当数组的 size >= 扩容阈值，触发扩容，size 大小会在 createEnty 和 removeEntry 的时候扭转
if ((size >= threshold) && (null != table[bucketIndex])) {
// 扩容到 2 倍大小，后边会跟进这个办法
resize(2 * table.length);
// 扩容后从新计算 hash 和 index
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
// 创立一个新的链表节点，点进去能够理解到是将新节点增加到了链表的头部
createEntry(hash, key, value, bucketIndex);
}看看 resize 是如何扩容的
void resize(int newCapacity) {Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 创立 2 倍大小的新数组
Entry[] newTable = new Entry[newCapacity];
// 将旧数组的链表转移到新数组，就是这个办法导致的 hashMap 不平安，等下咱们进去看一眼
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
// 从新计算扩容阈值 (容量 * 加载因子)
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) {e.hash = null == e.key ? 0 : hash(e.key);
}
// 计算节点在新数组中的下标
int i = indexFor(e.hash, newCapacity);
// 将旧节点插入到新节点的头部
e.next = newTable[i];
// 这行才是真正把数据插入新数组中，后面那行代码只是设置以后节点的 next
// 这两行代码决定了倒序插入
// 比方：以前同一个地位上是:3，7，前面可能变成了：7、3
newTable[i] = e;
// 将下一个元素赋值给以后元素，以便遍历下一个元素
e = next;
}
}
}我来给大家剖析一下，为什么这几个代码是头插法，网上很多技术文章都没有说分明。
三、头插法
咱们把眼光聚焦到这几行代码：
// 获取下一个元素，记录到一个长期变量，以便前面应用
Entry<K,V> next = e.next;
// 计算节点在新数组中的下标
int i = indexFor(e.hash, newCapacity);
// 将旧节点插入到新节点的头部
e.next = newTable[i];
// 这行才是真正把数据插入新数组中，后面那行代码只是设置以后节点的 next
newTable[i] = e;
// 将下一个元素赋值给以后元素，以便遍历下一个元素
e = next;假如刚开始 hashMap 有这些数据
调用 put 办法须要进行一次扩容，刚开始会创立一个空的数组，大小是以前的 2 倍，如图所示：
开始第一轮循环：
//next= 7 e = 3 e.next = 7
Entry<K,V> next = e.next;
// i=3
int i = indexFor(e.hash, newCapacity);
//e.next = null，刚初始化时新数组的元素为 null
e.next = newTable[i];
// 给新数组 i 地位 赋值 3
newTable[i] = e;
// e = 7
e = next;执行完之后，第一轮循环之后数据变成这样的
再接着开始第二轮循环：
//next= 5 e = 7 e.next = 5
Entry<K,V> next = e.next;
// i=3
int i = indexFor(e.hash, newCapacity);
//e.next = 3，此时雷同地位上曾经有 key= 3 的值了，将该值赋值给以后元素的 next
e.next = newTable[i];
// 给新数组 i 地位 赋值 7
newTable[i] = e;
// e = 5
e = next;下面会形成一个新链表，连贯的程序正好反过来了。
因为第二次循环时，节点 key= 7 的元素插到雷同地位上已有元素 key= 3 的后面，所以说是采纳的头插法。
四、死循环的产生
接下来重点看看死循环是如何产生的？
假如数据跟元素数据统一，有两个线程：线程 1 和 线程 2，同时执行 put 办法，最初同时调用 transfer 办法。
线程 1 先执行，到 Entry<K,V> next = e.next; 这一行，被挂起了。
//next= 7 e = 3 e.next = 7
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;此时线程 1 创立的数组会创立一个空数组
接下来，线程 2 开始执行，因为线程 2 运气比拟好，没有被中断过，执行结束了。
过一会儿，线程 1 被复原了，从新执行代码。
//next= 7 e = 3 e.next = 7
Entry<K,V> next = e.next;
// i = 3
int i = indexFor(e.hash, newCapacity);
// e.next = null，刚初始化时新数组的元素为 null
e.next = newTable[i];
// 给新数组 i 地位 赋值 3
newTable[i] = e;
// e = 7
e = next;这时候线程 1 的数组会变成这样的
再执行第二轮循环，此时的 e =7
//next= 3 e = 7 e.next = 3
Entry<K,V> next = e.next;
// i = 3
int i = indexFor(e.hash, newCapacity);
// e.next = 3，此时雷同地位上曾经有 key= 3 的值了，将该值赋值给以后元素的 next
e.next = newTable[i];
// 给新数组 i 地位 赋值 7
newTable[i] = e;
// e = 3
e = next;这里特地要阐明的是 此时 e =7，而 e.next 为什么是 3 呢？
因为 hashMap 的数据是公共的，还记得线程 2 中的生成的数据吗？
此时 e =7，那么 e.next 必定是 3。
通过下面第二轮循环之后，线程 1 失去的数据如下：
此时因为循环判断还没有退出，判断条件是：while(null != e)，所以要开始第三轮循环：
//next= null e = 3 e.next = null
Entry<K,V> next = e.next;
// i = 3
int i = indexFor(e.hash, newCapacity);
// e.next = 7，要害的一步，因为第二次循环是 key:7 .next = key:3，当初 key:3.next = key:7
e.next = newTable[i];
// 给新数组 i 地位 赋值 3
newTable[i] = e;
// e = null
e = next;因为 e =null，此时会退出循环，最终线程 1 的数据会是这种构造：
key:3 和 key:7 又复原了刚开始的程序，然而他们的 next 会互相援用，形成环形援用。
留神，此时调用 hashmap 的 get 办法获取数据时，如果只是获取循环链上 key:3 和 key:7 的数据，是不会有问题的，因为能够找到。就怕获取循环链上没有的数据，比方：key:11，key:15 等，会进入有限循环中导致 CPU 使用率飙升。
五、如何防止死循环
为了解决这个问题，jdk1.8 把扩容是复制元素到新数组由 头插法 改成了 尾插法。此外，引入了红黑树，晋升遍历节点的效率。在这里我就不过多介绍了，如果有趣味的敌人，能够关注我的公众号，前面会给大家详细分析 jdk1.8 的实现，以及 jdk1.7、jdk1.8 hashmap 的区别。
此外，HashMap 是非线程平安的，要防止在多线程的环境中应用 HashMap，而应该改成应用 ConcurrentHashMap。
所以总结一下要防止产生死循环的问题的办法：改成 ConcurrentHashMap
