您当前的位置:首页 > 电脑百科 > 程序开发 > 编程百科

HashMap初始容量总结,彻底吃透位运算,简历立马多项熟练

时间:2021-04-06 11:45:52  来源:今日头条  作者:java分享者

 

场景描述

我们在日常学习和研发中,经常会接触一些底层的源码,有些同学在遇到位运算(提高系统的运行效率)实现的方法时,读起来就有些吃力了,例如HashMap类中的tableSizeFor(int cap)方法,源代码如下。

/**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;
    /**
     * 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;
    }

当我们使用HashMap集合没有指定初始容量时默认是16,如果给定了一个初始容量,tableSizeFor(int cap)方法会返回一个等于2的n次方的数来作为集合的初始容量。如果用户给定的初始容量就等于2的n次方,那么返回的这个数就等于用户给定值,否则将会返回一个大于且最接近用户给定值的2的n次方的数来作为HashMap集合的初始容量。

案例演示

为了演示效果我这里使用反射的方式直接调用HashMap类里的tableSizeFor(int cap)方法测试容量的返回值。有对反射不是很理解的同学可以将源码复制出来测试也可以在这个方法上添加断点debug调试。

代码示例

假设用户给定初始容量 cap=7

import JAVA.lang.reflect.Method;
public class Demo {
    public static void main(String[] args) throws Exception {
        Class aClass = Class.forName("java.util.HashMap");
        Object instance = aClass.newInstance();
        Method tableSizeFor = aClass.getDeclaredMethod("tableSizeFor", int.class);
        //设置目标类中的tableSizeFor方法可访问
        tableSizeFor.setAccessible(true);
        //假设用户给定的初始值时cap=7
        Object invoke = tableSizeFor.invoke(instance, 7);
        //打印返回值
        System.out.println("tableSizeFor方法返回值:"+invoke);
    }
}

运行结果

F:softwareJavajdk1.8.0_121binjava.exe "-javaagent:D:IntelliJ IDEA 2019.1.4libidea_rt.jar=51583:D:IntelliJ IDEA 2019.1.4bin" -Dfile.encoding=UTF-8 -classpath F:softwareJavajdk1.8.0_121jrelibcharsets.jar;F:softwareJavajdk1.8.0_121jrelibdeploy.jar;F:softwareJavajdk1.8.0_121jrelibextaccess-bridge-64.jar;F:softwareJavajdk1.8.0_121jrelibextcldrdata.jar;F:softwareJavajdk1.8.0_121jrelibextDNSns.jar;F:softwareJavajdk1.8.0_121jrelibextjaccess.jar;F:softwareJavajdk1.8.0_121jrelibextjfxrt.jar;F:softwareJavajdk1.8.0_121jrelibextlocaledata.jar;F:softwareJavajdk1.8.0_121jrelibextnashorn.jar;F:softwareJavajdk1.8.0_121jrelibextsunec.jar;F:softwareJavajdk1.8.0_121jrelibextsunjce_provider.jar;F:softwareJavajdk1.8.0_121jrelibextsunmscapi.jar;F:softwareJavajdk1.8.0_121jrelibextsunpkcs11.jar;F:softwareJavajdk1.8.0_121jrelibextzipfs.jar;F:softwareJavajdk1.8.0_121jrelibjavaws.jar;F:softwareJavajdk1.8.0_121jrelibjce.jar;F:softwareJavajdk1.8.0_121jrelibjfr.jar;F:softwareJavajdk1.8.0_121jrelibjfxswt.jar;F:softwareJavajdk1.8.0_121jrelibjsse.jar;F:softwareJavajdk1.8.0_121jrelibmanagement-agent.jar;F:softwareJavajdk1.8.0_121jrelibplugin.jar;F:softwareJavajdk1.8.0_121jrelibresources.jar;F:softwareJavajdk1.8.0_121jrelibrt.jar;D:ideastudyspacespring_studyspring-studyspring-study-proxytargetclasses;E:softwareMavenRepositoryorgspringframeworkspring-webmvc3.2.0.RELEASEspring-webmvc-3.2.0.RELEASE.jar;E:softwareMavenRepositoryorgspringframeworkspring-context3.2.0.RELEASEspring-context-3.2.0.RELEASE.jar;E:softwareMavenRepositoryorgspringframeworkspring-aop3.2.0.RELEASEspring-aop-3.2.0.RELEASE.jar;E:softwareMavenRepositoryorgspringframeworkspring-core3.2.0.RELEASEspring-core-3.2.0.RELEASE.jar;E:softwareMavenRepositorycommons-loggingcommons-logging1.1.1commons-logging-1.1.1.jar;E:softwareMavenRepositoryorgspringframeworkspring-web3.2.0.RELEASEspring-web-3.2.0.RELEASE.jar;E:softwareMavenRepositoryaopallianceaopalliance1.0aopalliance-1.0.jar;E:softwareMavenRepositoryorgspringframeworkspring-expression3.2.0.RELEASEspring-expression-3.2.0.RELEASE.jar;E:softwareMavenRepositoryorgspringframeworkspring-beans3.2.0.RELEASEspring-beans-3.2.0.RELEASE.jar;E:softwareMavenRepositorycomalibabafastjson1.2.47fastjson-1.2.47.jar com.shiguang.service.Demo
tableSizeFor方法返回值:8
Process finished with exit code 0

此时我们设置初始容量cap=9

import java.lang.reflect.Method;
public class Demo {
    public static void main(String[] args) throws Exception {
        Class aClass = Class.forName("java.util.HashMap");
        Object instance = aClass.newInstance();
        Method tableSizeFor = aClass.getDeclaredMethod("tableSizeFor", int.class);
        //设置目标类中的tableSizeFor方法可访问
        tableSizeFor.setAccessible(true);
        //将初始值时变更为cap=9
        Object invoke = tableSizeFor.invoke(instance, 9);
        //打印返回值
        System.out.println("tableSizeFor方法返回值:"+invoke);
    }
}

运行结果

F:softwareJavajdk1.8.0_121binjava.exe "-javaagent:D:IntelliJ IDEA 2019.1.4libidea_rt.jar=51640:D:IntelliJ IDEA 2019.1.4bin" -Dfile.encoding=UTF-8 -classpath F:softwareJavajdk1.8.0_121jrelibcharsets.jar;F:softwareJavajdk1.8.0_121jrelibdeploy.jar;F:softwareJavajdk1.8.0_121jrelibextaccess-bridge-64.jar;F:softwareJavajdk1.8.0_121jrelibextcldrdata.jar;F:softwareJavajdk1.8.0_121jrelibextdnsns.jar;F:softwareJavajdk1.8.0_121jrelibextjaccess.jar;F:softwareJavajdk1.8.0_121jrelibextjfxrt.jar;F:softwareJavajdk1.8.0_121jrelibextlocaledata.jar;F:softwareJavajdk1.8.0_121jrelibextnashorn.jar;F:softwareJavajdk1.8.0_121jrelibextsunec.jar;F:softwareJavajdk1.8.0_121jrelibextsunjce_provider.jar;F:softwareJavajdk1.8.0_121jrelibextsunmscapi.jar;F:softwareJavajdk1.8.0_121jrelibextsunpkcs11.jar;F:softwareJavajdk1.8.0_121jrelibextzipfs.jar;F:softwareJavajdk1.8.0_121jrelibjavaws.jar;F:softwareJavajdk1.8.0_121jrelibjce.jar;F:softwareJavajdk1.8.0_121jrelibjfr.jar;F:softwareJavajdk1.8.0_121jrelibjfxswt.jar;F:softwareJavajdk1.8.0_121jrelibjsse.jar;F:softwareJavajdk1.8.0_121jrelibmanagement-agent.jar;F:softwareJavajdk1.8.0_121jrelibplugin.jar;F:softwareJavajdk1.8.0_121jrelibresources.jar;F:softwareJavajdk1.8.0_121jrelibrt.jar;D:ideastudyspacespring_studyspring-studyspring-study-proxytargetclasses;E:softwareMavenRepositoryorgspringframeworkspring-webmvc3.2.0.RELEASEspring-webmvc-3.2.0.RELEASE.jar;E:softwareMavenRepositoryorgspringframeworkspring-context3.2.0.RELEASEspring-context-3.2.0.RELEASE.jar;E:softwareMavenRepositoryorgspringframeworkspring-aop3.2.0.RELEASEspring-aop-3.2.0.RELEASE.jar;E:softwareMavenRepositoryorgspringframeworkspring-core3.2.0.RELEASEspring-core-3.2.0.RELEASE.jar;E:softwareMavenRepositorycommons-loggingcommons-logging1.1.1commons-logging-1.1.1.jar;E:softwareMavenRepositoryorgspringframeworkspring-web3.2.0.RELEASEspring-web-3.2.0.RELEASE.jar;E:softwareMavenRepositoryaopallianceaopalliance1.0aopalliance-1.0.jar;E:softwareMavenRepositoryorgspringframeworkspring-expression3.2.0.RELEASEspring-expression-3.2.0.RELEASE.jar;E:softwareMavenRepositoryorgspringframeworkspring-beans3.2.0.RELEASEspring-beans-3.2.0.RELEASE.jar;E:softwareMavenRepositorycomalibabafastjson1.2.47fastjson-1.2.47.jar com.shiguang.service.Demo
tableSizeFor方法返回值:16
Process finished with exit code 0

这个时候返回的是16,2的4次方,也是大于且最接近9的2的n次方的数。那么tableSizeFor(int cap)方法是如何实现这个功能的呢?

代码分析

首先我们先理解三个位运算符
“|” 或运算
举例:
0001
0010
------------------或运算(对应二进制位同是0时等于0,只要有1等于1)
0011
“|=” 或等于
举例:a |= b 就相当于 a = a | b
">>>" 无符号右移
举例:1001 >>> 2
1001
---------- 1001无符号右移2位
0010 01

了解以上位运算符,我们便可以轻松明白这个方法的原理了

用户指定HashMap初始数组容量 cap=9,进入tableSizeFor(int cap)方法
     1 [执行代码]:int n = cap - 1; n=8[最后我们再解释为什么这里要cap-1]
     2 [执行代码]: n |= n >>> 1;
       首先计算n >>> 1
       ------------------------------------------------------
         二进制         十进制           描述
       ------------------------------------------------------
       0000 1000         8            初始值
       ----------------------n >>> 1
       0000 0100~~0~~    4             结果
       接着计算 n|n >>> 1
       0000 1000         8
       0000 0100         4
       -------------------------------或运算
       0000 1100         12            结果
     3 [执行代码]: n |= n >>> 2;[注意]此时的n=0000 1100
       首先计算n >>> 2
       0000 1100         12
       -------------------------n >>> 2
       0000 0011~~00~~    3            结果
       接着计算 n|n >>> 2
       0000 1100         12
       0000 0011          3
       --------------------------------或运算
       0000 1111         15             结果
     4 [执行代码]: n |= n >>> 4;[注意]此时的n=0000 1111
       首先计算 n >>> 4
       0000 1111         15			   
       -------------------------n >>> 4
       0000 0000~~1111~~  0		        结果
       
       接着计算 n|n >>> 4
       0000 1111		 15
       0000 0000		  0
       --------------------------------或运算
       0000 1111         15
     5 [执行代码]: n |= n >>> 8;
       0000 1111         15             结果
     6 [执行代码]: n |= n >>> 16;
       0000 1111         15             结果
     ----------------------------------------------------
     我们不难发现规律
       start 0000 1000
       end   0000 1111
     初始值经过两轮[无符号右移]加[或运算]后已将最高二进制位上的1后面的所有二进制位都变成了1
     我们知道int类型占4个字节,也就是32位, 这样任意一个int类型的数进来经过这5轮[无符号右移]加[或运算],最高二进制位上的1后面的所有二进制位都会变成1
     接着我们执行这个方法的最后一行代码
     return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
     显然此时我们的n=15,在[0,MAXIMUM_CAPACITY]这个区间内,所以
     return n + 1;
     系统设置HashMap集合的初始容量 cap=16;

那int n = cap - 1这行代码又有什么用呢?
显然这行代码是为了防止用户给定的初始值就等于2的n次方,如果用户给定值是8,而tableSizeFor(int cap)方法里没有cap - 1这行代码,那么方法的返回值就变成了16,这样就造成了不必要的内存浪费 。



Tags:HashMap   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
1、HashMap主要成员变量size 记录了 Map 中 KV 对的个数。loadFactor 装载印子,用来衡量 HashMap 满的程度。loadFactor 的默认值为 0.75f。threshold 临界值,当实际 KV 个数...【详细内容】
2021-06-08  Tags: HashMap  点击:(152)  评论:(0)  加入收藏
场景描述我们在日常学习和研发中,经常会接触一些底层的源码,有些同学在遇到位运算(提高系统的运行效率)实现的方法时,读起来就有些吃力了,例如HashMap类中的tableSizeFor(int cap...【详细内容】
2021-04-06  Tags: HashMap  点击:(247)  评论:(0)  加入收藏
前言本文咱们了解一下红黑树的设计,相比 jdk1.7 的 HashMap 而言,jdk1.8 最重要的就是引入了红黑树的设计,当冲突的链表长度超过 8 个的时候,链表结构就会转为红黑树结构。01、...【详细内容】
2021-01-18  Tags: HashMap  点击:(173)  评论:(0)  加入收藏
本节让我们一起研究一下该容器是如何在保证线程安全的同时又能保证高效的操作。 ConcurrentHashMap 是线程安全且高效的 HashMap 。...【详细内容】
2020-10-16  Tags: HashMap  点击:(79)  评论:(0)  加入收藏
絮叨学校短学期刚结束了,离学校开学还有很多天,一直呆在寝室玩游戏岂不是浪费了大好时光,于是心血来潮想看看HashMap的源码。虽然我没有经历过面试,但是java程序员都知道,HashMap...【详细内容】
2020-09-27  Tags: HashMap  点击:(59)  评论:(0)  加入收藏
一、前言得益于Doug Lea老爷子的操刀,让HashMap成为使用和面试最频繁的API,没办法设计的太优秀了!HashMap 最早出现在 JDK 1.2中,底层基于散列算法实现。HashMap 允许 null 键和...【详细内容】
2020-08-11  Tags: HashMap  点击:(46)  评论:(0)  加入收藏
TL:DR他们将键映射到值。哈希映射可能是映射概念最常用的实现。 它们允许将任意对象与其他任意对象关联。这对于执行诸如通过某些公共属性将数据分组或连接在一起之类的工作...【详细内容】
2020-07-19  Tags: HashMap  点击:(69)  评论:(0)  加入收藏
jdk1.7中的底层实现过程(底层基于数组+链表)在我们new HashMap()时,底层创建了默认长度为16的一维数组Entry[ ] table。当我们调用map.put(key1,value1)方法向HashMap里添加数...【详细内容】
2020-06-28  Tags: HashMap  点击:(40)  评论:(0)  加入收藏
通过Map.values()遍历所有的value,不能遍历key public class TestDemo{ public static void main(String[] args) { HashMap<String,String> hashMap = new Has...【详细内容】
2020-03-08  Tags: HashMap  点击:(47)  评论:(0)  加入收藏
HashMap是数组+链表实现的,既然用到hash散列,那么肯定不可避免的会出现冲突问题,HashMap解决冲突的方法是拉链法,因为这里有用到数组,那么当容量不足的时候就需要进行扩容操作了...【详细内容】
2019-10-24  Tags: HashMap  点击:(116)  评论:(0)  加入收藏
▌简易百科推荐
摘 要 (OF作品展示)OF之前介绍了用python实现数据可视化、数据分析及一些小项目,但基本都是后端的知识。想要做一个好看的可视化大屏,我们还要学一些前端的知识(vue),网上有很多比...【详细内容】
2021-12-27  项目与数据管理    Tags:Vue   点击:(1)  评论:(0)  加入收藏
程序是如何被执行的&emsp;&emsp;程序是如何被执行的?许多开发者可能也没法回答这个问题,大多数人更注重的是如何编写程序,却不会太注意编写好的程序是如何被运行,这并不是一个好...【详细内容】
2021-12-23  IT学习日记    Tags:程序   点击:(9)  评论:(0)  加入收藏
阅读收获✔️1. 了解单点登录实现原理✔️2. 掌握快速使用xxl-sso接入单点登录功能一、早期的多系统登录解决方案 单系统登录解决方案的核心是cookie,cookie携带会话id在浏览器...【详细内容】
2021-12-23  程序yuan    Tags:单点登录(   点击:(8)  评论:(0)  加入收藏
下载Eclipse RCP IDE如果你电脑上还没有安装Eclipse,那么请到这里下载对应版本的软件进行安装。具体的安装步骤就不在这赘述了。创建第一个标准Eclipse RCP应用(总共分为六步)1...【详细内容】
2021-12-22  阿福ChrisYuan    Tags:RCP应用   点击:(7)  评论:(0)  加入收藏
今天想简单聊一聊 Token 的 Value Capture,就是币的价值问题。首先说明啊,这个话题包含的内容非常之光,Token 的经济学设计也可以包含诸多问题,所以几乎不可能把这个问题说的清...【详细内容】
2021-12-21  唐少华TSH    Tags:Token   点击:(9)  评论:(0)  加入收藏
实现效果:假如有10条数据,分组展示,默认在当前页面展示4个,点击换一批,从第5个开始继续展示,到最后一组,再重新返回到第一组 data() { return { qList: [], //处理后...【详细内容】
2021-12-17  Mason程    Tags:VUE   点击:(14)  评论:(0)  加入收藏
什么是性能调优?(what) 为什么需要性能调优?(why) 什么时候需要性能调优?(when) 什么地方需要性能调优?(where) 什么时候来进行性能调优?(who) 怎么样进行性能调优?(How) 硬件配...【详细内容】
2021-12-16  软件测试小p    Tags:性能调优   点击:(19)  评论:(0)  加入收藏
Tasker 是一款适用于 Android 设备的高级自动化应用,它可以通过脚本让重复性的操作自动运行,提高效率。 不知道从哪里听说的抖音 app 会导致 OLED 屏幕烧屏。于是就现学现卖,自...【详细内容】
2021-12-15  ITBang    Tags:抖音防烧屏   点击:(23)  评论:(0)  加入收藏
11 月 23 日,Rust Moderation Team(审核团队)在 GitHub 上发布了辞职公告,即刻生效。根据公告,审核团队集体辞职是为了抗议 Rust 核心团队(Core team)在执行社区行为准则和标准上...【详细内容】
2021-12-15  InfoQ    Tags:Rust   点击:(24)  评论:(0)  加入收藏
一个项目的大部分API,测试用例在参数和参数值等信息会有很多相似的地方。我们可以复制API,复制用例来快速生成,然后做细微调整既可以满足我们的测试需求1.复制API:在菜单发布单...【详细内容】
2021-12-14  AutoMeter    Tags:AutoMeter   点击:(20)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条