首页 > 其他分享 >HashMap的数组最大容量为什么要设计为2的30次方?而不是2的31次方-1?数组容量为什么一定要设计为2的幂?

HashMap的数组最大容量为什么要设计为2的30次方?而不是2的31次方-1?数组容量为什么一定要设计为2的幂?

时间:2024-03-23 21:31:12浏览次数:24  
标签:hash HashMap 容量 16 31 数组 次方

目录

问题

 数组容量为什么一定要设计为2的幂(2的n次方)?

1、首先要清楚HashMap的底层基本原理

2、再来看下怎么通过hash值决定存放在哪个桶中?

首先看下hash值

再看下怎么确定当前key存放在哪个数组下标下的

为什么要做按位与而不用模运算符%?

为什么要n-1呢?

n是一个什么样的数的时候才能保证n-1的二进制全是1呢?

3、总结

为什么到16就停止了?

HashMap的数组最大容量为什么要设计为2的30次方?而不是2的31次方-1?

回到开头,为什么已经选用了int类型,什么不用2^31-1,而是用了2^31?


一、问题

今天看HashMap源码的时候看到了下面这行,数组的最大容量

1 << 30表示1左移30位,也就是表示2的30次方。

不由得很是疑惑,既然已经选用了int类型,int占4个字节,32位,最左边1个符号位,还剩31位用来表达范围,31位全是1的情况下,int类型可以表达的最大值也就是2^31-1=2147483647,相当于是21亿+,而2^30=1073741824,相当于10亿+,那HashMap的容量可以设计为10亿+,为什么不能设计为21亿+呢?

带着问题继续研究源码

要搞清楚为什么设计成2^30次方的关键就在于数组容量为什么一定要设计为2的幂(2的n次方)?

、数组容量为什么一定要设计为2的幂(2的n次方)?

1、首先要清楚HashMap的底层基本原理

HashMap的基本原理是数组+链表+红黑树。

数组初始容量是16,每次添加元素时,需要先计算key的hash值来决定存放在哪个桶中(即数组中的哪个位置),然后将value值放在对应的桶中。每个桶中存放的是一个链表,链表长度默认为8。

扩容:当数组元素数量>=数组容量*扩容因子(默认是0.75)时,触发扩容,所以默认第一次扩容16*0.75=12,每次扩容为原来数组容量的2倍,当数组容量大于等于64时,链表长度达到8时,链表会转为红黑树(自平衡的二叉搜索树)。

补充:当数组容量<64,且某个链表节点数达到阈值8时,会优先触发扩容,并不是直接转红黑树。

2、再来看下怎么通过hash值决定存放在哪个桶中?

首先看下hash值

1)hashCode()是一个本地方法(基于其他语言实现),会返回一个32位的整数(int类型)。

2)h >>> 16,对这个hash值进行无符号右移16位的运算,左边补0,结果就是上面得到Hash值的高16位(左边的16位)。

3)h ^ (h >>> 16)然后对h和第二步的结果进行按位异或运算,也就是对原Hash值的高16位和低16位进行按位异或运算,最终的到的值就是HashMap中要用的hash值。

这里也是为什么Object对象中要拥有hashCode()方法的原因之一。

为什么要进行异或运算呢?

原始的hashCode()方法返回的哈希码可能分布不够均匀,尤其是在高位部分。通过 (h >>> 16) 这个无符号右移16位的操作,可以将哈希码的高半部分移到低半部分,然后再与原始哈希码做异或运算,这样可以将高位和低位的信息进行混合,增加了哈希码的随机性,减少由于哈希碰撞引发的链表过长或者树形结构过深的问题,从而提高查询和插入的效率。

再看下怎么确定当前key存放在哪个数组下标下的

当容量为16时,n-1为15,二进制为1111,然后和hash值去做按位与运算,来确定最后存放的桶的下标。(这里在调试时,n是256,有知道的大佬可以解惑吗?) 这里调试时候遇到256的原因是类加载器中也有用到map(这一点可以在调用栈中明显看到),所以第一次进的断点并不是我们想要的断点,这里是个误区,调试时需要注意。

为什么要做按位与而不用模运算符%?

按位与操作是计算机底层硬件直接支持的,执行速度非常快。

而且按位与可以直接获取原来hash值的低位二进制,如下:

1011 1101------199

0000 1111------15

-------------------------

0000 1101-----13

所以最终决定存放在哪个桶的时候是根据hash值取低位的二进制来决定的,并不是很多人说的hash对数组长度取余。结果范围始终在0到n-1之间,正好对应数组的索引。     

为什么要n-1呢?

为了保证得到的全是1的二进制。

n是一个什么样的数的时候才能保证n-1的二进制全是1呢?

只有当n是2的幂的时候,n-1的二进制才能保证全1。

3、总结

所以设计者规定了,HashMap中的数组容量必须是2的幂(即2的n次方)。

并且在有参构造器中,可以指定数组容量。

通过这个算法得到的返回值,一定是大于且最接近指定容量的2的幂。

如:指定容量是70,返回值就会是128=2^7

为什么到16就停止了?

右移的次数加起来 1+2+4+8+16=31,最多只有31位啊。

三、HashMap的数组最大容量为什么要设计为2的30次方?而不是2的31次方-1?

现在已经知道数组的容量一定要保证2的幂

回到开头,为什么已经选用了int类型,什么不用2^31-1,而是用了2^31?

在int范围内,2的幂的最大值是2^30,2^31-1是int类型能表示的最大值,但它不是2的幂啊!!!

所以很多人会说最大容量是2^30的原因是,要保证2的幂,这是关键。

标签:hash,HashMap,容量,16,31,数组,次方
From: https://blog.csdn.net/weixin_45967584/article/details/136918330

相关文章

  • 100道面试必会算法-09-最大子数组和(初探动态规划)
    100道面试必会算法-09-最大子数组和(初探动态规划)题目一个整数数组nums,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。子数组是数组中的一个连续部分。示例1:输入:nums=[-2,1,-3,4,-1,2,1,-5,4]输出:6解释:连续子数组[4,-1,2,1]的和最大,......
  • 使用CSDN编写一元二次方程
    一元二次方程标准形式:ax2+bx......
  • BUGAWAY算法小抄-树状数组(2024.03.23 更新)
    什么是树状数组?树状数组是支持单点修改和区间查询的、代码量小的数据结构。事实上,树状数组能解决的问题是线段树(一棵二叉树,每个节点表示一个区间,并存储该区间的一些相关信息。线段树可以高效地进行区间查询和区间更新操作。不是本文重点)能解决的问题的子集:树状数组能做的,线段树......
  • 用函数和数组实现扫雷游戏(从0开始)
    文章目录概要整体架构流程(这里用VS2023来制作)代码实现小结概要学完数组和函数后我们可以通过所学知识写一个扫雷游戏,并实现一些拓展功能。我们采用多文件联调的模式来制作,这里需要先建好三个文件game.hgame.cminesweeper.c整体架构流程(这里用VS2023来制作)在......
  • 代码随想录算法训练营day31 | leetcode 455. 分发饼干、376. 摆动序列、53. 最大子数
    目录贪心理论基础核心:题目链接:455.分发饼干-简单题目链接:376.摆动序列-中等题目链接:53.最大子数组和-中等贪心理论基础核心:由局部推全局最优题目链接:455.分发饼干-简单题目描述:假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。对每......
  • 用索引"copyofRange(int[] arr, int from,int to)"复制数组中的数,形成新数组的方法
    publicclasstest2{publicstaticvoidmain(String[]args){//定义原数组int[]arr={1,2,3,4,5,6,7,8,9};//引用copyofRange方法复制元素到新数组中int[]newcopy=copyofRange(arr,3,7);//输出新数组for(inti=......
  • mongoDB使用记录:误用数组索引
    版本:mongoDB4.2集群方案:副本+分片一个问题场景:集合内对多个字段建立索引,其中包含数组索引;当执行查询时,业务查询期望命中数组索引,mongodb筛选策略首次给出的执行方案命中了另外的索引key,导致当次慢查询,扫描超过1000w数量的文档,业务出现卡顿;处理&优化方案:mongodb筛选策略命中......
  • 一元二次方程ax2+bx+c=0,a、b、c的值由用户在三行中输入,根据用户输入的数值求解方程的
    输入格式输入三行数据每行输入一个实数输出格式方程的解示例1输入:852输出:该方程无实数解示例2输入:009输出:Dataerror!a=float(input())b=float(input())c=float(input())delta=b**2-4*a*c#德塔ifdelta<0:print("该方程无实数解")#ab==0elif......
  • 程序跑飞原因总结 && 引脚配置&&中断&&while循环&&数组越界 &&硬件原因
    2023.11月开始做了新项目,技术不到家导致程序多次跑飞,现在总结如下一、引脚配置错误错误原因:同一个引脚初始化两次1.硬件原理图变更,引脚功能变动,改动时不仔细2.代码规范不好:对于引脚的宏定义封装不好,除了.h文件还在其他地方出现数字引脚错误现象:1.程序跑飞2.调试时将新增......
  • 数组 题目
    1.2034:【例5.1】反序输出【题目描述】输入n个数,要求程序按输入时的逆序把这n个数打印出来,已知整数不超过100个。也就是说,按输入相反顺序打印这n个数。【输入】输入一行共有n个数,每个数之间用空格隔开。【输出】如题要求:一行,共有n个数,每个数之间用一个空格隔开。......