• resize方法

void resize(intnewCapacity)

{

Entry[] oldTable = table;

intoldCapacity = oldTable.length;

......

//创建一个新的Hash Table

Entry[] newTable =new Entry[newCapacity];

//将Old Hash Table上的数据迁移到New Hash Table上

transfer(newTable);

table = newTable;

threshold = (int)(newCapacity * loadFactor);

}

• transfer方法

void transfer(Entry[] newTable)

{

Entry[] src = table;

intnewCapacity = newTable.length;

//下面这段代码的意思是：

// 从OldTable里摘一个元素出来，然后放到NewTable中

for(intj = 0; j < src.length; j++) {

Entry<K,V> e = src[j];

if(e != null) {

src[j] =null;

do{

Entry<K,V> next = e.next;

inti = indexFor(e.hash, newCapacity);

e.next = newTable[i];

newTable[i] = e;

e = next;

}while (e != null);

}

}

}

单线程下的ReHash

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

详细描述可以看下面这张图：

并发下的Rehash

1. 假设我们有两个线程。我用红色和浅蓝色标注了一下。

do{

Entry<K,V> next = e.next;// <--假设线程一执行到这里就被调度挂起了

inti = indexFor(e.hash, newCapacity);

e.next = newTable[i];

newTable[i] = e;

e = next;

}while (e != null);

而我们的线程二执行完成了。于是我们有下面的这个样子。

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

1. 线程一被调度回来执行。

• 先是执行 newTalbe[i] = e;
• 然后是e = next，导致了e指向了key(7)，
• 而下一次循环的next = e.next导致了next指向了key(3)

1. 线程一继续执行

把key(7)摘下来，放到newTable[i]的第一个，然后把e和next往下移

1. 环形链接出现

e.next = newTable[i] 导致 key(3).next 指向了 key(7)

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

当我们的线程一调用到HashTable.get(11)时，悲剧就出现了——Infinite Loop