看HashMap的源碼時，發(fā)現(xiàn)了里面好多很不錯的算法。
tableSizeFor的功能（不考慮大于最大容量的情況）是返回大于輸入?yún)?shù)且最近的2的整數(shù)次冪的數(shù)。比如10，則返回16。
該算法源碼如下：

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;
}

詳解如下：

先來分析有關(guān)n位操作部分：先來假設(shè)n的二進制為01xxx...xxx。接著

對n右移1位：001xx...xxx，再位或：011xx...xxx

對n右移2為：00011...xxx，再位或：01111...xxx

此時前面已經(jīng)有四個1了，再右移4位且位或可得8個1

同理，有8個1，右移8位肯定會讓后八位也為1。

綜上可得，該算法讓最高位的1后面的位全變?yōu)?。

最后再讓結(jié)果n+1，即得到了2的整數(shù)次冪的值了。

由于int是32位，所以>>>16便能滿足。

舉個栗子.jpg

現(xiàn)在回來看看第一條語句：

int n = cap - 1;

讓cap-1再賦值給n的目的是另找到的目標值大于或等于原值。例如二進制1000，十進制數(shù)值為8。如果不對它減1而直接操作，將得到答案10000，即16。顯然不是結(jié)果。減1后二進制為111，再進行操作則會得到原來的數(shù)值1000，即8。

HashMap里的MAXIMUM_CAPACITY是2³⁰。我結(jié)合tableSizeFor()的實現(xiàn)，猜測設(shè)置原因如下：
int的正數(shù)最大可達2³¹-1，而沒辦法取到2³¹。所以容量也無法達到2³¹。又需要讓容量滿足2的冪次。所以設(shè)置為2³⁰。