专栏名称: 算法与数据结构
算法与数据结构知识、资源分享
目录
相关文章推荐
arXiv每日学术速递  ·  ViG3D-UNet:集成3D图与卷积模块, ... ·  10 小时前  
arXiv每日学术速递  ·  ViG3D-UNet:集成3D图与卷积模块, ... ·  10 小时前  
九章算法  ·  「九点热评」Meta面试新政策曝光 ·  昨天  
算法爱好者  ·  TikTok 又可以“续命” 75 天 ·  2 天前  
九章算法  ·  计算机专业走向,没有悬念了! ·  2 天前  
51好读  ›  专栏  ›  算法与数据结构

漫画:高并发下的HashMap

算法与数据结构  · 公众号  · 算法  · 2017-11-14 10:02

正文

请到「今天看啥」查看全文


, V > e : table ) {
while ( null != e) {
Entry< K , V > next = e. next ;
if (rehash) {
e. hash = null == e. key ? 0 : hash(e. key );
}
int i = indexFor (e. hash , newCapacity);
e. next = newTable[i];
newTable[i] = e;
e = next;
}
}
}








注意:下面的内容十分烧脑,请小伙伴们坐稳扶好。



假设一个HashMap已经到了Resize的临界点。此时有两个线程A和B,在同一时刻对HashMap进行Put操作:







此时达到Resize条件,两个线程各自进行Rezie的第一步,也就是扩容:




这时候,两个线程都走到了ReHash的步骤。让我们回顾一下ReHash的代码:



假如此时线程B遍历到Entry3对象,刚执行完红框里的这行代码,线程就被挂起。对于线程B来说:


e = Entry3

next = Entry2


这时候线程A畅通无阻地进行着Rehash,当ReHash完成后,结果如下(图中的e和next,代表线程B的两个引用):




直到这一步,看起来没什么毛病。接下来线程B恢复,继续执行属于它自己的ReHash。线程B刚才的状态是:


e = Entry3

next = Entry2


当执行到上面这一行时,显然 i = 3,因为刚才线程A对于Entry3的hash结果也是3。



我们继续执行到这两行,Entry3放入了线程B的数组下标为3的位置,并且 e指向了Entry2 。此时e和next的指向如下:


e = Entry2

next = Entry2


整体情况如图所示:





接着是新一轮循环,又执行到红框内的代码行:



e = Entry2

next = Entry3


整体情况如图所示:




接下来执行下面的三行,用头插法把Entry2插入到了线程B的数组的头结点:



整体情况如图所示:








请到「今天看啥」查看全文