關于HashMap的詳解文章請移步：

鏈接: HashMap源碼研究——源碼一行一行的注釋

文章目錄

• 為什么初始容量是 2次冪？
• 如果指定了不是2的次冪的容量會發生什么？
• • 有一個初始容量參數的構造方法HashMap(int initialCapacity)
  • 有兩個參數的構造方法HashMap(int initialCapacity, float loadFactor)
• 擾動函數

為什么初始容量是 2次冪？

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 如果沒有hash碰撞則直接插入元素if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);else {......} }

通過看源碼，我們發現，判斷桶的索引的實現是 i = ( n - 1 ) & hash，其中 n 是 map 的容量。

任何 2 的整數冪 - 1 得到的二進制都是 1，如：16 - 1 = 15（1111）；32 - 1 = 31（11111）

而 n-1 與 hash 做的是與運算(&)，與運算是 兩個都為1，才為1

既然我們的 n-1 永遠都是 1，那 ( n - 1 ) & hash 的計算結果就是 低位的hash 值。如：

00100100 10100101 11000100 00100101 // Hash 值 & 00000000 00000000 00000000 00001111 // 16 - 1 = 15 ----------------------------------00000000 00000000 00000000 00000101 // 高位全部歸零，只保留末四位。

那容量不是 2次冪會怎么樣？我們來做個試驗。

2次冪的情況：

非2次冪的情況，假設 n = 10:

對比來看，哪種發生哈希碰撞的概率更低一目了然，如果 n 為 2次冪，可以保證數據的均勻插入，降低哈希沖突的概率，畢竟沖突越大，代表數組中的鏈表/紅黑樹越大，從而降低Hashmap 的性能。

如果指定了不是2的次冪的容量會發生什么？

答案：會獲得最接近的一個2的次冪作為容量

有一個初始容量參數的構造方法HashMap(int initialCapacity)

參數：initialCapacity 初始容量

public HashMap(int initialCapacity) {//此處通過把第二個參數負載因子使用默認值0.75f，然后調用有兩個參數的構造方法this(initialCapacity, DEFAULT_LOAD_FACTOR);}

這個一個參數的構造方法，使用HashMap的默認負載因子，把該初始容量和默認負載因子作為入參，調用HashMap的兩個參數的構造方法

有兩個參數的構造方法HashMap(int initialCapacity, float loadFactor)

參數：initialCapacity 初始容量
參數：loadFactor 負載因子

/*** Constructs an empty <tt>HashMap</tt> with the specified initial* capacity and load factor.* 通過指定的初始容量和負載因子初始化一個空的HashMap** @param initialCapacity the initial capacity 初始化容量* @param loadFactor the load factor 負載因子* @throws IllegalArgumentException if the initial capacity is negative* or the load factor is nonpositive* 如果初始容量或者負載因子為負數，則會拋出非法數據異常*/public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0) //如果初始容量小于0，拋出異常throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY) //如果初始容量超過最大容量（1<<32）initialCapacity = MAXIMUM_CAPACITY; //則使用最大容量作為初始容量if (loadFactor <= 0 || Float.isNaN(loadFactor)) //如果負載因子小于等于0或者不是數字，則拋出異常throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor; //把負載因子賦值給成員變量loadFactor//調用tableSizeFor方法計算出不小于initialCapacity的最小的2的冪的結果，并賦給成員變量thresholdthis.threshold = tableSizeFor(initialCapacity); }

我們下面看看tableSizeFor()這個方法是如何計算的，這個方法的實現原理很巧妙，源碼如下：

/*** Returns a power of two size for the given target capacity.*/static final int tableSizeFor(int cap) {int n = cap - 1; //容量減1，為了防止初始化容量已經是2的冪的情況，最后有+1運算。n |= n >>> 1; //將n無符號右移一位再與n做或操作n |= n >>> 2; //將n無符號右移兩位再與n做或操作n |= n >>> 4; //將n無符號右移四位再與n做或操作n |= n >>> 8; //將n無符號右移八位再與n做或操作n |= n >>> 16; //將n無符號右移十六位再與n做或操作//如果入參cap為小于或等于0的數，那么經過cap-1之后n為負數，n經過無符號右移和或操作后仍未負 //數,所以如果n<0,則返回1;如果n大于或等于最大容量，則返回最大容量;否則返回n+1return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}

首先，為什么要對cap做減1操作。int n = cap - 1;
這是為了防止，cap已經是2的冪。如果cap已經是2的冪， 又沒有執行這個減1操作，則執行完后面的幾條無符號右移操作之后，返回的capacity將是這個cap的2倍。如果不懂，要看完后面的幾個無符號右移之后再回來看看。
下面看看這幾個無符號右移操作：
如果n這時為0了（經過了cap-1之后），則經過后面的幾次無符號右移依然是0，最后返回的capacity是1（最后有個n+1的操作）。
這里只討論n不等于0的情況。
第一次右移

n |= n >> 1;

由于n不等于0，則n的二進制表示中總會有一bit為1，這時考慮最高位的1。通過無符號右移1位，則將最高位的1右移了1位，再做或操作，使得n的二進制表示中與最高位的1緊鄰的右邊一位也為1，如000011xxxxxx。
第二次右移

n |= n >>> 2;

注意，這個n已經經過了n |= n >>> 1; 操作。假設此時n為000011xxxxxx ，則n無符號右移兩位，會將最高位兩個連續的1右移兩位，然后再與原來的n做或操作，這樣n的二進制表示的高位中會有4個連續的1。如00001111xxxxxx 。
第三次右移

n |= n >>> 4;

這次把已經有的高位中的連續的4個1，右移4位，再做或操作，這樣n的二進制表示的高位中會有8個連續的1。如00001111 1111xxxxxx 。
以此類推
注意，容量最大也就是32bit的正數，因此最后n |= n >>> 16; ，最多也就32個1，但是這時已經大于了MAXIMUM_CAPACITY ，所以取值到MAXIMUM_CAPACITY 。

但是，請注意，在構造方法中，并沒有對table這個成員變量進行初始化，table的初始化被推遲到了put方法中，在put方法中會對threshold重新計算。

擾動函數

HashMap 中的擾動函數是一個通過對 key 值類型自帶的哈希函數生成的散列值進行位移計算來擾亂散列值，以達到降低哈希碰撞的概率的方法。源碼中對應的是 hash()，但具體是如何進行移位和降低碰撞概率的？？

// jdk 8 static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

我們分析一下hash()，key.hash() 調用的是key類型自帶的哈希函數，返回的是 int 類型的散列值。

如果沒有擾動函數的情況下，我們拿著散列值作為下標找到 hashmap 中對應的桶位存下即可（不發送哈希沖突的情況下），但 int 類型是 32 位，很少有Hashmap的數組有40億這么大，所以， key 類型自帶的哈希函數返回的散列值不能拿來直接用。如果我們取低幾位的 hash 值來做數組映射行不行，但是如果低位相同，高位不同的 hash 值就碰撞了，如：

// Hash 碰撞示例： 00000000 00000000 00000000 00000101 & 1111 = 0101 // H1 00000000 11111111 00000000 00000101 & 1111 = 0101 // H2

為了解決這個問題，HashMap 想了個辦法，用擾動函數降低碰撞的概率。將 hash 值右移16位（hash值的高16位）與 原 hash 值做異或運算（^），從而得到一個新的散列值。如：

00000000 00000000 00000000 00000101 // H1 00000000 00000000 00000000 00000000 // H1 >>> 16 00000000 00000000 00000000 00000101 // hash = H1 ^ (H1 >>> 16) = 500000000 11111111 00000000 00000101 // H2 00000000 00000000 00000000 11111111 // H2 >>> 16 00000000 00000000 00000000 11111010 // hash = H2 ^ (H2 >>> 16) = 250

H1,H2 兩個 hash 值經過擾動后，很明顯不會發生碰撞。

總結
總的來說，不管是規定 Hashmap 的 n 為 2次冪，還是擾動函數，都是為了一個目標，降低哈希沖突的概率，從而使 HashMap 性能得到優化。而規定 n 為 2次冪，是在新建 Hashmap對象初始化時，規定其容量大小的角度來優化。而擾動函數是插入 key 值時改變 key 的散列值來達到優化效果。

總結

以上是生活随笔為你收集整理的为什么HashMap默认初始容量为2次幂？不是2次幂会怎样？讲讲 HashMap 扰动函数？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。