写点什么

面试官:多线程环境下,HashMap 为什么会出现死循环?

  • 2021 年 11 月 12 日
  • 本文字数:1598 字

    阅读完需:约 5 分钟

//如果该 key 已被插入,则替换掉旧的 value (链接操作)


for (Entry<K,V> e = table[i]; e != null; e = e.next) {


Object k;


if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {


V oldValue = e.value;


e.value = value;


e.recordAccess(this);


return oldValue;


}


}


modCount++;


//该 key 不存在,需要增加一个结点


addEntry(hash, key, value, i);


return null;


}


当我们往 HashMap 中 put 元素的时候,先根据 key 的 hash 值得到这个元素在数组中的位置(即下标),然后就可以把这个元素放到对应的位置中了。


如果这个元素所在的位置上已经存放有其他元素了,那么在同一个位置上的元素将以链表的形式存放。新加入的元素放在链头,而先前加入的放在链尾。


检查容量是否超标 addEntry:


void addEntry(int hash, K key, V value, int bucketIndex) {


Entry<K,V> e = table[bucketIndex];


table[bucketIndex] = new Entry<K,V>(hash, key, value, e);


//查看当前的 size 是否超过了我们设定的阈值 threshold,如果超过,需要 resize


if (size++ >= threshold) {


resize(2 * table.length);


}


}


如果现在 size 已经超过了 threshold,那么就要进行 resize 操作。新建一个更大尺寸的 hash 表,然后把数据从老的 Hash 表中迁移到新的 Hash 表中。


调整 Hash 表大小 resize:


void resize(int newCapacity) {


Entry[] oldTable = table;


int oldCapacity = oldTable.length;


// ......


//创建一个新的 Hash Table


Entry[] newTable = new Entry[newCapacity];


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


transfer(newTable);


table = newTable;


threshold = (int)(newCapacity * loadFactor);


}


当 table[] 数组容量较小,容易产生哈希碰撞。所以,Hash 表的尺寸和容量非常的重要。


一般来说,Hash 表这个容器当有数据要插入时,都会检查容量有没有超过设定的 thredhold。如果超过,需要增大 Hash 表的尺寸,这个过程称为 resize。


多个线程同时往 HashMap 添加新元素时,多次 resize 会有一定概率出现死循环。因为每次 resize 需要把旧的数据映射到新的哈希表,这一部分代码在 HashMap#transfer() 方法中


void transfer(Entry[] newTable) {


Entry[] src = table;


int newCapacity = 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 = newTable[i];


newTable[i] = e;


e = next;


} while (e != null);


}


}


}


标红代码是导致多线程使用 hashmap 出现 CPU 使用率骤增,出现死循环,从而多个线程阻塞的罪魁祸首。


3、图解 HashMap 死循环



3.1 正常的 reHash 的过程(单线程)

假设了我们的 hash 算法就是简单的用 key mod 一下表的大小(也就是数组的长度)。


最上面的是 old hash 表,其中的 Hash 表的 size=2,。所以 key = 3, 7, 5,在 mod 2 以后都冲突在 table[1] 这里了。


接下来的三个步骤是 Hash 表 resize 成 4,然后所有的 <key,value> 重新 rehash 的过程。



3.2 并发下的 Rehash(多线程)


假设我们有两个线程。


do {


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


【一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开:qq.cn.hn/FTf 免费领取
复制代码


起了,执行其他操作


int i = indexFor(e.hash, newCapacity);


e.next = newTable[i];


newTable[i] = e;


e = next;


} while (e != null);


而我们的线程二执行完成了。于是我们有下面这张图:



注意:因为 Thread1 的 e 指向了 key(3),而 next 指向了 key(7),其在线程二 rehash 后,指向了线程二重组后的链表。我们可以看到,链表的顺序被反转后,在这里线程一变成了操作经过线程二操作后的 HashMap。


线程一调度执行。


  • 先是执行 newTalbe[i] = e;

评论

发布
暂无评论
面试官:多线程环境下,HashMap为什么会出现死循环?