java对HashMap中容量计算算法的理解

Question

我有兴趣了解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;
}

上面的实现可以代替复杂的按位右移实现，这有什么意义

Answer 1

该算法是一种快速确定2的最小幂的方法，它大于或等于给定的cap

它的工作方式是计算只有一个位集的数字，这个位的位置高于原始数字中的所有其他位（如果只有一个位集，则位于原始数字的最高位）。为此，它将所有小于前导位的位设置为1，然后添加1

下面是它如何处理写为001XXXXXXXXX的正数（前导位后的位无关紧要）：

int n = cap - 1;    // will not change anything to the leading bit except
                    // if cap is already a power of 2. In that case,  
                    // we had cap = 001000000000 and now n = 000111111111 and
                    // the other lines won't change anything, we just have to
                    // do +1 in the end and we're done, n = cap;
                    // otherwise, let's assume that not every 'X' is a '0'

n |= n >>> 1;       // n >>> 1 = 0001XXXXXXX
                    // so    n = 0011XXXXXXX

n |= n >>> 2;       // n >>> 2 = 000011XXXXX
                    // so    n = 001111XXXXX

n |= n >>> 4;       //       n = 0011111111X

n |= n >>> 8;       //       n = 00111111111

n |= n >>> 16;      //       n = 00111111111

return n + 1;       //  result = 01000000000

对于负数，n在每一行都是负数，因为符号位总是1，所以结果将是1