请选择 进入手机版 | 继续访问电脑版

ConcurrentHashMap的源码分析-为什么要做高低位的划分

[复制链接]
林雨宣 发表于 2021-1-2 19:45:40 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
要想相识这么设计的目的,我们需要从ConcurrentHashMap的根据下标获取对象的算法来看,在putVal方法中1018行
(f = tabAt(tab, i = (n - 1) & hash)) == null
通过(n-1) & hash来得到在table中的数组下标来获取节点数据,【&运算是二进制运算符,1 & 1=1,其他都为0】
假设我们的table长度是16, 二进制是【0001 0000】,减一以后的二进制是 【0000 1111】
如果某个key的hash值=9,对应的二进制是【0000 1001】,那么按照(n-1) & hash的算法
0000 1111 & 0000 1001 =0000 1001 , 运算效果是9 
当我们扩容以后,16变成了32,那么(n-1)的二进制是 【0001 1111】
仍然以hash值=9的二进制盘算为例
0001 1111 & 0000 1001 =0000 1001 ,运算效果仍然是9 
我们换一个数字,如果某个key的hash值是20,对应的二进制是【0001 0100】,仍然按照(n-1) & hash算法,分别在16为长度和32位长度下的盘算效果
16位: 0000 1111 & 0001 0100=0000 0100
32位: 0001 1111 & 0001 0100 =0001 0100
从效果来看,同样一个hash值,在扩容前和扩容之后,得到的下标位置是不一样的,这种情况固然是不允许出现的,所以在扩容的时候就需要思量,
而使用高低位的迁移方式,就是管理这个问题.
各人可以看到,16位的效果到32位的效果,正好增加了16. 
比如 20 & 15=4 、20 & 31=20 ; 4-20 =16
比如 60 & 15=12 、60 & 31=28; 12-28=16 
所以对于高位,直接增加扩容的长度,当下次hash获取数组位置的时候,可以直接定位到对应的位置。
这个地方又是一个很巧妙的设计,直接通过高低位分类以后,就使得不需要在每次扩容的时候来重新盘算hash,极大提升了效率。
 

来源:https://blog.csdn.net/Leon_Jinhai_Sun/article/details/112062598
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )