HashMap容量分析

Stella981
• 阅读 802

了解过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中存放元素数组的大小,可以避免求余操作,效率较高,同时,减少了碰撞次数。

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Wesley13 Wesley13
3年前
java将前端的json数组字符串转换为列表
记录下在前端通过ajax提交了一个json数组的字符串,在后端如何转换为列表。前端数据转化与请求varcontracts{id:'1',name:'yanggb合同1'},{id:'2',name:'yanggb合同2'},{id:'3',name:'yang
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Stella981 Stella981
3年前
JS 对象数组Array 根据对象object key的值排序sort,很风骚哦
有个js对象数组varary\{id:1,name:"b"},{id:2,name:"b"}\需求是根据name或者id的值来排序,这里有个风骚的函数函数定义:function keysrt(key,desc) {  return function(a,b){    return desc ? ~~(ak
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
3年前
HashMap 的底层实现原理
HashMap是一个用于存储KeyValue键值对的集合,每一个键值对也叫做Entry。这些个Entry分散存储在一个数组当中,这个数组就是HashMap的主干。HashMap数组每一个元素的初始值都是Null。 !(https://oscimg.oschina.net/oscnet/8495d30fe00a2865dd74088d2
Wesley13 Wesley13
3年前
35岁是技术人的天花板吗?
35岁是技术人的天花板吗?我非常不认同“35岁现象”,人类没有那么脆弱,人类的智力不会说是35岁之后就停止发展,更不是说35岁之后就没有机会了。马云35岁还在教书,任正非35岁还在工厂上班。为什么技术人员到35岁就应该退役了呢?所以35岁根本就不是一个问题,我今年已经37岁了,我发现我才刚刚找到自己的节奏,刚刚上路。
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
10个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这