HashMap是JDK中非常重要的容器，採用 數組 + 鏈表 的方式實現，理想情況下能支持 O(1) 時間複雜度的增刪改查操作。本文將由淺入深地講解哈希表的實現原理，並對HashMap的部分源碼進行分析。
1. 從數組說起
數組應該是我們最先學習的數據結構，它是內存中一塊連續的存儲單元，因此計算機可以根據數組起始地址、元素長度和下標，計算出我們要訪問的元素的地址，時間複雜度為 O(1) 。
以下代碼定義了一個簡單的 Student 類，假如我們要存儲 20 個 Student 對象，我們希望能夠在 O(1) 時間複雜度內，根據 studentID 找到相應的對象。
<code>public class Student { public int studentID; public String name; public Student(int studentID, String name) { this.studentID = studentID; this.name = name; }} 複製代碼/<code>如果我們要存儲的 20 個 Student 對象的 studentID 剛好就是從 0 到 19，我們自然可以新建一個長度為 20 的 Student 數組 students，然後將對象的 studentID 作為數組下標，放到對應的 slot 裡面，如下圖所示。這樣的話，如果我們想找 studentID 為 15 的對象，我們就可以直接訪問 students[15]。
<code>Student[] students = new Student[20]; Student stu0 = new Student(0, "stu0");Student stu19 = new Student(19, "stu19"); students[stu0.studentID] = stu0;students[stu19.studentID] = stu19; 複製代碼/<code>
為了表述方便，我們用 key 表示查找關鍵字，在這裡指的 studentID，用 value 表示查找內容，這裡指的 Student 對象，用 slot 表示數組的每一個元素，slot 由數組下標 index 來唯一標識（slot 的意思是槽，數組的元素就像是一個槽一樣，等著被 Student 對象填滿）。下圖展示了 Student 對象在數組中的存儲狀態。
但是實際情況很可能是這 20 個 Student 對象的 studentID 在某個範圍內隨機分佈，比如 0~2000。如果我們這個時候還把 studentID 作為數組下標的話，就需要創建一個長度為 2001 的數組，但我們只使用其中的 20 個用來存放 Student 對象，這樣就造成了大量的空間浪費。
2. 哈希函數和哈希碰撞
那如何既能利用數組的常數查找特性，又能避免空間浪費呢？我們可以很自然地想到，建立一個將 studentID 映射到 0~19 的函數，比如 h(studentID) = studentID % 20。這個函數就叫做哈希函數（或者散列函數），以此為例，我們可以將 studentID 分別為 21，140，1163 的 Student 對象存儲到數組上，如下圖。
<code>Student stu21 = new Student(21, "stu21");Student stu140 = new Student(140, "stu140");Student stu1163 = new Student(1163, "stu1163");students[stu21.studentID % 20] = stu21;students[stu140.studentID % 20] = stu140;students[stu1163.studentID % 20] = stu1163; 複製代碼/<code>
哈希函數的實現方式有很多，一個好的哈希函數應該儘可能地讓映射後的結果均勻地分佈在數組上。
接下來我們再考慮另一個問題，如果我們有兩個 Student 對象，他們的 studentID 分別為 21 和 41，那麼這兩個對象都要存儲到數組上 index 為 1 的 slot，這種情況就叫做哈希碰撞。
解決哈希碰撞的方式有兩種，拉鍊法和開放尋址法。前者就是 HashMap 中用到的方法，在每個 slot 後面懸掛一條鏈表，每進來一個結點就把它放到鏈表的尾部。後者是採用不同的方式重新計算一次 key 對應的 index，直到找到一個不包含 Student 對象的 slot。
以上就是哈希表的基本原理，studentID 就類似於下文所說的哈希值的概念，我們通過 key 的哈希值來判斷這個結點要放到哪個 slot 中。
下面我們通過 JDK 12.0.2 版本的源碼來看看 HashMap 是如何工作的。
3. HashMap 中的常量
HashMap 中的一些比較重要的常量如下。
<code>static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; static final float DEFAULT_LOAD_FACTOR = 0.75f;static final int TREEIFY_THRESHOLD = 8; 複製代碼/<code>
根據英文名稱我們可以大致瞭解該常量的作用，DEFAULT_INITIAL_CAPACITY 是默認初始容量，1 << 4 表示 1 左移四位，也就是 16。大家已經明白，HashMap 是以 數組+鏈表 的方式實現的，這裡容量指的就是實例化 HashMap 對象內部數組的長度。如果我們調用哈希表的構造函數時，未指定初始容量，數組的長度就由這個默認初始容量確定。
DEFAULT_LOAD_FACTOR 默認裝載因子，裝載因子的含義是平均每個 slot 上懸掛了多少個結點，可以由下式計算得到
裝載因子 = 結點數量 / 數組長度
同樣的，如果調用哈希表的構造函數時，未指定裝載因子，就使用這個裝載因子。
TREEIFY_THRESHOLD 是樹形化閾值，當某個 slot 懸掛的結點數量大於樹形化閾值的時候，就把鏈表轉化為一棵紅黑樹。為什麼樹形化閾值取 8 呢？按照官方的說法，如果 key 的哈希值是隨機的，在裝載因子為 0.75 時，每個 slot 中節點出現的頻率服從參數為 0.5 的泊松分佈，所以鏈表的長度（size）為 k 的概率為
代入 k = 8 可以得到 0.00000006，也就是說鏈表長度為 8 的概率小於千萬分之一，所以選取 8 作為樹形化閾值。
4. 靜態內部類 Node
node 就是結點的意思，本文中所說的 “結點”，指的就是一個 Node 對象。Node
<code>static class Nodeimplements Map.Entry /<code>複製代碼
Node
<code>final int hash;final K key;V value;Nodenext; 複製代碼 /<code>
5. HashMap 構造函數和擴容
以下是 HashMap 的成員變量，table 是 Node 數組，HashMap 就用它來存放結點。size 表示目前 HashMap 中存放的結點總數。threshold 是閾值，表示當前的數組容量所能容納的結點數，它是裝載因子和數組容量的乘積，當 size 大於 threshold 的時候，就需要進行擴容操作。loadFactor 即裝載因子。
<code>transient Node[] table;transient int size;int threshold;final float loadFactor; 複製代碼 /<code>
構造函數的主要任務就是初始化其中的一些成員變量，因為我們調用的是無參構造函數，所以只有裝載因子被賦值了。注意這個時候並沒有初始化 table 數組。
<code>public HashMap(int initialCapacity, float loadFactor) {// 省略了一些判斷極端輸入的代碼this.loadFactor = loadFactor;this.threshold = tableSizeFor(initialCapacity);}public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted} 複製代碼/<code>tableSizeFor() 這個方法返回大於等於 initialCapaticy 的最小的 2 的冪。比如輸入 16 就返回 16，輸入 17 就返回 32。以下是該方法的實現。
<code>static final int tableSizeFor(int cap) { int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1); return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;} 複製代碼/<code>因為位運算的執行效率很高，所以在 HashMap 中有很多地方都有應用，最大化地提高了執行速度。-1 的十六進制表示是 0x1111，numberOfLeadingZeros 返回 cap - 1 前面 0 的個數，>>> 是無符號右移運算。以 cap= 16 為例，cap -1 = 0x000F，於是 n = 0x000F，返回 n + 1， 也就是 16,。
擴容操作由 resize() 方法完成，因為代碼要綜合考慮各種情況，所以有很多 if-else 語句，但是這些並不是我們要理解的重點。我們需要知道的是，一般情況下， resize() 主要完成的任務是構造一個新的數組，數組的長度為原數組長度的 2 倍，然後將原數組的節點複製到新數組，最後返回新數組。
<code>final Node[] resize() { Node /<code>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node [] newTab = (Node [])new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode )e).split(this, newTab, j, oldCap); else { // preserve order Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; } 複製代碼
複製過程由 for 循環來完成，其中 e instanceof TreeNode 是用來判斷結點 e 是不是已經被樹形化為紅黑樹結點。
因為數組容量始終是 2 的冪，所以原數組中某個 index 對應的 slot 懸掛的鏈表上的結點，只可能出現在新數組的兩個 slot 中：index 和 index + oldCap。oldCap 表示原數組的長度。相應的，loHead 表示 index 對應的 slot 懸掛的鏈表頭部，hiHead 表示 index + oldCap 對應的 slot 懸掛的鏈表尾部。
在判斷 e 應該放到哪條鏈表的尾部時，也採用了比較討巧的辦法，e.hash & oldCap 如果為 0 就放到 loTail，如果為 1 就放到 hiTail。
6. put() 和 get() 方法
以下面的代碼為例，分析 put() 方法的執行過程。
<code>Student stu21 = new Student(21, "stu21");HashMap<integer> map = new HashMap<>();map.put(stu21.studentID, stu21); 複製代碼/<integer>/<code>
stu21.studentID 是 int 類型，在執行 put() 方法之前，需要進行裝箱，把它轉換為 Integer 類型，這一過程由編譯器自動完成。
<code>public V put(K key, V value) { return putVal(hash(key), key, value, false, true);} 複製代碼/<code>put() 方法中調用了 putVal() 方法。如下所示，其中的 hash() 方法是一個靜態方法。返回的是 key 的哈希值無符號右移 16 位，然後跟自身異或的結果。其目的是為了利用哈希值前 16 位的信息。
<code>static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);} 複製代碼/<code>下面是 putVal() 方法的代碼，HashMap 不允許內部有重複的 key 存在，所以當 put() 方法的參數 key 與已有節點的 key 重複時，默認會將原來的 value 覆蓋。onlyIfAbsent 為 true 表示只有在原來的 value 為 null 的時候才進行覆蓋，此處傳入的是 false，所以新的 value 一定會把原有的 value 覆蓋。
<code>final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } 複製代碼 /<code>雖然代碼有點長，但是 put() 執行的操作也比較簡單，根據 i = hash & (n - 1) 計算出應該存放的 slot 的下標，如果 table[i] 為 null，直接生成新的結點放進去。否則從結點開始往下走，如果哪個節點的 key 和傳入的 key 一樣，就覆蓋掉該結點的 value，直到到達鏈表尾部，生成一個新結點放到最後，這時如果這條鏈表的節點數大於 8，就開始執行樹形化操作。
這裡補充一點，當我們用某個類作為 key 的時候，我們如果重寫了 equals() 方法，應該把 hashCode() 方法也一起重寫了。因為我們需要保證兩個 key 相等的時候，它們的哈希值一定要相等。否則我們就有可能在 HashMap 裡面存儲兩個相等的 key。
get() 方法相對來講就比較簡單了，不做過多解釋。
<code>public V get(Object key) { Node e; return (e = getNode(hash(key), key)) == null ? null : e.value;} 複製代碼 /<code><code>final NodegetNode(int hash, Object key) { Node /<code>[] tab; Node first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode )first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null;}
總結：HashMap 以 “數組 + 鏈表” 的方式實現，其內部以 Node 對象的方式存儲 key-value 鍵值對。數組的長度始終保持為 2 的冪，方便使用位運算提高執行速度。key 的哈希值隨機的條件下，其增刪改查操作的時間複雜度正比於它的負載因子（loadFactor）。當某條鏈表的結點數大於 8 的時候，該鏈表被轉化為一棵紅黑樹。當結點總數大於 threshold 的時候，進行擴容操作，新數組的長度是原數組的兩倍。
閱讀更多 互聯網架構小馬哥 的文章
