讀HashMap源碼之tableSizeFor

/**
     * Returns a power of two size for the given target capacity.
     */
    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的n次方那個數

即如果傳入10，傳回2^4 = 16、傳入18，傳回2^5 = 32，傳入34，應該傳回2^6 = 64

測試一下

public static void main(String[] args) {
        System.out.println("傳入10----"+tableSizeFor(10));
        System.out.println("傳入18----"+tableSizeFor(18));
        System.out.println("傳入34----"+tableSizeFor(34));
    }

    static final int tableSizeFor(int cap) {
        Integer MAXIMUM_CAPACITY = 1 << 30;
        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;
    }      

結果：

怎麼來的呢？先認識一下兩個運算符​​

​|​

​​和​

​>>>​

​​

​|​

​不用多說，二進制或，兩個都為0才為0

​

​>>>​

​，無符号右移

無符号右移，忽略符号位，空位都以0補齊

10進制轉二進制的時候，因為二進制數一般分8位、 16位、32位以及64位（java是四個位元組32位） 表示一個十進制數，是以在轉換過程中，最高位會補零

來動手算一個，傳入10

int n = cap - 1;      

後n = 9

n |= n >>> 1;      

先算​

​n >>> 1​

​​，再算​

​n= n|前面的結果​

​​

同理，在計算```n |= n >>> 2;``，此時n已經等于13了

同理，在計算```n |= n >>> 4;``，此時n已經等于15了

到此可以看出，它的每一次運算，都是在将有0的位轉換成1，直到所有位都為1為止