前言

最近閱讀了許多HashMap實現及源碼分析的文章，特意此文記錄HashMap的知識點。
HashMap 底層由 數組 + 鏈表 組成，在 jdk1.7 和 1.8 中具體略有不同。

JDK1.7的HashMap

數據結構：圖片來源

核心成員變量

圖片來源

初始化桶大小（1<<4，即：16），因為底層是數組，所以這是數組默認的大小。

桶容量最大值。

默認的負載因子（0.75）

table 真正存放數據的數組。

Map 中存放元素數量。

桶的容量大小，可在初始化時顯式指定。

負載因子，可在初始化時顯式指定。

負載因子

當 存放的鍵值對數量(size) = 桶容量(threshold) * 負載因子(loadFactor)時，會發生擴容，而擴容這個過程涉及到 rehash、復制數據等操作，所以非常消耗性能。因此最好提前預估 HashMap 的大小，盡量的減少擴容帶來的性能損耗。

Entry

Entry是HashMap的一個內部類，用于保存鍵值對，實現HashMap中的鏈表，主要成員變量：

• key：寫入的鍵。
• value: 寫入的值。
• next：開始的時候就提到 HashMap 是由數組和鏈表組成，所以這個 next 就是用于實現鏈表結構。
• hash: 存放的是當前 key 的 hashcode。

桶初始大小為16的原因

要解釋這個問題，首先要知道這個容量的用途。容量就是一個HashMap中"桶"的個數（數組的大小），當想要往一個HashMap中put一個元素的時候，需要通過一定的算法計算出應該把他放到哪個桶中。HashMap中通過以下兩個方法實現計算一個元素對應的桶（數組的索引）

• int hash(Object k)：該方法主要是將Object轉換成一個整型。
• int indexFor(int h, int length)：該方法主要是將hash生成的整型轉換成鏈表數組中的下標。jdk1.8沒有此方法，不過計算的方式相同。

static int indexFor(int h, int length) {return h & (length-1); }

在保證length（容量）是2^n 的前提下，h & (length-1)相當于h % (length-1)，即用位運算(&)代替取模運算(%)

Java之所有使用位運算(&)來代替取模運算(%)，最主要的考慮就是效率。
位運算(&)效率要比代替取模運算(%)高很多，主要原因是位運算直接對內存數據進行操作，不需要轉成十進制，因此處理速度非常快。

為什么保證容量為2^n即使用位運算(&)來實現取模運算(%)

總結：因為位運算直接對內存數據進行操作，不需要轉成十進制，所以位運算要比取模運算的效率更高，所以HashMap在計算元素要存放在數組中的index的時候，使用位運算代替了取模運算。而等價代替，前提是要求HashMap的容量一定要是2^n。

由上述分析，容量只要為2^n即可，HashMap選擇16的原因可能是個經驗值。

既然一定要設置一個默認的2^n 作為初始值，那么就需要在效率和內存使用上做一個權衡。這個值既不能太小，也不能太大。太小了就有可能頻繁發生擴容，影響效率。太大了又浪費空間，不劃算。(官方未給出原因)

擴容

由上述分析：HashMap必須保證容量為2^n。因此在擴容時，HashMap會進行成倍的擴容（容量變為原來的2倍）。
擴容的步驟為：

• 新建數組：創建一個新的Entry空數組，長度是原數組的2倍。
• 重新計算hash：遍歷原Entry數組，把所有的Entry重新Hash到新數組。

Put方法（頭插法）

JDK1.7下的put方法添加新元素時使用頭插法：即新來的值會成為頭節點。

public V put(K key, V value) {//判斷當前數組是否需要初始化if (table == EMPTY_TABLE) {inflateTable(threshold);}//如果 key 為空，則 put 一個空值進去。if (key == null)return putForNullKey(value);//計算鍵值hash值int hash = hash(key);//查找對應的桶的索引int i = indexFor(hash, table.length);//遍歷鏈表for (Entry<K,V> e = table[i]; e != null; e = e.next) {Object k;//遍歷判斷里面的 hashcode、key 是否和傳入 key 相等，//如果相等則進行覆蓋，并返回原來的值。if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}modCount++;//添加新鍵值對（頭插法），會判斷是否需要擴容addEntry(hash, key, value, i);return null; }

頭插法的問題

使用頭插法，在擴容時會反轉鏈表上元素的順序。在多線程及需要擴容的條件下，可能出現環形鏈表，造成死循環。
jdk1.7HashMap出現環路（有個例子，但我感覺不是特別清楚）

JDK1.8的HashMap

JDK1.7的HashMap在 Hash 沖突嚴重時，桶上形成的鏈表會變的越來越長，這樣在查詢時的效率就會越來越低；時間復雜度為 O(N)。
因此JDK1.8重點解決的此問題。
數據結構：圖片來源

主要區別

• 新的成員變量 TREEIFY_THRESHOLD 用于判斷是否需要將鏈表轉換為紅黑樹的閾值。鏈表長度大于等于該值時，會嘗試轉為紅黑樹（還需判斷數組長度是否大于MIN_TREEIFY_CAPACITY）
• 新的成員變量 UNTREEIFY_THRESHOLD 用于判斷是否需要紅黑樹轉為鏈表的閾值。
• 用Node代替Entry，在達到紅黑樹閾值時，將鏈表轉為紅黑樹提高查詢效率。
• put方法添加新的元素時，由頭插法改為尾插法。使用尾插，在擴容時會保持鏈表元素原本的順序，就不會出現鏈表成環的問題。但在 HashMap 擴容的時候會調用 resize() 方法，此時并發操作仍然可能在一個桶上形成環形鏈表。
  JDK1.8下的HashMap依舊是線程不安全的，只是用尾插法代替頭插法解決了JDK1.7時，容易出現環形鏈表的問題。

轉為紅黑樹的條件

默認情況下：鏈表長度大于 8（TREEIFY_THRESHOLD）， 表的長度大于 64（MIN_TREEIFY_CAPACITY） 的時候會轉化紅黑樹。

參考

• HashMap? ConcurrentHashMap? 相信看完這篇沒人能難住你！
• 《吊打面試官》系列-HashMap
• HashMap 為什么線程不安全？

總結

以上是生活随笔為你收集整理的一文理清HashMap的实现及细节的全部內容，希望文章能夠幫你解決所遇到的問題。

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