让星星⭐月亮告诉你,HashMap之tableSizeFor(int cap)方法原理详解(分2的n次幂和非2的n次幂两种情况讨论)

简介: `HashMap` 的 `tableSizeFor(int cap)` 方法用于计算一个大于或等于给定容量 `cap` 的最小的 2 的幂次方值。该方法通过一系列的无符号右移和按位或运算,逐步将二进制数的高位全部置为 1,最后加 1 得到所需的 2 的幂次方值。具体步骤包括:1. 将 `cap` 减 1,确保已经是 2 的幂次方的值直接返回。2. 通过多次无符号右移和按位或运算,将最高位 1 后面的所有位都置为 1。3. 最终加 1,确保返回值为 2 的幂次方。该方法保证了 `HashMap` 的数组容量始终是 2 的幂次方,从而优化了哈希表的性能。

⭐⭐⭐方法说明🌙🌙🌙:HashMap的tableSizeFor(int cap)方法,可以返回一个大于或等于给定cap值的且最靠近cap值的2的n次幂的数值.此方法可以保证HashMap的数组容量一定是2的n次幂.采用的具体算法原理详细如下:
⭐⭐⭐原理1🌙🌙🌙:二进制或运算:0|0=0 0|1=1 1|1=1,只要有1结果就等于1.
⭐⭐⭐原理2🌙🌙🌙:假设某个int 正数,其二进制表达式(记为A)中1所在最高位的位置是从左往右数第n个数(2≤n≤32,因为int占4个字节,4个字节等于32个比特位,所以n最大为32;而当n=0时,二进制表达式中无1,无符号右移后也没任何变化,故不做讨论;当n=1时,二进制表达式中只有1个1,故再如何无符号右移后再或运算也都不会有任何变化,故也不做讨论),
⭐⭐⭐原理3🌙🌙🌙:某int正数二进制表达式中1所在最高位的位置是从左往右数第n位,则能换算成1的位数最多也只能有n位.
步骤1:则A无符号右移1位后与原A做或位运算得到二进制表达式B,可保证B前2个高位全是1;(前提1:32≥n≥2)
步骤2:则B无符号右移2位后与原B做或位运算得到二进制表达式C,可保证C前4个高位全是1;(前提2:32≥n≥4)
步骤3:则C无符号右移4位后与原C做或位运算得到二进制表达式D,可保证D前8个高位全是1;(前提3:32≥n≥8)
步骤4:则D无符号右移8位后与原D做或位运算得到二进制表达式E,可保证E前16个高位全是1;(前提4:32≥n≥16)
步骤5:则E无符号右移16位后与原E做或位运算得到二进制表达式F,可保证F前32个高位全是1;(前提5:n=32)
⭐⭐⭐注意🌙🌙🌙:1.上述步骤是有前后顺序的,是一步步从左到右把位数全部换算位1的.且只有满足对应的前提条件,才能得到对应的保证结果;
2.若1所在最高位的位置是2时,其实走到步骤1就已经结束了,后续步骤再如何无符号右移后再或运算,其最终结果也都不会有任何变化了,因为最高位的位置限定了其能有的1的个数.
3.若还未走到步骤5时,最高位后面的位就已经都换算成了1,则后续步骤也都会照常进行下去,但并不会对最终结果有任何影响,道理同第2点.

 /**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
   
        int n = cap - 1;
        //第一点:这里减1,是为了保证本身已经是2的n次幂的情形下(如:2^3=8),直接返回该值,而不是返回另外的临近的大于它的其他2的n次幂的值(2^4=16)
        //举例:
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        //第二点:经过上述的无符号右移和或位运算的操作,会将最高位1后面的位全变为1,
        //举例:cap=25,应该返回32
        //32=2^5=( 2^0+ 2^1+ 2^2+ 2^3+ 2^4)+1
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        //第三点:此处的n+1结合第二点,可以保证返回的是2的n次幂的数值
    }

举例1 本身就是2的n次幂:
假设cap=256,期望得到的结果应该是256=1×2^8= (1×2^0+ 1×2^1+ 1×2^2+ 1×2^3+ 1×2^4+ 1×2^5+ 1×2^6+ 1×2^7)+1(即将1所在的最高位后面的位的值全部换算为0,然后对最高位后的所有位求和后再加1),tableSizeFor(int cap)方法的详细运算过程如下:
static final int tableSizeFor(int cap) {//cap=256
第一步:int n = cap - 1;//n=256-1=255=1+2+4+8+16+32+64+128=1×2^0+ 1×2^1+1×2^2+ 1×2^3+ 1×2^4+ 1×2^5+ 1×2^6+ 1×2^7
//255是正数,所以其原码/反码/补码对应的二进制表示都是一样的,且一个int等于4个字节等于32比特,所以其二进制完整表示等于00000000 00000000 00000000 11111111
//下面这段计算,一开始粗心了,真没看懂,还以为是个什么新的计算符号,用心瞧了瞧,其实很简单
第二步:n|=n>>>1;//即n=n|(n>>>1);即此时n的二进制值 或位运算 此时n的二进制值无符号右移1位后的值

此时n的二进制值                            00000000 00000000 00000000 11111111
                                          或运算
此时n的二进制值无符号右移1位后的值            00000000 00000000 00000000 01000100
-----------------------------------------------------------------------------------------------
                                        00000000 00000000 00000000 11000100

结论:由于最高位是第八位,且此时最高位后续的位的0都已经换算成了1,即前8位都是1了,即使再无符号右移了8位,然后再与前8位已经是1的值进行或的位运算,结果还是不变的.

第三步:n|=n>>>2;//即n=n|(n>>>2);即此时n的二进制值 或位运算 此时n的二进制值无符号右移2位后的值

此时n的二进制值                            00000000 00000000 00000000 11000100
                                          或运算
此时n的二进制值无符号右移2位后的值            00000000 00000000 00000000 00110001
-----------------------------------------------------------------------------------------------
                                        00000000 00000000 00000000 11110101

结论:主要是将前2个已经为1的最高位向右移了2位,然后再与前2个2最高位是1的值进行或的位运算时,就可以保证前4位都是1
第四步:n|=n>>>4;//即n=n|(n>>>4);即此时n的二进制值 或位运算 此时n的二进制值无符号右移4位后的值

此时n的二进制值                            00000000 00000000 00000000 11110101  
                                          或运算
此时n的二进制值无符号右移4位后的值            00000000 00000000 00000000 00001111
-----------------------------------------------------------------------------------------------
                                        00000000 00000000 00000000 11111111

结论:主要是将前4个已经为1的最高位向右移了4位,然后再与前4个最高位是1的值进行或的位运算时,就可以保证前8位都是1
注意:此时已经达到除高位1外,其他位都换算成1的目的了,所以后续的步骤的处理逻辑应该只是保持该结果,而不应该再对该结果有所变更.
第五步:n|=n>>>8;//即n=n|(n>>>8);即此时n的二进制值 或位运算 此时n的二进制值无符号右移8位后的值

此时n的二进制值                            00000000 00000000 00000000 11111111  
                                          或运算
此时n的二进制值无符号右移8位后的值            00000000 00000000 00000000 00000000
-----------------------------------------------------------------------------------------------
                                        00000000 00000000 00000000 11111111

结论:由于最高位是第八位,且此时最高位后续的位的0都已经换算成了1,即前8位都是1了,即使再无符号右移了8位,然后再与前8位已经是1的值进行或的位运算,结果还是不变的.
第六步:n|=n>>>16;//即n=n|(n>>>16);即此时n的二进制值 或位运算 此时n的二进制值无符号右移16位后的值

此时n的二进制值                            00000000 00000000 00000000 11111111  
                                          或运算
此时n的二进制值无符号右移8位后的值            00000000 00000000 00000000 00000000
-----------------------------------------------------------------------------------------------
                                        00000000 00000000 00000000 11111111

结论:同第五步的结论,由于最高位是第八位,且此时最高位后续的位的0都已经换算成了1,即前8位都是1了,即使再无符号右移了16位,然后再与前8位已经是1的值进行或的位运算,结果还是不变的.
}

举例2 本身不是2的n次幂:
假设cap=137,期望得到的结果应该是256=1×2^8= (1×2^0+ 1×2^1+ 1×2^2+ 1×2^3+ 1×2^4+ 1×2^5+ 1×2^6+ 1×2^7)+1(即将1所在的最高位后面的位的值全部换算为0,然后对最高位后的所有位求和后再加1),tableSizeFor(int cap)方法的详细运算过程如下:
static final int tableSizeFor(int cap) {//cap=137
第一步:int n = cap - 1;//n=137-1=136=0+0+0+8+0+0+0+128=0×2^0+ 0×2^1+0×2^2+ 1×2^3+ 0×2^4+ 0×2^5+ 0×2^6+ 1×2^7
//136是正数,所以其原码/反码/补码对应的二进制表示都是一样的,且一个int等于4个字节等于32比特,所以其二进制完整表示等于00000000 00000000 00000000 10001000
第二步:n|=n>>>1;//即n=n|(n>>>1);即此时n的二进制值 或位运算 此时n的二进制值无符号右移1位后的值

此时n的二进制值                            00000000 00000000 00000000 10001000
                                          或运算
此时n的二进制值无符号右移1位后的值            00000000 00000000 00000000 01000100
-----------------------------------------------------------------------------------------------
                                        00000000 00000000 00000000 11000100

结论:主要是将为1的最高位第8位向右移了1位,然后再与最高位为1的原来的值进行或的位运算时,就可以保证最高位第8位和第7位必然都是1(注:这里第3位也是1,是因为原来的值里的第4位本来就是1,右移1位后第4位变成第3位所以也是1,并非该算法导致的必然结果.)

第三步:n|=n>>>2;//即n=n|(n>>>2);即此时n的二进制值 或位运算 此时n的二进制值无符号右移2位后的值

此时n的二进制值                            00000000 00000000 00000000 11000100
                                          或运算
此时n的二进制值无符号右移2位后的值            00000000 00000000 00000000 00110001
-----------------------------------------------------------------------------------------------
                                        00000000 00000000 00000000 11110101

结论:主要是将前2个已经为1的最高位向右移了2位,然后再与前2个2最高位是1的值进行或的位运算时,就可以保证前4位都是1
第四步:n|=n>>>4;//即n=n|(n>>>4);即此时n的二进制值 或位运算 此时n的二进制值无符号右移4位后的值

此时n的二进制值                            00000000 00000000 00000000 11110101  
                                          或运算
此时n的二进制值无符号右移4位后的值            00000000 00000000 00000000 00001111
-----------------------------------------------------------------------------------------------
                                        00000000 00000000 00000000 11111111

结论:主要是将前4个已经为1的最高位向右移了4位,然后再与前4个最高位是1的值进行或的位运算时,就可以保证前8位都是1
注意:此时已经达到除高位1外,其他位都换算成1的目的了,所以后续的步骤的处理逻辑应该只是保持该结果,而不应该再对该结果有所变更.
第五步:n|=n>>>8;//即n=n|(n>>>8);即此时n的二进制值 或位运算 此时n的二进制值无符号右移8位后的值

此时n的二进制值                            00000000 00000000 00000000 11111111  
                                          或运算
此时n的二进制值无符号右移8位后的值            00000000 00000000 00000000 00000000
-----------------------------------------------------------------------------------------------
                                        00000000 00000000 00000000 11111111

结论:由于最高位是第八位,且此时最高位后续的位的0都已经换算成了1,即前8位都是1了,即使再无符号右移了8位,然后再与前8位已经是1的值进行或的位运算,结果还是不变的.
第六步:n|=n>>>16;//即n=n|(n>>>16);即此时n的二进制值 或位运算 此时n的二进制值无符号右移16位后的值

此时n的二进制值                            00000000 00000000 00000000 11111111  
                                          或运算
此时n的二进制值无符号右移8位后的值            00000000 00000000 00000000 00000000
-----------------------------------------------------------------------------------------------
                                        00000000 00000000 00000000 11111111

结论:同第五步的结论,由于最高位是第八位,且此时最高位后续的位的0都已经换算成了1,即前8位都是1了,即使再无符号右移了16位,然后再与前8位已经是1的值进行或的位运算,结果还是不变的.
}

目录
相关文章
|
2月前
|
存储
让星星⭐月亮告诉你,HashMap的put方法源码解析及其中两种会触发扩容的场景(足够详尽,有问题欢迎指正~)
`HashMap`的`put`方法通过调用`putVal`实现,主要涉及两个场景下的扩容操作:1. 初始化时,链表数组的初始容量设为16,阈值设为12;2. 当存储的元素个数超过阈值时,链表数组的容量和阈值均翻倍。`putVal`方法处理键值对的插入,包括链表和红黑树的转换,确保高效的数据存取。
59 5
|
2月前
|
算法 索引
让星星⭐月亮告诉你,HashMap的resize()即扩容方法源码解读(已重新完善,如有不足之处,欢迎指正~)
`HashMap`的`resize()`方法主要用于数组扩容,包括初始化或加倍数组容量。该方法首先计算新的数组容量和扩容阈值,然后创建新数组。接着,旧数组中的数据根据`(e.hash & oldCap)`是否等于0被重新分配到新数组中,分为低位区和高位区两个链表,确保数据迁移时的正确性和高效性。
67 3
|
2月前
|
存储 索引
让星星⭐月亮告诉你,HashMap在put数据时是如何找到要存放的位置的?
HashMap 是一种常用的键值对存储结构,其底层采用数组+链表+红黑树实现。本文探讨了 HashMap 在插入键值对时如何确定存放位置。通过分析 `put` 方法的源代码,重点解析了哈希码的计算过程和数组索引的确定方法。哈希码通过 `hashCode()` 方法和位运算优化,确保均匀分布,从而减少哈希碰撞,提高性能。最终,通过 `(n-1) & hash` 计算出数组索引,确保键值对被正确存放到指定位置。
36 2
|
7月前
|
数据采集 分布式计算 数据处理
Dataphin常见问题之与指定类型int不兼容如何解决
Dataphin是阿里云提供的一站式数据处理服务,旨在帮助企业构建一体化的智能数据处理平台。Dataphin整合了数据建模、数据处理、数据开发、数据服务等多个功能,支持企业更高效地进行数据治理和分析。
|
7月前
|
SQL 流计算 OceanBase
OceanBase CDC从热OB库采集过来的Tinyint(1)类型会默认转换成Boolean,请教一下,如果想转换成int类型,有什方法么?
【2月更文挑战第25天】OceanBase CDC从热OB库采集过来的Tinyint(1)类型会默认转换成Boolean,请教一下,如果想转换成int类型,有什方法么?
181 3
|
2月前
|
Python
[oeasy]python036_数据类型有什么用_type_类型_int_str_查看帮助
本文回顾了Python中`ord()`和`chr()`函数的使用方法,强调了这两个函数互为逆运算:`ord()`通过字符找到对应的序号,`chr()`则通过序号找到对应的字符。文章详细解释了函数参数类型的重要性,即`ord()`需要字符串类型参数,而`chr()`需要整数类型参数。若参数类型错误,则会引发`TypeError`。此外,还介绍了如何使用`type()`函数查询参数类型,并通过示例展示了如何正确使用`ord()`和`chr()`进行转换。最后,强调了在函数调用时正确传递参数类型的重要性。
24 3
|
4月前
|
Java
【Java基础面试五】、 int类型的数据范围是多少?
这篇文章回答了Java中`int`类型数据的范围是-2^31到2^31-1,并提供了其他基本数据类型的内存占用和数值范围信息。
【Java基础面试五】、 int类型的数据范围是多少?
|
4月前
|
自然语言处理 Go 数据安全/隐私保护
对 int 类型的数据加密,有哪些好的方案?
对 int 类型的数据加密,有哪些好的方案?
106 13
|
6月前
|
机器学习/深度学习 人工智能 分布式计算
人工智能平台PAI产品使用合集之int类型是否可以为raw feature
阿里云人工智能平台PAI是一个功能强大、易于使用的AI开发平台,旨在降低AI开发门槛,加速创新,助力企业和开发者高效构建、部署和管理人工智能应用。其中包含了一系列相互协同的产品与服务,共同构成一个完整的人工智能开发与应用生态系统。以下是对PAI产品使用合集的概述,涵盖数据处理、模型开发、训练加速、模型部署及管理等多个环节。
|
6月前
|
运维 Cloud Native 关系型数据库
云原生数据仓库AnalyticDB产品使用合集之布尔类型和int类型可以自动转换吗
阿里云AnalyticDB提供了全面的数据导入、查询分析、数据管理、运维监控等功能,并通过扩展功能支持与AI平台集成、跨地域复制与联邦查询等高级应用场景,为企业构建实时、高效、可扩展的数据仓库解决方案。以下是对AnalyticDB产品使用合集的概述,包括数据导入、查询分析、数据管理、运维监控、扩展功能等方面。
159 1