HashMap的ReHash图解

  • Z时代
  • 2024-01-10
  • 分类：综合

编程

昨天在看redis的hash扩容时提到了与java的hashmap类似，之前一直没有仔细研究过，翻了几篇博客，选了容易理解的一片转载下。

  • resize方法

voidresize(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方法

voidtransfer(Entry[] newTable)
{
    Entry[] src = table;
    intnewCapacity = newTable.length;
//下面这段代码的意思是：
//  从OldTable里摘一个元素出来，然后放到NewTable中
for(int j =0; j < src.length; j++){
        Entry<K,V> e = src[j];
if(e !=null){
            src[j]=null;
do{
                Entry<K,V> next = e.next;
                //获取元素在新表中的位置索引
                int i =indexFor(e.hash, newCapacity);
                //将新表中的元素赋值给当前元素e的next
                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)

3、线程一继续执行

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

4、环形链接出现

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


   

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

以上是 HashMap的ReHash图解 的全部内容， 来源链接： utcz.com/z/514942.html

回到顶部