在 jdk8 的 HashMap 中做了很大的改動，使得Map的性能大幅提升，其中有這麼一段代碼：
/**
* 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 + 1;
}
這個方法是用于找到大于或等于輸入 cap 的最小的2的幂,比如當我輸入5時，大于或等于5的最小的2的整數次幂為8(23)，則該方法傳回8。
| 輸入(整數形式) | 輸入(二進制形式) | 傳回(整數形式) | 傳回(二進制形式) | 傳回值(2的幂形式) |
|---|---|---|---|---|
| 1 | | 1 | | 20 |
| 2 | | 2 | | 21 |
| 3 | | 4 | | 22 |
| 4 | | 4 | | 22 |
| 5 | | 8 | | 23 |
| 6 | | 8 | | 23 |
| 7 | | 8 | | 23 |
| 8 | | 8 | | 23 |
通過這個方法可以實作提前設定一個較為穩定的容量，進而避免頻繁擴容導緻的性能下降。
這個方法的實作原理比較有趣，位運算占據了方法的主體。為了分析整個運算，我這裡簡化了一下，隻保留了有效操作：
>>>
>>>
>>>
是無符号右移運算，無符号表示運算不考慮符号位。對于
int
類型的數而言，符号位為最高位。當我想要表示一個正數2時，最高位符号位為0,對應的結果為：
當我想要表示一個負數
-2
，則最高位符号位為1，其餘位要用補碼表示：
無符号右移表示最高位符号位也參與
位移運算
，如果對 -2 使用無符号右移的話，由于符号位的"1"被移動到了其他位上，此時我們會得到一個非常大的正整數。
但這明顯與我們預期不符，是以無符号位右移通常運用在正整數上。算術上的效果展現為除以2數次幂。
n |= n >>> 1
n |= n >>> 1
我們回到代碼上來，
n |= n >>> 1
不僅僅表示無符号右移，而且同時按位或了n本身，最終又将計算得到的結果指派給了n。
直接看的效果應該不明是以，不知道這樣是什麼意思。但是如果我們一位一位來看的話應該會清楚一些，由于有按位右移邏輯，我們保留最低位為0。這樣的話我們可以帶入n=2，執行一下看看會發生什麼效果：
圖檔上表現出來的效果可能不太清楚，但宏觀上表述的話就是最高位的1填補了低它一位的位置。也就是2
0010
中的1填充了低它一位的位置，最終變成了3
0011
。
再進一步分析的話會發現最高位低一位的位置是0或1對這個運算結果都沒什麼影響，因為最終都會被高位的1填充：
位移或運算
了解了這裡的代碼後，我們不難發現我們隻需要研究最左邊為1的哪一位對它身後的小兄弟做了什麼即可：
其中最後一步
n|n>>>16
：
簡單來說既是不論我們輸入一個什麼樣的正數，在
return
前我們最終都會得到一個2n-1的數。接下來再加1就能後得到我們預期的結果了。
為什麼要 cap-1
cap-1
回到開頭我們來研究一下
int n = cap - 1
起到了什麼樣的作用。此時如果我們輸入一個15，程式執行到該行會得到一個14：
好像沒什麼作用。因為不論你怎麼減，隻要不影響到最高位的1，最終結果都不變的。
但實際這裡處理的是輸入參數為 2 的整數次幂的值。如當輸入值為16時：
這裡當我們去掉
減一操作
後再試試：
二進制的展現效果如下：
也就是說最開始的
減一操作
當我們輸入了2的整數次幂時，傳回其本身，而不是将擴充一倍。
參考資料
HashMap源碼注解
HashMap中tableSizeFor解讀