我們看HashMap的源碼可以知道仆潮,HashMap的長度強制為2的n次方
static final int tableSizeFor(int cap) {
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
@HotSpotIntrinsicCandidate
public static int numberOfLeadingZeros(int i) {
// HD, Count leading 0's
if (i <= 0)
return i == 0 ? 32 : 0;
int n = 31;
if (i >= 1 << 16) { n -= 16; i >>>= 16; }
if (i >= 1 << 8) { n -= 8; i >>>= 8; }
if (i >= 1 << 4) { n -= 4; i >>>= 4; }
if (i >= 1 << 2) { n -= 2; i >>>= 2; }
return n - (i >>> 1);
}
那為什么HashMap的長度L需要是2的N次方呢?
往HashMap中存儲一對k-v擅憔,那么要先計算key的hashcode鸵闪,然后我們通過hashcode計算要把這個k-v存儲到長度為L的數(shù)組的哪個位置
最簡單的,我們可以通過模運算 hashcode%L 來計算存儲的位置暑诸,但是模運算的效率相對較低蚌讼,HashMap使用位運算(與運算)來計算存儲的位置:hashcode&(L-1),這比模運算要快很多
比如長度L為16个榕,hashcode是 ……1001,那么hashcode&(L-1)為1001&1111=1001=9篡石,其實就是根據hashcode的最后四位來決定放到哪個桶里
如果長度L不為2的N次方,會怎么樣呢西采?
比如長度L為10凰萨,任何一個hashcode和1001做與運算,都不可能等于0110械馆,這樣就會有幾個位置胖眷,永遠不可能存儲到數(shù)據
hashcode和一個二進制數(shù)做與運算,如果這個二進制數(shù)的某一位為0霹崎,那么這一位與運算的結果永遠不可能為1珊搀,也就是說,如果這個二進制數(shù)不是每一位都是1尾菇,那么一定會有一些結果永遠不可能達到境析。所以這個二進制數(shù)的每一位都要是1,換成十進制這個數(shù)必須是2的N次方減1派诬。