数据结构
HashMap 使用哈希表也叫散列表来存储数据的，哈希表为解决冲突，可以采用开放地址法、链地址法等来解决问题，Java 中 HashMap 采用了链地址法，即数组（主） + 单链表（副）的形式。
1.7 中 HashMap 死循环分析
在多线程环境下，使用 HashMap 进行 put 操作会引起死循环，导致 CPU 利用率接近 100%，HashMap 在并发执行 put 操作时会引起死循环，是因为多线程会导致 HashMap 的 Entry 链表形成环形数据结构，一旦形成环形数据结构，Entry 的 next 节点永远不为空， 就会产生死循环获取 Entry。那么这个死循环是如何生成的呢？我们来仔细分析下。
HashMap 扩容流程
引发死循环，是在 HashMap 的扩容操作中。
正常的扩容操作是这个流程。HashMap 的扩容在 put 操作中会触发扩容，主要是三个方法：
// 添加键值对（Entry ）到 HashMap中
void addEntry(int hash, K key, V value, int bucketIndex) {
// 如果键值对的数量大于等于阀值并且哈希表中对应的位置不为 null
if ((size >= threshold) && (null != table[bucketIndex])) {
// 将哈希表扩容为原来的 2 倍
resize(2 * table.length);
// 判断传入的 key 是否为空，不为空则再次调用 hash 方法计算 hash 值
hash = (null != key) ? hash(key) : 0;
// 根据新表的长度重新计算所放的位置
bucketIndex = indexFor(hash, table.length);
}
}
// 当容量不足时（容量 > 阈值），则扩容（扩到2倍）
void resize(int newCapacity) {
// 获取旧的 table 数组
Entry[] oldTable = table;
// 获取旧的数组的长度
int oldCapacity = oldTable.length;
// 极端情况，如果旧的长度已经是最大容量
if (oldCapacity == MAXIMUM_CAPACITY) {
// 直接等于最大容量
threshold = Integer.MAX_VALUE;
return;
}
// 1.初始化一个新的 Entry 数组，传入的参数是旧的数组的两倍
Entry[] newTable = new Entry[newCapacity];
// 2.将键值对转移到新的 Entry 数组
transfer(newTable, initHashSeedAsNeeded(newCapacity));
// 3.将新的数组赋值给旧的数组
table = newTable;
// 4.重新计算阀值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
// 作用：将旧数组上的数据（键值对）转移到新table中，从而完成扩容
// 过程：按旧链表的正序遍历链表、在新链表的头部依次插入
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
// 遍历哈希表 table
for (Entry<K,V> e : table) {
while(null != e) {
// next 用来保存头节点的下一个节点
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 计算在元素在新的哈希表中的位置
int i = indexFor(e.hash, newCapacity);
// 将元素放在数组上：采用单链表的头插入方式 = 在链表头上存放数据 = 将数组位置的原有数据放在后1个指针、将需放入的数据放到数组位置中
// 即 扩容后，可能出现逆序：按旧链表的正序遍历链表、在新链表的头部依次插入
e.next = newTable[i];
newTable[i] = e;
// 访问下1个Entry链上的元素，如此不断循环，直到遍历完该链表上的所有节点
e = next;
}
}
}
综合来说，HashMap 一次扩容的过程：
- 1、取当前 table 的 2 倍作为新 table 的大小
- 2、根据算出的新 table 的大小 new 出一个新的 Entry 数组来，名为 newTable
- 3、轮询原 table 的每一个位置，将每个位置上连接的 Entry，算出在新 table 上的位置，并以链表形式连接
- 4、原 table 上的所有 Entry 全部轮询完毕之后，意味着原 table 上面的所有 Entry 已经移到了新的 table 上，HashMap 中的 table 指向 newTable
实例介绍
现在 HashMap 中有三个元素，Hash 表的 size=2, 所以 key = 3, 7, 5，在 mod 2(对2取余) 以后都冲突在 table[1] 这里了。
按照方法中的代码：
对 table[1] 中的链表来说，进入 while 循环，此时 e=key(3)，那么 next=key(7)， 经过计算重新定位 e=key(3) 在新表中的位置，并把 e=key(3) 挂在 newTable[3] 的位置。
这样循环下去，将 table[1] 中的链表循环完成后，于是 HashMap 就完成了扩容。
并发下的扩容
上面都是单线程下的扩容，当多线程进行扩容时，会是什么样子呢？ 初始的 HashMap 还是：
我们现在假设有两个线程并发操作，都进入了扩容操作。
我们以颜色进行区分两个线程。
我们假设，线程 1 执行到 Entry<K,V> next = e.next; 时被操作系统调度挂起了，而线程 2 执行完成了扩容操作。
于是，在线程 1,2 看来，就应该是这个样子。
接下来，线程 1 被调度回来执行：
1）
2）
3）
4）
5）
6）
7）
循环列表产生后，一旦线程 1 调用 get（11,15 之类的元素）时，就会进入一 个死循环的情况，将 CPU 的消耗到 100%。
总结
HashMap 之所以在并发下的扩容造成死循环，是因为，多个线程并发进行时，因为一个线程先期完成了扩容，将原 Map 的链表重新散列到自己的表中， 并且链表变成了倒序，后一个线程再扩容时，又进行自己的散列，再次将倒序链表变为正序链表。于是形成了一个环形链表，当 get 表中不存在的元素时，造成死循环。
网友评论