JDK1.7HashMap的死循环问题

HashMap的rehash源代码

Put一个Key,Value对到Hash表中：

 

检查容量是否超标：

新建一个更大尺寸的hash表，然后把数据从老的Hash表中迁移到新的Hash表中：

迁移的源代码，注意高亮处：

正常的ReHash的过程：

画了个图做了个演示。

• 我假设了我们的hash算法就是简单的用key mod 一下表的大小（也就是数组的长度）。
• 最上面的是old hash 表，其中的Hash表的size=2, 所以key = 3, 7, 5，在mod 2以后都冲突在table[1]这里了。、
• 接下来的三个步骤是Hash表 resize成4，然后所有的<key,value> 重新rehash的过程。

 

并发下的Rehash

1）假设我们有两个线程，线程一执行到1处就被调度挂起，而线程二执行完成：

主要源码：

运行结果：

此时，因为Thread1的 e 指向了key(3)，而next指向了key(7)，其在线程二rehash后，指向了线程二重组后的链表。我们可以看到链表的顺序被反转后。

2）线程一被调度回来执行：

继续执行（当前：e指向key（3） ，next 指向key（7））：

int i = indexFor(e.hash, newCapacity); // 计算索引位置，int i=3

e.next = newTable[i]; // 线程一的newTable[3]的值是null，所以e.next=null，e.next赋值为null，没有变化

newTable[i] = e; // newTable[3]赋值e

e = next; //为下一次循的e赋值，e指向key（7）

在下次循环时，e指向key（7） ，next 指向key（3）

3）线程一接着循环工作：

继续执行：（当前：e指向key（7） ，next 指向key（3））

Entry<K,V> next = e.next; // next指向key（3）

int i = indexFor(e.hash, newCapacity); // 计算索引位置，int i=3

e.next = newTable[i]; // 线程一的newTable[3]的值是key（3），所以e.next=key（3）

newTable[i] = e; // 摘下key（7），放到newTable[3]的第一个

e = next; //为下一次循的e赋值，e指向key（3）

在下次循环时，e指向key（3） ，next 指向null

4）线程一接着循环工作，出现环形链接：

继续执行：（当前：e指向key（3） ，next 指向null）

Entry<K,V> next = e.next; // next指向null

int i = indexFor(e.hash, newCapacity); // 计算索引位置，int i=3

e.next = newTable[i]; // 线程一的newTable[3]的值是key（7），所以e.next=key（7），即key（3）.next指向key（7）

注意：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了。

newTable[i] = e; // 把key（3），放到newTable[3]第一个

e = next; //为下一次循的e赋值，e为null

下次无循环，因为e为null，循环停止

 

5）调用HashTable.get(11)时，死循环