HashMap的rehash源代码

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

检查容量是否超标：

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

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

正常的ReHash的过程：

画了个图做了个演示。

• 假设hash算法是简单的key%table.length 。
• 最上面是old hash表，它的hash表的长度是2, 在key = 3, 7, 5时，key%2都在table[1]位置，会发生hash冲突。
• 接下来的三个步骤是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)时，死循环