开发者社区> 李不言> 正文

HashMap容量分析

简介: 了解过HashMap都应该知道,HashMap内部会创建一个Entry table数组来存放元素,而且这个数组的长度永远都是2的指数次方。那么问题来了,为什么选择2的指数次方呢? 首先,思考一下计算出hash值后,应该存放在数组的哪个位置?显然用求余(模)最简单。
+关注继续查看

了解过HashMap都应该知道,HashMap内部会创建一个Entry<K, V> table数组来存放元素,而且这个数组的长度永远都是2的指数次方。那么问题来了,为什么选择2的指数次方呢?
首先,思考一下计算出hash值后,应该存放在数组的哪个位置?显然用求余(模)最简单。然而模的效率并不高,看看JDK是怎么做的,indexFor方法:

static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

其中h就是hash值,length是table的长度。对2的指数次方求模运算(h % length)和h & (length-1)结果是一样的,这点从代码注释也可以知道,不明白可以看最后的备注。

接着看看为什么容量是2的指数次方的问题,假如容量分别是16和15两种情况,对应的length-1的二进制分别是11111110,然后我们思考hash值分别是8和9这两种情况,8 & 1111 = 8,9 & 1111 = 9,存放在table[8]和table[9]对应的位置,没有发生碰撞;然后8 & 1110 = 8,9 & 1110 = 8,两个hash值都被存放在了table的同一位置,显然发生了碰撞。放大来看,如果容量是15的话,length - 1对应的二进制是1110,进行与运算后,最后一位永远是0,即xxx0,这将会导致table中0001001101011001101101111101这几个位置永远都不能存放元素了,空间浪费不说,碰撞概率也增大。而我们2的指数次方对应的数length-1后二进制全是1,进行与运算显然不会干扰到原hash值,不会导致table中哪个位置不能存放元素。

解释一下“对2的指数次方求模运算(h % length)和h & (length-1)结果是一样的”,以4(二进制为11)为例:
0 % 4 = 0 同 4 % 4 = 0 ……
1 % 4 = 1 同 5 % 4 = 1 ……
2 % 4 = 2 同 6 % 4 = 2 ……
3 % 4 = 3 同 7 % 4 = 3 ……
00 & 11 = 0 同 100 && 11 = 0 ……
01 & 11 = 1 同 101 && 11 = 1 ……
10 & 11 = 2 同 110 && 11 = 2 ……
11 & 11 = 3 同 111 && 11 = 3 ……
明显,求余运算每4个一循环,对应二进制大于4之后,高位的数字与0进行与运算,始终为0,效果等同于每4个一循环。

总结一下:使用2的指数次方作为HashMap中存放元素数组的大小,可以避免求余操作,效率较高,同时,减少了碰撞次数。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
LinkedHashMap源码分析(基于JDK1.6)
LinkedHashMap类似于HashMap,但是迭代遍历它时,取得“键值对”的顺序是插入次序,或者是最近最少使用(LRU)的次序。只比HashMap慢一点;而在迭代访问时反而更快,因为它使用链表维护内部次序(HashMap是基于散列表实现的,相关HashMap的内容可以看《Java集合类》和《HashMap源码分析》)。
606 0
HashSet及LinkedHashSet源码分析(基于JDK1.6)
Java容器类的用途是“保存对象”,分为两类:Map——存储“键值对”组成的对象;Collection——存储独立元素。Collection又可以分为List和Set两大块。List保持元素的顺序,而Set不能有重复的元素。
751 0
MySQL使用profile分析语句性能消耗
MySQL使用profile分析语句性能消耗 --查看profile是否开启mysql> show variables like '%profil%';+------------------------+-...
760 0
统计分析SQL Server Profiler 跟踪的SQL
--跟踪文件读入到表中分析 SELECT * INTO ZGSJY FROM fn_trace_gettable('E:\wxxcdbprofiler.trc', default); --某时间内,最耗时SQL select TOP 100 SUBSTRING(Textdata,1,660) as '名称', count(*) as '数量', sum(duration/1000) as
735 0
wireshark抓包分析
引用: http://wenku.baidu.com/view/14606f4469eae009581bec75.html
530 0
MongoDB · 特性分析 · Sharded cluster架构原理
为什么需要Sharded cluster? MongoDB目前3大核心优势:『灵活模式』+ 『高可用性』 + 『可扩展性』,通过json文档来实现灵活模式,通过复制集来保证高可用,通过Sharded cluster来保证可扩展性。 当MongoDB复制集遇到下面的业务场景时,你就需要考虑使用Sh
2670 0
+关注
李不言
码农,搬砖的
25
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
OceanBase 入门到实战教程
立即下载
阿里云图数据库GDB,加速开启“图智”未来.ppt
立即下载
实时数仓Hologres技术实战一本通2.0版(下)
立即下载