HashMap的ReHash图解

• 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的过程

image

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

image

并发下的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);

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

image

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

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

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

image

3. 线程一继续执行

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

image

4. 环形链接出现

e.next = newTable[i] 导致 key(3).next 指向了 key(7)
注意：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了。

image

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