【优雅的避坑】new HashMap(list.size())指定size就能完全避免扩容带来的额外开销了吗? 这本出自华为18级工程师之手的多线程高并发文档绝对值得你一看 SpringBoot-web开发(四): SpringMVC的拓展、接管(源码分析) 硅谷大数据独角兽Palantir登陆纽交所 上市首日收涨逾30% 发力智能边缘 英特尔从技术创新和生态协作两个维度掘金工业物联网 大数据提前说:黄金周旅游有些区域热度暴增475% 大数据为煤矿工人健康保驾护航 瑞萨电子:物联网给MCU带来新风口 物联网创新创业大赛长三角赛区复赛落幕 教育培训行业预付费资金划入银行监管账户 朝阳区建立首个预付费监管平台 “区块链+大数据+云计算”分场景监管预付费 华为与南网电动联合发布《智慧充电桩物联网技术白皮书》 安阳航空运动文化旅游节|专访中国联通研究院物联网终端技术研究室主任王湘宁 NRF52832学习笔记(28)——一主多从连接 学习笔记 #pragma GCC diagnostic ignored “-Wformat“ 的使用 各种缩写名词汇总,力求最全面最精确 LLAPNDK_DOUBLE声波发送代码分析 一篇文章搞定嵌入式看门狗watch dog概述与示例代码 热爱大数据的乘客请上车,一起追逐工业之光 | Q推荐 UniswapV2核心合约学习(1)— UniswapV2Factory.sol 花火交易所系统开发搭建 3GPP R16中与车联网、PC5、V2X、直连通信相关的协议汇总 【转】整整30天终于走完,分享下我的昆山人才引进落户经历 聊一下《技术力量-一线技术团队成功启示录》 小胡的第一篇Blog 云队友丨在注意力稀缺的时代,专注是你成败的关键筹码 离开华为换种生活,它不香吗? 架构制图:工具与方法论 如何在1分钟内CSDN收益1000万,走上人生巅峰?! 109亿!华为成都人工智能大数据中心落户成都 北京国际大数据交易所设立工作实施方案中多次提及区块链 金色财经 英特尔发布物联网增强处理器产品 首次安装Linux,配置网络、换源一步到位 Maxwell采集binlog系列(一)-Linux系统安装JDK Java架构师之路:Java程序员必看的10本书的电子版 Java面试凉经总结篇:和大家聊聊我是怎么没的? BATJ大厂高频面试题!TCP/IP三次握手四次挥手、高并发终于被他通过画图讲清楚了,搞懂这个,年薪50w! 阿里P8级架构师老毕呕心沥血熬夜一个星期又又又又又出新分享SpringBoot文档 nginx之安装第三方模块及平滑升级 步步为营!蚂蚁金服的六轮面试我是怎么撑过来的?(Java岗)已拿股票期权! NLP顶会论文写作技巧个人总结! 时间戳 2020-09-21转Tue Sep 29 2020 08:00:00 GMT+0800 (中国标准时间) Vue条件和循环语句 又是没有专业技术的一篇嘿嘿! html+css原生动画魔方小例子 width和height的默认值auto与%详解(附案例)。 JavaScript运算符类型及用法 58同城大数据剖析制造业求偏好:90后求职者占比20%以上,男性求职者占比60%以上 东软教育(09616.HK):IT好风频借力,程序员高教第一股扬帆起航,给予“买入”评级,目标价7.92港元 拟与人工智能研究院在物联网等领域展开合作 *ST同洲连续两日涨停 树米科技完成A+轮融资“物联网”赛道受资本热捧
您的位置:首页 >大数据 >

【优雅的避坑】new HashMap(list.size())指定size就能完全避免扩容带来的额外开销了吗?

设置HashMap的初始容量

设置HashMap的初始容量只是优化的开始。

HashMap在Java的使用中占据着很重要的地位,平时使用的时候,相信很多Java程序员都知道在定义HashMap的时候,给它设置一个初始容量,以便减少hashMap扩容(resize)带来的额外开销,比如像我同(zi)事(ji)的这段代码:

@Testpublic void longLongAGo() {int count = 1000000;System.out.println("---------------- 不设置hashMap初始容量 ------------");long start = System.currentTimeMillis();HashMap<Integer, Object> map = new HashMap<>();for (int i = 0; i < count; i++) {map.put(i, UUID.randomUUID());}long end = System.currentTimeMillis();System.out.println("添加1000000个元素耗时:" + (end - start));System.out.println("---------------- 设置hashMap初始容量 -------------------");long start1 = System.currentTimeMillis();HashMap<Integer, Object> map1 = new HashMap<>(count);for (int i = 0; i < count; i++) {map1.put(i, UUID.randomUUID());}long end1 = System.currentTimeMillis();System.out.println("添加1000000个元素耗时:" + (end1 - start1));}复制代码

 

 

 

我同事说他在初始化的时候设定了map的容量,不会在添加元素的过程中进行自动扩容了,大大提高了性能,从结果看确实如此!

所以,集合初始化时,指定集合初始值大小能提升性能。

然鹅,我抱着怀疑的态度,对比了设置初始容量和不设置初始容量时,hashMap的扩容次数,当设置初始容量为1000000时,容器并不是想象中的不扩容了,而是也扩容了1次:

@SneakyThrows@Testpublic void testing() {int count = 1000000;System.out.println("---------------- 初始化hashMap容量为1000000 ------------");int resizeCount = 0;HashMap<Integer, Object> map = new HashMap<>(count);Method capacityMethod = map.getClass().getDeclaredMethod("capacity");capacityMethod.setAccessible(true);int capacity = (int) capacityMethod.invoke(map);System.out.println("初始容量:" + capacity);for (int i = 0; i < count; i++) {map.put(i, UUID.randomUUID());int curCapacity = (int) capacityMethod.invoke(map);if (curCapacity > capacity) {System.out.println("当前容量:" + curCapacity);resizeCount++;capacity = curCapacity;}}System.out.println("hashMap扩容次数:" + resizeCount);System.out.println("---------------- 不初始化hashMap容量 -------------------");resizeCount = 0;HashMap<Integer, Object> map1 = new HashMap<>();Method capacityMethod1 = map1.getClass().getDeclaredMethod("capacity");capacityMethod1.setAccessible(true);int capacity1 = (int) capacityMethod1.invoke(map1);System.out.println("初始容量:" + capacity1);for (int i = 0; i < count; i++) {map1.put(i, UUID.randomUUID());int curCapacity = (int) capacityMethod1.invoke(map1);if (curCapacity > capacity1) {System.out.println("当前容量:" + curCapacity);resizeCount++;capacity1 = curCapacity;}}System.out.println("扩容次数:" + resizeCount);}复制代码

由于我们无法直接调用hashMap的capacity()方法,因此使用反射来查看每添加一个元素,它的容量变化,以此来监测hashMap的扩容次数。

//使用反射,调用hashMap的capacity()方法Method capacityMethod = map.getClass().getDeclaredMethod("capacity");capacityMethod.setAccessible(true);int capacity = (int) capacityMethod.invoke(map);复制代码

关于反射,欢迎阅读 Java最强大的技术之一:反射 ,可以对反射机制有个大致的了解。

差点跑偏了,现在回到上面程序的执行结果:

---------------- 初始化hashMap容量为1000000 ------------初始容量:1048576当前容量:2097152hashMap扩容次数:1---------------- 不初始化hashMap容量 -------------------初始容量:16当前容量:32当前容量:64当前容量:128当前容量:256当前容量:512当前容量:1024当前容量:2048当前容量:4096当前容量:8192当前容量:16384当前容量:32768当前容量:65536当前容量:131072当前容量:262144当前容量:524288当前容量:1048576当前容量:2097152扩容次数:17复制代码

通过运行结果发现:

设置了初始容量的hashMap,其初始容量并不是我指定的1000000,而是1048576(2^20)hashMap的容量并不是固定不变的,当达到扩容条件时会进行扩容,从 16 扩容到 32、64、128…(Hash 会选择大于当前容量的第一个 2 的幂作为容量)即使制定了初始容量,而且初始容量是1048576,当添加1000000个元素(1000000是小于1048576)时,hashMap依然会扩容1次

为什么会酱紫呢?带着上面的三个发现,来看一下HashMap的扩容机制。

HashMap的扩容机制

先看一下HashMap的几个成员变量:

 

HashMap成员变量

 

 

DEFAULT_INITIAL_CAPACITY:默认初始容量是2^4=16DEFAULT_LOAD_FACTOR:默认的装载系数是0.75,是用来衡量HashMap的容量满的程度的transient int size:map中k,v对的数目final float loadFactor:装载系数,默认值为0.75int threshold:调整大小的下一个大小值(容量 × 装载系数)。当实际 k,v 个数超过 threshold 时,HashMap 会将容量扩容

再来看一个方法capacity()

final int capacity() {return (table != null) ? table.length :(threshold > 0) ? threshold :DEFAULT_INITIAL_CAPACITY;}复制代码

这是啥?前面不是已经定义了一个size变量了吗?

可以把capacity看成是HashMap这个桶的体积(这个体积是可以变大的),而size是这个桶当前装了多少东西。

桶的容量是由threshold定义的,而且默认容量是2的4次幂,也就是16,源码上是这样写的:

/** * The default initial capacity - MUST be a power of two. */static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16复制代码

 

 

 

1 << 4就是左移4位的意思,也就是2^4=16。

那么什么时候扩容呢?这个很容易就能够想到,我们向hashMap这个桶里put数据,当桶的k,v对的数目size快填满桶-逼近capacity时,这个桶将要扩容!

前面的例子已经展示了,hashMap并不是等size到了capacity才扩容,而是在到达capacity的某个值时就扩容了,这个值就是threshold的时候,hashMap进行resize(),而这个,来看源码:

 

HashMap扩容点源码

 

 

部分源码已折叠,主要展示和容量有关的部分。

size增长到大于threshold的时候,hashMap进行resize(),而threshold = loadFactor * capacity,这样就可以知道hashMap这个桶在什么时候自动扩大它的体积了。

真正的避免HashMap扩容

前面分析到,当size > threshold的时候,hashMap进行扩容,利用threshold = loadFactor * capacity这个公式,我们在初始化的时候就有方向了。

首先肯定不能直接设置成loadFactor * capacity,因为这个数有可能不是2的幂,HashMap规定的容器容量必须是2的幂,既然如此,我设置成大于loadFactor * capacity的第一个2的幂的数就行了,可以这样做:

int initCapacity = 1 + (int) (count / 0.75);HashMap<Integer, Object> map = new HashMap<>(initCapacity);复制代码

1 + (int) (count / 0.75)这个公式来源于HashMap源码:

/** * Returns a power of two size for the given target capacity. */static final int tableSizeFor(int cap) {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 的幂并返回。

这些都是二进制的位操作,将数依次向右移位,然后和原值取或。可以随便找一个数代入代码中验证,结果就是第一个比它大的2的幂!

为什么这样做,或许就是因为 无符号右移 >>> 、或运算 | 就是快吧!

 

 

 

结果验证

计算容量的公式前面已经搞出来了,现在验证一下对不对:

@SneakyThrows@Testpublic void perfect() {int count = 1000000;int initCapacity = 1 + (int) (count / 0.75);HashMap<Integer, Object> map = new HashMap<>(initCapacity);Method capacityMethod = map.getClass().getDeclaredMethod("capacity");capacityMethod.setAccessible(true);int capacity = (int) capacityMethod.invoke(map);System.out.println("jdk hashMap default capacity:" + capacity);int resizeCount = 0;for (int i = 0; i < count; i++) {map.put(i, UUID.randomUUID());int curCapacity = (int) capacityMethod.invoke(map);if (curCapacity > capacity) {System.out.println("当前容量:" + curCapacity);resizeCount++;capacity = curCapacity;}}System.out.println("hashMap扩容次数:" + resizeCount);复制代码

运行结果:

 

 

 

扩容次数为0,perfect!

把initCapacity=1333334这个数代入到HashMap的tableSizeFor方法就能算出容量为2097152=2^21了!

不想计算初始化容量-仍有他途

Guava是一种基于开源的Java库,其中包含谷歌正在由他们很多项目使用的很多核心库。这个库是为了方便编码,并减少编码错误。这个库提供用于集合,缓存,支持原语,并发性,常见注解,字符串处理,I/O和验证的实用方法。

Guava中有现成的初始化HashMap的方法,它不用我们计算initCapacity,测试一把看看。

先引入Guava包:

<dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId><version>29.0-jre</version></dependency>复制代码

测试:

@SneakyThrows@Testpublic void perfectWithGuava() {int count = 1000000;HashMap<Integer, Object> map = Maps.newHashMapWithExpectedSize(count);Method capacityMethod = map.getClass().getDeclaredMethod("capacity");capacityMethod.setAccessible(true);int capacity = (int) capacityMethod.invoke(map);System.out.println("guava hashMap default capacity:" + capacity);int resizeCount = 0;for (int i = 0; i < count; i++) {map.put(i, UUID.randomUUID());int curCapacity = (int) capacityMethod.invoke(map);if (curCapacity > capacity) {System.out.println("当前容量:" + curCapacity);resizeCount++;capacity = curCapacity;}}System.out.println("hashMap扩容次数:" + resizeCount);}复制代码

运行结果:

 

 

 

同样能使HashMap不用扩容!

瞅一下关键代码:

... = Maps.newHashMapWithExpectedSize(count);

我猜这个newHashMapWithExpectedSize(int)的源码中肯定也是按照类似于HashMap的return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;这种方法计算的,来看一下:

 

Guava Maps源码

 

 

恭喜你,都能猜对了!

小结

设置了初始容量的hashMap,其真实初始容量并不一定是指定的数值,而是HashMap内部计算过的hashMap的容量并不是固定不变的,当达到扩容条件时会进行扩容,从 16 扩容到 32、64、128…(Hash 会选择大于当前容量的第一个 2 的幂作为容量)不要以为指定了初始容量,hashMap就不扩容了避免hashMap扩容的方法是传入一个1 + (int) (count / 0.75)计算出的初始值还可以使用Guava的newHashMapWithExpectedSize(int count)

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。