本文主要是介绍让星星⭐月亮告诉你，HashMap之tableSizeFor(int cap)方法原理详解(分2的n次幂和非2的n次幂两种情况讨论)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
⭐⭐⭐方法说明🌙🌙🌙: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)+1return (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×21+1×22+ 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×21+0×22+ 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的值进行或的位运算,结果还是不变的.
}
这篇关于让星星⭐月亮告诉你，HashMap之tableSizeFor(int cap)方法原理详解(分2的n次幂和非2的n次幂两种情况讨论)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
