万万没想到,HashMap默认容量的选择,竟然背后有这么多思考!?

集合是Java开发日常开发中经常会使用到的,而作为一种典型的K-V结构的数据结构,HashMap对于Java开发者一定不陌生。在日常开发中,我们经常会像如下方式以下创建一个HashMap:

Map<String, String> map = new HashMap<String, String>();

但是,大家有没有想过,上面的代码中,我们并没有给HashMap指定容量,那么,这时候一个新创建的HashMap的默认容量是多少呢?为什么呢?本文就来分析下这个问题。

什么是容量

在Java中,保存数据有两种比较简单的数据结构:数组和链表。数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。HashMap就是将数组和链表组合在一起,发挥了两者的优势,我们可以将其理解为链表的数组。

在HashMap中,有两个比较容易混淆的关键字段:size和capacity ,这其中capacity就是Map的容量,而size我们称之为Map中的元素个数。

简单打个比方你就更容易理解了:HashMap就是一个“桶”,那么容量(capacity)就是这个桶当前最多可以装多少元素,而元素个数(size)表示这个桶已经装了多少元素。

如以下代码:

Map<String, String> map = new HashMap<String, String>();

map.put("hollis", "hollischuang");



Class<?> mapType = map.getClass();

Method capacity = mapType.getDeclaredMethod("capacity");

capacity.setAccessible(true);

System.out.println("capacity : " + capacity.invoke(map));



Field size = mapType.getDeclaredField("size");

size.setAccessible(true);

System.out.println("size : " + size.get(map));

输出结果:

capacity : 16、size : 1

上面我们定义了一个新的HashMap,并向其中put了一个元素,然后通过反射的方式打印capacity和size,其容量是16,已经存放的元素个数是1。

通过前面的例子,我们发现了,当我们创建一个HashMap的时候,如果没有指定其容量,那么会得到一个默认容量为16的Map,那么,这个容量是怎么来的呢?又为什么是这个数字呢?

容量与哈希

要想讲清楚这个默认容量的缘由,我们要首先要知道这个容量有什么用?

我们知道,容量就是一个HashMap中”桶”的个数,那么,当我们想要往一个HashMap中put一个元素的时候,需要通过一定的算法计算出应该把他放到哪个桶中,这个过程就叫做哈希(hash),对应的就是HashMap中的hash方法。

我们知道,hash方法的功能是根据Key来定位这个K-V在链表数组中的位置的。也就是hash方法的输入应该是个Object类型的Key,输出应该是个int类型的数组下标。如果让你设计这个方法,你会怎么做?

其实简单,我们只要调用Object对象的hashCode()方法,该方法会返回一个整数,然后用这个数对HashMap的容量进行取模就行了。如果真的是这么简单的话,那HashMap的容量设置就会简单很多了,但是考虑到效率等问题,HashMap的hash方法实现还是有一定的复杂的。

hash的实现

接下来就介绍下HashMap中hash方法的实现原理。(下面部分内容参考自我的文章:全网把Map中的hash()分析的最透彻的文章,别无二家。PS:网上的关于HashMap的hash方法的分析的文章,很多都是在我这篇文章的基础上”衍生”过来的。)

具体实现上,由两个方法int hash(Object k)和int indexFor(int h, int length)来实现。

hash :该方法主要是将Object转换成一个整型。indexFor :该方法主要是将hash生成的整型转换成链表数组中的下标。

为了聚焦本文的重点,我们只来看一下indexFor方法。我们先来看下Java 7(Java8中虽然没有这样一个单独的方法,但是查询下标的算法也是和Java 7一样的)中该实现细节:

static int indexFor(int h, int length) {

    return h & (length-1);

}

indexFor方法其实主要是将hashcode换成链表数组中的下标。其中的两个参数h表示元素的hashcode值,length表示HashMap的容量。那么return h & (length-1) 是什么意思呢?

其实,他就是取模。Java之所有使用位运算(&)来代替取模运算(%),最主要的考虑就是效率。位运算(&)效率要比代替取模运算(%)高很多,主要原因是位运算直接对内存数据进行操作,不需要转成十进制,因此处理速度非常快。

那么,为什么可以使用位运算(&)来实现取模运算(%)呢?这实现的原理如下:

X % 2^n = X & (2^n – 1)

假设n为3,则2^3 = 8,表示成2进制就是1000。2^3 -1 = 7 ,即0111。

此时X & (2^3 – 1) 就相当于取X的2进制的最后三位数。

从2进制角度来看,X / 8相当于 X >> 3,即把X右移3位,此时得到了X / 8的商,而被移掉的部分(后三位),则是X % 8,也就是余数。上面的解释不知道你有没有看懂,没看懂的话其实也没关系,你只需要记住这个技巧就可以了。或者你可以找几个例子试一下。

6 % 8 = 6 ,6 & 7 = 6
10 & 8 = 2 ,10 & 7 = 2

运算过程如下如:

所以,return h & (length-1);只要保证length的长度是2^n 的话,就可以实现取模运算了。

所以,因为位运算直接对内存数据进行操作,不需要转成十进制,所以位运算要比取模运算的效率更高,所以HashMap在计算元素要存放在数组中的index的时候,使用位运算代替了取模运算。之所以可以做等价代替,前提是要求HashMap的容量一定要是2^n 。

那么,既然是2^n ,为啥一定要是16呢?为什么不能是4、8或者32呢?

关于这个默认容量的选择,JDK并没有给出官方解释,笔者也没有在网上找到关于这个任何有价值的资料。(如果哪位有相关的权威资料或者想法,可以留言交流)

根据作者的推断,这应该就是个经验值(Experience Value),既然一定要设置一个默认的2^n 作为初始值,那么就需要在效率和内存使用上做一个权衡。这个值既不能太小,也不能太大。

太小了就有可能频繁发生扩容,影响效率。太大了又浪费空间,不划算。

所以,16就作为一个经验值被采用了。

在JDK 8中,关于默认容量的定义为:static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 ,其故意把16写成1<<4,就是提醒开发者,这个地方要是2的幂。

值得玩味的是:注释中的 aka 16 也是1.8中新增的,那么,接下来我们再来谈谈,HashMap是如何保证其容量一定可以是2^n 的呢?如果用户自己设置了的话又会怎么样呢?

关于这部分,HashMap在两个可能改变其容量的地方都做了兼容处理,分别是指定容量初始化时以及扩容时。

指定容量初始化

当我们通过HashMap(int initialCapacity)设置初始容量的时候,HashMap并不一定会直接采用我们传入的数值,而是经过计算,得到一个新值,目的是提高hash的效率。(1->1、3->4、7->8、9->16)

在JDK 1.7和JDK 1.8中,HashMap初始化这个容量的时机不同。JDK 1.8中,在调用HashMap的构造函数定义HashMap的时候,就会进行容量的设定。而在JDK 1.7中,要等到第一次put操作时才进行这一操作。

看一下JDK是如何找到比传入的指定值大的第一个2的幂的:

int n = cap - 1;

n |= n >>> 1;

n |= n >>> 2;

n |= n >>> 4;

n |= n >>> 8;

n |= n >>> 16;

return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

上面的算法目的挺简单,就是:根据用户传入的容量值(代码中的cap),通过计算,得到第一个比他大的2的幂并返回。

请关注上面的几个例子中,蓝色字体部分的变化情况,或许你会发现些规律。5->8、9->16、19->32、37->64都是主要经过了两个阶段。

Step 1,5->7
Step 2,7->8
Step 1,9->15
Step 2,15->16
Step 1,19->31
Step 2,31->32

对应到以上代码中,Step1:

n |= n >>> 1;

n |= n >>> 2;

n |= n >>> 4;

n |= n >>> 8;

n |= n >>> 16;

对应到以上代码中,Step2:

return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

Step 2 比较简单,就是做一下极限值的判断,然后把Step 1得到的数值+1。

Step 1 怎么理解呢?其实是对一个二进制数依次向右移位,然后与原值取或。其目的对于一个数字的二进制,从第一个不为0的位开始,把后面的所有位都设置成1。

随便拿一个二进制数,套一遍上面的公式就发现其目的了:

1100 1100 1100 >>>1 = 0110 0110 0110

1100 1100 1100 | 0110 0110 0110 = 1110 1110 1110

1110 1110 1110 >>>2 = 0011 1011 1011

1110 1110 1110 | 0011 1011 1011 = 1111 1111 1111

1111 1111 1111 >>>4 = 1111 1111 1111

1111 1111 1111 | 1111 1111 1111 = 1111 1111 1111

通过几次无符号右移和按位或运算,我们把1100 1100 1100转换成了1111 1111 1111 ,再把1111 1111 1111加1,就得到了1 0000 0000 0000,这就是大于1100 1100 1100的第一个2的幂。

好了,我们现在解释清楚了Step 1和Step 2的代码。就是可以把一个数转化成第一个比他自身大的2的幂。但是还有一种特殊情况套用以上公式不行,这些数字就是2的幂自身。如果数字4套用公式的话。得到的会是 8,不过其实这个问题也被解决了,具体验证办法及JDK的解决方案见全网把Map中的hash()分析的最透彻的文章,别无二家。这里就不再展开了。

总之,HashMap根据用户传入的初始化容量,利用无符号右移和按位或运算等方式计算出第一个大于该数的2的幂。

扩容

除了初始化的时候会指定HashMap的容量,在进行扩容的时候,其容量也可能会改变。

HashMap有扩容机制,就是当达到扩容条件时会进行扩容。HashMap的扩容条件就是当HashMap中的元素个数(size)超过临界值(threshold)时就会自动扩容。

在HashMap中,threshold = loadFactor * capacity。

loadFactor是装载因子,表示HashMap满的程度,默认值为0.75f,设置成0.75有一个好处,那就是0.75正好是3/4,而capacity又是2的幂。所以,两个数的乘积都是整数。

对于一个默认的HashMap来说,默认情况下,当其size大于12(16*0.75)时就会触发扩容。

下面是HashMap中的扩容方法(resize)中的一段:

if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

                 oldCap >= DEFAULT_INITIAL_CAPACITY)

    newThr = oldThr << 1; // double threshold

}

从上面代码可以看出,扩容后的table大小变为原来的两倍,这一步执行之后,就会进行扩容后table的调整,这部分非本文重点,省略。

可见,当HashMap中的元素个数(size)超过临界值(threshold)时就会自动扩容,扩容成原容量的2倍,即从16扩容到32、64、128 …

所以,通过保证初始化容量均为2的幂,并且扩容时也是扩容到之前容量的2倍,所以,保证了HashMap的容量永远都是2的幂。

总结

HashMap作为一种数据结构,元素在put的过程中需要进行hash运算,目的是计算出该元素存放在hashMap中的具体位置。

hash运算的过程其实就是对目标元素的Key进行hashcode,再对Map的容量进行取模,而JDK 的工程师为了提升取模的效率,使用位运算代替了取模运算,这就要求Map的容量一定得是2的幂。

而作为默认容量,太大和太小都不合适,所以16就作为一个比较合适的经验值被采用了。

为了保证任何情况下Map的容量都是2的幂,HashMap在两个地方都做了限制。

首先是,如果用户制定了初始容量,那么HashMap会计算出比该数大的第一个2的幂作为初始容量。

另外,在扩容的时候,也是进行成倍的扩容,即4变成8,8变成16。

本文,通过分析为什么HashMap的默认容量是16,我们深入HashMap的原理,分析了下背后的原理,从代码中我们可以发现,JDK 的工程师把各种位运算运用到了极致,想尽各种办法优化效率。值得我们学习!

最后,留一个思考题,既然HashMap并不会直接接收用户传入的初始容量,那么为什么《阿里巴巴Java开发手册》还是建议开发者在创建HashMap的时候制定一个初始容量呢?这个容量设置成多少合适呢?为什么?

关于作者:Hollis,一个对Coding有着独特追求的人,现任阿里巴巴技术专家,个人技术博主,技术文章全网阅读量数千万,《程序员的三门课》联合作者。

来源 l Hollis(ID:hollischuang)

Image placeholder
IT头条
未设置
  83人点赞

没有讨论,发表一下自己的看法吧

推荐文章
长城汽车张小斌:企业数字化不是选择,而是唯一的出路

长城汽车集团云计算总监张小斌20年IT行业经验。西安交通大学计算机专业毕业,中科院计算所硕士,曾在朗讯贝尔实验室、美国硅谷、HP、赛门铁克、Websense担任架构师、主任工程师、研发经理等职务,负责

视频会议新选择,讯众及时会了解下

当下的视频会议市场,各大厂商分庭抗礼,小厂商们伺机突破,入局者越来越多,同质化竞争明显,多数厂商受困于竞争激烈的“红海”,亟需寻求破局之道。这其中,有一家新公司表现较为亮眼,不论是在产品创新还是在标杆

做深度学习这么多年还不会挑GPU?这儿有份选购全攻略

大数据文摘出品来源:timdettmers编译:刘佳玮、钱天培深度学习是一个对算力要求很高的领域。GPU的选择将从根本上决定你的深度学习体验。一个好的GPU可以让你快速获得实践经验,而这些经验是正是建

93.7% 的程序员!竟然都不知道 Redis 为什么默认16个数据库?

▍导读在实际项目中Redis常被应用于做缓存,分布式锁、消息队列等。但是在搭建配置好Redis服务器后很多朋友应该会发现和有这样的疑问,为什么Redis默认建立了16个数据库,如下图所示。椐调查发现:

jquery中有哪几种类型的选择器?

jQuery选择器一、基本选择器基本选择器是jQuery中最常用也是最简单的选择器,它通过元素的id、class和标签名等来查找DOM元素。1、ID选择器#id描述:根据给定的id匹配一个元素,返回单

1000亿文本信息,高并发MD5查询,这么大数据量的业务怎么弄?

==提问== 沈老师,你好,想请教一个身份证信息检索的问题。公司有一个每秒5万并发查询的业务,(假设)根据身份证MD5查询身份证信息,目前有1000亿条数据,纯文本存储,前几天看你写LevelDB,请

如何在 Go 中使用切片容量和长度

来做一个快速测验-以下代码输出什么?vals:=make([]int,5) fori:=0;i

云架构远没想象般安全 派拓网络五大建议助力云安全

当企业业务大量向云端转移,云上安全问题变得愈加严峻,如何保障云端业务的安全成为企业关注的重点问题之一。前不久,网络安全企业PaloAltoNetworks(派拓网络)发布了一份云安全报告,揭示亚太区大

母延年:希望以后提到Lucene除了ES还能想到录信

在搜索领域你可能没有听过“录信”,但是一定听过Lucene。录信数软CTO母延年“‘录信’是‘Lucene’的谐音,我的Lucene发音不太准。”在刚刚过去的SACC2019大会上,录信数软CTO母延

行业目前最大容量,东芝16TB硬盘里藏了哪些技术?

强大的SSD似乎给硬盘(HDD)带来了“毁灭性”的打击,使其淡出存储舞台,但事实并非如此。这种冲击确实存在,不过更多在消费级硬盘市场。对于企业级的数据存储,可以说从现在到未来很长一段时间内,硬盘依旧会

代表性企业级大容量氦气硬盘解析:希捷Exos X14

 海量数据时代,AI、大数据、物联网等技术不止带来了业务应用的转型,还带来了数据的“井喷式”爆发增长。IDC曾预测,2025年全球数据量将高达163ZB。在如此情况下,数据存储成了一个至关重要的问题,

前有堵截,后有追兵,核心技术如何突围?

摘要:真正的强大不是完美,而是能正视自己的不足,认清差距,这样才能有更强的动力砥砺前行。最近,一系列事件包括贸易战、美国公司禁售、技术封锁、修改授权协议等,美国对中国技术堵截之心昭然若揭。另一方面,中

GitHub上十大很火的Python项目,最后一个竟然是它!

课程推荐:Python开发工程师--学习猿地--送9个上线商业项目 作为程序开发人员,GitHub是大家平时必逛的网站,GitHub作为目前全球比较大的男性同性交友平台,上面存在着太多太多的宝藏程序。

笨办法学 Linux Bash:Shell、`.profile`、`.bashrc`、`.bash_history`

Bash:Shell、.profile、.bashrc、.bash_history。 当使用CLI(命令行界面)来使用Linux时,你正在与一个名为shell的程序进行交互。所有你输入的都传递给she

Bash技巧:使用参数扩展获取变量的子字符串和字符串长度

在bash中,通常使用${parameter}表达式来获取parameter变量的值,这是一种参数扩展(parameterexpansion)。Bash还提供了其他形式的参数扩展,可以对变量值做一些处

阿里云小蜜对话机器人背后的核心算法

0.对话系统简介 对话系统的一般架构如图: 图1:对话系统一般架构 这是我们所熟知的对话系统框架,这里面主要有:NLU自然语言理解,DM对话管理,NLG自然语言生成3个主要模块,DM里面有dialo

AI 计算竞争升级,参访平安科技背后的硬实力

平安科技的四块科技版图,分别是云、认知、区块链和人工智能。所有的AI公司在AI领域中最核心的壁垒不是技术,因为技术都是人创造的,打磨团队就可以。核心的壁垒应该时间、业务和场景。智能科技的涌现、大数据

pymysql fetchone () , fetchall () , fetchmany ()

最近在用python操作mysql数据库时,碰到了下面这两个函数,标记一下: 1.定义 1.1fetchone(): 返回单个的元组,也就是一条记录(row),如果没有结果则返回None 1.2fet

从 simplemde 写入 + inline-attachment 图片拖拽上传 到 parsedown 解析

###准备工作安装富文本编辑器sparksuite/simplemde-markdown-editor yarnaddsimplemde--save 安装markedjs/marked,在JS中解析

揭秘华新水泥核心业务上云的背后故事

武汉地处九省通衢之地,“敢为人先,追求卓越”的武汉精神,引领着武汉在科技“攻尖”与产业“攻坚”方面硕果连连。近日,“武汉·选择不凡华为云城市峰会2019”成功举办,华为云与湖北政企客户及伙伴共同探讨“

TPC-C解析系列01_TPC-C benchmark测试介绍

作者:阳振坤2019.10导语:自从蚂蚁金服自研数据库OceanBase获得TPC-C测试第一名后,引起了行业内外大量关注,我们衷心的感谢大家对OceanBase的支持与厚爱,也虚心听取外界的意见和建

腾讯财报背后的小秘密:转型路上的未知

8月14日,腾讯发布第二季度财报,不凑巧的是,当日欧市盘中,美国2年期与10年期国债利率发生2007年来首次倒挂,引起市场对经济衰退的恐慌,美股三大指数均暴跌3%。8月15日,中国香港恒生指数低开1.

从跟随者到开拓者,阿里云数据库角色变化背后的机遇与挑战

数据库经过40多年的发展与变迁已经改写了格局,在开源、云端浪潮之下曾经的数据库霸主Oracle也已经跌下王座,不断向着云与智能化发展,新的厂商也获得了各自机会,在云数据库时代是一个百花齐放、百家争鸣的

欧洲最大笔融资,骗过软银!印度AI公司被曝造假,自动开发背后是真人码农

大数据文摘编辑部出品AI融资有泡沫,这大家都知道。但是,这泡沫能有多大呢?一家名叫Engineer.ai的明星AI初创公司刚刚刷新了这一纪录。这家以ai作为域名的公司由两名印度创始人创建,号称可以通过

“小应用”背后的“大改变” 爱奇艺赋能流媒体播放服务

热门视频里,“弹幕盖脸”几乎是必然事件,然而有一个地方看视频,你会发现密密麻麻的弹幕都绕开主角飘过,这个地方就是爱奇艺。对于大家观看视频时喜闻乐见的弹幕,爱奇艺提供了蒙版弹幕服务,可以让用户实现“弹幕