java对HashMap中容量计算算法的理解
我有兴趣了解HashMap中容量计算算法的工作原理
其中,如果我们创建的对象HashMap具有一些所需的容量20,那么算法将始终计算下一个最高容量,即(2^x>;20)
下面是jdk实现
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;
}
有人能给我解释一下上述算法是如何工作的吗?每一步都会发生什么
我知道,在每一步中,他们都会将数字2除以,然后按位或按旧值进行运算。 他们这样做是因为他们必须分配下一个(2^x)大于n的值
但有人能帮我解释一下,在每一步中,一些数字会发生什么,我试着调试,但感觉很复杂
我有一些想法,如下所示
private static int calculateCapacity(int cap){
int max_capcity = 256;
if(cap<16){
return 16;
}else if(cap <32){
return 32;
}else if(cap <64){
return 64;
}else if(cap < 128){
return 128;
}
return max_capcity;
}
上面的实现可以代替复杂的按位右移实现,这有什么意义
# 1 楼答案
该算法是一种快速确定
2
的最小幂的方法,它大于或等于给定的cap
它的工作方式是计算只有一个位集的数字,这个位的位置高于原始数字中的所有其他位(如果只有一个位集,则位于原始数字的最高位)。为此,它将所有小于前导位的位设置为
1
,然后添加1
下面是它如何处理写为
001XXXXXXXXX
的正数(前导位后的位无关紧要):对于负数,
n
在每一行都是负数,因为符号位总是1
,所以结果将是1