HashMap中的resize以及死链的情况

之前我已经写过关于HashMap的内容了:http://www.cnblogs.com/wang-meng/p/7545725.html

我们都知道HashMap是线程不安全的, 如果多线程来访问会有什么问题呢? 答案是会造成死锁。

接下来我们就分析下为何会造成死锁。

说到HashMap中死锁的情况, 我们就必须要先讲下resize()方法, 顾名思义, 这个方法就是来扩容的。

当HashMap的size超过 thredshold时, 就需要扩容了。 当我们put时:

(截图代码为JDK7 HashMap源码)

首先,我们需要知道几个最基本的概念: Entry<K,V>[] table的初始化长度length(默认值是16),Load factor为负载因子(默认值是0.75),threshold是HashMap所能容纳的最大数据量的Entry(键值对)个数。size是HashMap中实际存在 的键值对数量。threshold = length * Load factor。也就是说,在数组定义好长度之后,负载因子越大,所能容纳的键值对个数越多。

接着我们直接看上面的代码, 当size >= threshold且table[bucketIndex]不为空就会触发resize操作。 然后看resize()方法:

这里重点就是transfer方法, 接着我们来看transfer方法:

第一: 遍历旧的table

第二: 将旧的table中每个元素重新计算hash值, 然后赋予新的table中

具体我们将用图示的方法来解析:

单线程扩容:

假设:hash算法就是简单的key与length(数组长度)求余。

          hash表长度为2,如果不扩容, 那么元素key为3,5,7按照计算(key%table.length)的话都应该碰撞到table[1]上

扩容:hash表长度会扩容为4

          重新hash,key=3 会落到table[3]上(3%4=3), 当前e.next为key(7), 继续while循环

          重新hash,key=7 会落到table[3]上(7%4=3), 产生碰撞, 这里采用的是头插入法,所以key=7的Entry会排在key=3前面(这里可以具体看while语句中代码)

          当前e.next为key(5), 继续while循环

          重新hash,key=5 会落到table[1]上(5%4=3), 当前e.next为null, 跳出while循环, resize结束

如题如图所示:

多线程扩容:

这里我们先把核心代码搬出来, 方便查看

while(null != e) {

    Entry<K,V> next = e.next; //第一行

    int i = indexFor(e.hash, newCapacity); //第二行

    e.next = newTable[i]; //第三行

    newTable[i] = e; //第四行

    e = next; //第五行

}

去掉了一些冗余的代码, 层次结构更加清晰了。

第一行:记录odl hash表中e.next

第二行:rehash计算出数组的位置(hash表中桶的位置)

第三行:e要插入链表的头部, 所以要先将e.next指向new hash表中的第一个元素

第四行:将e放入到new hash表的头部

第五行: 转移e到下一个节点, 继续循环下去

核心代码如上所说, 下面就是多线程同时put的情况了, 然后同时进入transfer方法中:

假设这里有两个线程同时执行了put()操作,并进入了transfer()环节

while(null != e) {
    Entry<K,V> next = e.next; //线程1执行到这里被调度挂起了
    e.next = newTable[i];
    newTable[i] = e;
    e = next;
}

那么现在的状态为:

从上面的图我们可以看到,因为线程1的 e 指向了 key(3),而 next 指向了 key(7),在线程2 rehash 后,就指向了线程2 rehash 后的链表。

然后线程1被唤醒了:

  1. 执行e.next = newTable[i],于是 key(3)的 next 指向了线程1的新 Hash 表,因为新 Hash 表为空,所以e.next = null
  2. 执行newTable[i] = e,所以线程1的新 Hash 表第一个元素指向了线程2新 Hash 表的 key(3)。好了,e 处理完毕。
  3. 执行e = next,将 e 指向 next,所以新的 e 是 key(7)

然后该执行 key(3)的 next 节点 key(7)了:

  1. 现在的 e 节点是 key(7),首先执行Entry<K,V> next = e.next,那么 next 就是 key(3)了
  2. 执行e.next = newTable[i],于是key(7) 的 next 就成了 key(3)
  3. 执行newTable[i] = e,那么线程1的新 Hash 表第一个元素变成了 key(7)
  4. 执行e = next,将 e 指向 next,所以新的 e 是 key(3)

这时候的状态图为:

然后又该执行 key(7)的 next 节点 key(3)了:

  1. 现在的 e 节点是 key(3),首先执行Entry<K,V> next = e.next,那么 next 就是 null
  2. 执行e.next = newTable[i],于是key(3) 的 next 就成了 key(7)
  3. 执行newTable[i] = e,那么线程1的新 Hash 表第一个元素变成了 key(3)
  4. 执行e = next,将 e 指向 next,所以新的 e 是 key(7)

这时候的状态如图所示:

很明显,环形链表出现了!!当然,现在还没有事情,因为下一个节点是 null,所以transfer()就完成了,等put()的其余过程搞定后,HashMap 的底层实现就是线程1的新 Hash 表了。

参考:http://github.thinkingbar.com/hashmap-infinite-loop/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小红豆的数据分析

小蛇学python(19)装饰器

python的装饰器是python的特色高级功能之一,言简意赅得说,其作用是在不改变其原有函数和类的定义的基础上,给他们增添新的功能。

1112
来自专栏Pythonista

Python之路,Day2 - Python基础,列表,循环

1052
来自专栏owent

AC自动机

整个程序的算法思想是看别人的ACM的blog看懂的,感觉确实和KMP很像。但是代码呢就比较工程化一点。顺便回忆了一把ACM的感觉。

911
来自专栏Java成神之路

java_面试_01_一个月的面试总结(java)

       JVM内存管理机制和垃圾回收机制(基本每次面试都会问,一定要搞得透彻)

1233
来自专栏JAVA高级架构

java面试需要掌握知识点

重点知识 由于我面试的JAVA开发工程师,针对于JAVA,需要理解的重点内容有: JVM内存管理机制和垃圾回收机制(基本每次面试都会问,一定要搞得透彻) JVM...

3745
来自专栏灯塔大数据

干货 | 数据科学入门必读:如何使用正则表达式?

有时候,这些数据中会包含大量文本语料。比如,假如我们需要搞清楚「xxx文件 」中谁给谁发送过邮件,那么我们就要筛查 1150 万份文档!我们可以采用人工方式,亲...

1262
来自专栏Brian

Python进阶教程(一)

概述 hi,朋友们大家好,今天将英文原著作者 @yasoob《Intermediate Python》进行翻译和在工作中使用的Python技巧进行了总结。Git...

3837
来自专栏java一日一条

Java编程常见问题汇总3

这里本意是希望用当前类来加载希望的对象, 但是这里的getClass()可能抛出异常, 特别在一些受管理的环境中, 比如应用服务器, web容器, Java W...

822
来自专栏申龙斌的程序人生

零基础学编程020:强大的列表推导

问题描述:找出50之内的所有勾股数。 所谓勾股数,就是三个正整数,满足x*x + y*y = z*z。例如:3,4,5或5,12,13。 电脑解题只会用笨办法,...

28912
来自专栏owent

C++ 新特性学习(一) -- 概述+智能指针(smart_ptr)

C++ 0x/11 终于通过了,真是个很爽的消息。于是乎我决定对新的东西系统学习一下。

991

扫码关注云+社区

领取腾讯云代金券