本篇隨筆主要描述的是我閱讀 HashMap 源碼期間的對於 HashMap 的一些實現上的個人理解，用於個人備忘，有不對的地方，請指出～ 接下來會從以下幾個方面介紹 HashMap 源碼相關知識： 1、HashMap 存儲結構 2、HashMap 各常量、成員變數作用 3、HashMap 幾種構造方 ...
本篇隨筆主要描述的是我閱讀 HashMap 源碼期間的對於 HashMap 的一些實現上的個人理解，用於個人備忘，有不對的地方，請指出～
接下來會從以下幾個方面介紹 HashMap 源碼相關知識：
1、HashMap 存儲結構
2、HashMap 各常量、成員變數作用
3、HashMap 幾種構造方法
4、HashMap put 及其相關方法
5、HashMap get 及其相關方法
6、HashMap remove 及其相關方法（暫未理解透徹）
7、HashMap 擴容方法 resize()
介紹方法時會包含方法實現相關細節。
先來看一下 HashMap 的繼承圖：
HashMap 根據鍵的 hashCode 值存儲數據，大多數情況下可以直接定位到它的值，因而具有很快的訪問速度，但遍歷順序卻是不確定的。 HashMap 最多只允許一條記錄的鍵為 null ，允許多條記錄的值為 null 。HashMap 非線程安全，即任一時刻可以有多個線程同時寫 HashMap，可能會導致數據的不一致。如果需要滿足線程安全，可以用 Collections的synchronizedMap 方法使 HashMap 具有線程安全的能力，或者使用ConcurrentHashMap 。
一、HashMap 存儲結構
HashMap是數組+鏈表+紅黑樹（JDK1.8增加了紅黑樹部分）實現的，如下圖所示：
源碼中具體實現如下：
1 // Node<K,V> 類用來實現數組及鏈表的數據結構 2 static class Node<K,V> implements Map.Entry<K,V> { 3 final int hash; //保存節點的 hash 值 4 final K key; //保存節點的 key 值 5 V value; //保存節點的 value 值 6 Node<K,V> next; //指向鏈表結構下的當前節點的 next 節點，紅黑樹 TreeNode 節點中也有用到 7 8 Node(int hash, K key, V value, Node<K,V> next) { 9 this.hash = hash; 10 this.key = key; 11 this.value = value; 12 this.next = next; 13 } 14 15 public final K getKey() { } 16 public final V getValue() { } 17 public final String toString() { } 18 19 public final int hashCode() { 20 } 21 22 public final V setValue(V newValue) { 23 } 24 25 public final boolean equals(Object o) { 26 } 27 } 28 29 public class LinkedHashMap<K,V> { 30 static class Entry<K,V> extends HashMap.Node<K,V> { 31 Entry<K,V> before, after; 32 Entry(int hash, K key, V value, Node<K,V> next) { 33 super(hash, key, value, next); 34 } 35 } 36 } 37 38 // TreeNode<K,V> 繼承 LinkedHashMap.Entry<K,V>，用來實現紅黑樹相關的存儲結構 39 static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { 40 TreeNode<K,V> parent; // 存儲當前節點的父節點 41 TreeNode<K,V> left; //存儲當前節點的左孩子 42 TreeNode<K,V> right; //存儲當前節點的右孩子 43 TreeNode<K,V> prev; // 存儲當前節點的前一個節點 44 boolean red; // 存儲當前節點的顏色（紅、黑） 45 TreeNode(int hash, K key, V val, Node<K,V> next) { 46 super(hash, key, val, next); 47 } 48 49 final TreeNode<K,V> root() { 50 } 51 52 static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) { 53 } 54 55 final TreeNode<K,V> find(int h, Object k, Class<?> kc) { 56 } 57 58 final void treeify(Node<K,V>[] tab) { 59 } 60 61 final Node<K,V> untreeify(HashMap<K,V> map) { 62 } 63 64 final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, 65 int h, K k, V v) { 66 } 67 68 final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, 69 boolean movable) { 70 } 71 72 final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) { 73 } 74 75 /* ------------------------------------------------------------ */ 76 // Red-black tree methods, all adapted from CLR 77 // 紅黑樹相關操作 78 static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, 79 TreeNode<K,V> p) { 80 } 81 82 static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, 83 TreeNode<K,V> p) { 84 } 85 86 static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, 87 TreeNode<K,V> x) { 88 } 89 90 static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root, 91 TreeNode<K,V> x) { 92 } 93 94 static <K,V> boolean checkInvariants(TreeNode<K,V> t) { 95 } 96 97 }
二、HashMap 各常量、成員變數作用
1 //創建 HashMap 時未指定初始容量情況下的預設容量 2 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 3 4 //HashMap 的最大容量 5 static final int MAXIMUM_CAPACITY = 1 << 30; 6 7 //HashMap 預設的裝載因數,當 HashMap 中元素數量超過 容量*裝載因數 時，進行 resize() 操作 8 static final float DEFAULT_LOAD_FACTOR = 0.75f; 9 10 //用來確定何時將解決 hash 衝突的鏈表轉變為紅黑樹 11 static final int TREEIFY_THRESHOLD = 8; 12 13 // 用來確定何時將解決 hash 衝突的紅黑樹轉變為鏈表 14 static final int UNTREEIFY_THRESHOLD = 6; 15 16 /* 當需要將解決 hash 衝突的鏈表轉變為紅黑樹時，需要判斷下此時數組容量，若是由於數組容量太小（小於 MIN_TREEIFY_CAPACITY ）導致的 hash 衝突太多，則不進行鏈表轉變為紅黑樹操作，轉為利用 resize() 函數對 hashMap 擴容 */ 17 static final int MIN_TREEIFY_CAPACITY = 64;
1 //保存Node<K,V>節點的數組 2 transient Node<K,V>[] table; 3 4 //由 hashMap 中 Node<K,V> 節點構成的 set 5 transient Set<Map.Entry<K,V>> entrySet; 6 7 //記錄 hashMap 當前存儲的元素的數量 8 transient int size; 9 10 //記錄 hashMap 發生結構性變化的次數（註意 value 的覆蓋不屬於結構性變化） 11 transient int modCount; 12 13 //threshold的值應等於 table.length * loadFactor, size 超過這個值時進行 resize()擴容 14 int threshold; 15 16 //記錄 hashMap 裝載因數 17 final float loadFactor;
三、HashMap 幾種構造方法
1 //構造方法１，指定初始容量及裝載因數 2 public HashMap(int initialCapacity, float loadFactor) { 3 if (initialCapacity < 0) 4 throw new IllegalArgumentException("Illegal initial capacity: " + 5 initialCapacity); 6 if (initialCapacity > MAXIMUM_CAPACITY) 7 initialCapacity = MAXIMUM_CAPACITY; 8 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 9 throw new IllegalArgumentException("Illegal load factor: " + 10 loadFactor); 11 this.loadFactor = loadFactor; 12 /* tableSizeFor(initialCapacity) 方法返回的值是最接近 initialCapacity 的2的冪，若指定初始容量為９，則實際 hashMap 容量為16*/ 13 //註意此種方法創建的 hashMap 初始容量的值存在 threshold 中 14 this.threshold = tableSizeFor(initialCapacity); 15 } 16 //tableSizeFor(initialCapacity) 方法返回的值是最接近 initialCapacity 的2的冪 17 static final int tableSizeFor(int cap) { 18 int n = cap - 1; 19 n |= n >>> 1;// >>> 代表無符號右移 20 n |= n >>> 2; 21 n |= n >>> 4; 22 n |= n >>> 8; 23 n |= n >>> 16; 24 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 25 } 26 //構造方法２，僅指定初始容量，裝載因數的值採用預設的 0.75 27 public HashMap(int initialCapacity) { 28 this(initialCapacity, DEFAULT_LOAD_FACTOR); 29 } 30 //構造方法３，所有參數均採用預設值 31 public HashMap() { 32 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted 33 }
四、HashMap put 及其相關方法
這部分我覺得是 hashMap 中比較重要的代碼，介紹如下：
1 //指定節點 key,value，向 hashMap 中插入節點 2 public V put(K key, V value) { 3 //註意待插入節點 hash 值的計算，調用了 hash(key) 函數 4 //實際調用 putVal（）進行節點的插入 5 return putVal(hash(key), key, value, false, true); 6 } 7 static final int hash(Object key) { 8 int h; 9 /*key 的 hash 值的計算是通過hashCode()的高16位異或低16位實現的：(h = k.hashCode()) ^ (h >>> 16)，主要是從速度、功效、質量來考慮的，這麼做可以在數組table的length比較小的時候，也能保證考慮到高低Bit都參與到Hash的計算中，同時不會有太大的開銷*/ 10 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 11 } 12 13 public void putAll(Map<? extends K, ? extends V> m) { 14 putMapEntries(m, true); 15 } 16 17 /*把Map<? extends K, ? extends V> m 中的元素插入到 hashMap 中,若 evict 為 false,代表是在創建 hashMap 時調用了這個函數，例如利用上述構造函數３創建 hashMap;若 evict 為true,代表是在創建 hashMap 後才調用這個函數，例如上述的 putAll 函數。*/ 18 19 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { 20 int s = m.size(); 21 if (s > 0) { 22 /*如果是在創建 hashMap 時調用的這個函數則 table 一定為空*/ 23 if (table == null) { 24 //根據待插入的map 的 size 計算要創建的 hashMap 的容量。 25 float ft = ((float)s / loadFactor) + 1.0F; 26 int t = ((ft < (float)MAXIMUM_CAPACITY) ? 27 (int)ft : MAXIMUM_CAPACITY); 28 //把要創建的 hashMap 的容量存在 threshold 中 29 if (t > threshold) 30 threshold = tableSizeFor(t); 31 } 32 //判斷待插入的 map 的 size,若 size 大於 threshold，則先進行 resize() 33 else if (s > threshold) 34 resize(); 35 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { 36 K key = e.getKey(); 37 V value = e.getValue(); 38 //實際也是調用 putVal 函數進行元素的插入 39 putVal(hash(key), key, value, false, evict); 40 } 41 } 42 } 43 44 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 45 boolean evict) { 46 Node<K,V>[] tab; Node<K,V> p; int n, i; 47 if ((tab = table) == null || (n = tab.length) == 0) 48 n = (tab = resize()).length; 49 /*根據 hash 值確定節點在數組中的插入位置，若此位置沒有元素則進行插入，註意確定插入位置所用的計算方法為 (n - 1) & hash,由於 n 一定是２的冪次，這個操作相當於 50 hash % n */ 51 if ((p = tab[i = (n - 1) & hash]) == null) 52 tab[i] = newNode(hash, key, value, null); 53 else {//說明待插入位置存在元素 54 Node<K,V> e; K k; 55 //比較原來元素與待插入元素的 hash 值和 key 值 56 if (p.hash == hash && 57 ((k = p.key) == key || (key != null && key.equals(k)))) 58 e = p; 59 //若原來元素是紅黑樹節點，調用紅黑樹的插入方法:putTreeVal 60 else if (p instanceof TreeNode) 61 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 62 else {//證明原來的元素是鏈表的頭結點，從此節點開始向後尋找合適插入位置 63 for (int binCount = 0; ; ++binCount) { 64 if ((e = p.next) == null) { 65 //找到插入位置後，新建節點插入 66 p.next = newNode(hash, key, value, null); 67 //若鏈表上節點超過TREEIFY_THRESHOLD - 1，將鏈表變為紅黑樹 68 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 69 treeifyBin(tab, hash); 70 break; 71 } 72 if (e.hash == hash && 73 ((k = e.key) == key || (key != null && key.equals(k)))) 74 break; 75 p = e; 76 } 77 }//end else 78 if (e != null) { // 待插入元素在 hashMap 中已存在 79 V oldValue = e.value; 80 if (!onlyIfAbsent || oldValue == null) 81 e.value = value; 82 afterNodeAccess(e); 83 return oldValue; 84 } 85 }//end else 86 ++modCount; 87 if (++size > threshold) 88 resize(); 89 afterNodeInsertion(evict); 90 return null; 91 }//end putval
1 /*讀懂這個函數要註意理解 hash 衝突發生的幾種情況 2 １、兩節點 key 值相同（hash值一定相同），導致衝突 3 ２、兩節點 key 值不同，由於 hash 函數的局限性導致hash 值相同，衝突 4 ３、兩節點 key 值不同，hash 值不同，但 hash 值對數組長度取模後相同，衝突 5 */ 6 final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, 7 int h, K k, V v) { 8 Class<?> kc = null; 9 boolean searched = false; 10 TreeNode<K,V> root = (parent != null) ? root() : this; 11 //從根節點開始查找合適的插入位置（與二叉搜索樹查找過程相同） 12 for (TreeNode<K,V> p = root;;) { 13 int dir, ph; K pk; 14 if ((ph = p.hash) > h) 15 dir = -1; // dir小於０，接下來查找當前節點左孩子 16 else if (ph < h) 17 dir = 1; // dir大於０，接下來查找當前節點右孩子 18 else if ((pk = p.key) == k || (pk != null && k.equals(pk))) 19 //進入這個else if 代表 hash 值相同，key 相同 20 return p; 21 /*要進入下麵這個else if,代表有以下幾個含義: 22 1、當前節點與待插入節點 key 不同, hash 值相同 23 2、ｋ是不可比較的，即ｋ並未實現 comparable<K> 介面
（若 k 實現了comparable<K> 介面，comparableClassFor（k）返回的是ｋ的 class,而不是 null） 24 或者 compareComparables(kc, k, pk) 返回值為 0
(pk 為空 或者 按照 k.compareTo(pk) 返回值為０，
返回值為０可能是由於 ｋ的compareTo 方法實現不當引起的，compareTo 判定相等，而上個 else if 中 equals 判定不等)*/ 25 else if ((kc == null && 26 (kc = comparableClassFor(k)) == null) || 27 (dir = compareComparables(kc, k, pk)) == 0) { 28 //在以當前節點為根的整個樹上搜索是否存在待插入節點（只會搜索一次） 29 if (!searched) { 30 TreeNode<K,V> q, ch; 31 searched = true; 32 if (((ch = p.left) != null && 33 (q = ch.find(h, k, kc)) != null) || 34 ((ch = p.right) != null && 35 (q = ch.find(h, k, kc)) != null)) 36 //若樹中存在待插入節點，直接返回 37 return q; 38 } 39 // 既然ｋ是不可比較的，那我自己指定一個比較方式 40 dir = tieBreakOrder(k, pk); 41 }//end else if 42 43 TreeNode<K,V> xp = p; 44 if ((p = (dir <= 0) ? p.left : p.right) == null) { 45 //找到了待插入的位置，xp 為待插入節點的父節點 46 //註意TreeNode節點中既存在樹狀關係，也存在鏈式關係，並且是雙端鏈表 47 Node<K,V> xpn = xp.next; 48 TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn); 49 if (dir <= 0) 50 xp.left = x; 51 else 52 xp.right = x; 53 xp.next = x; 54 x.parent = x.prev = xp; 55 if (xpn != null) 56 ((TreeNode<K,V>)xpn).prev = x; 57 //插入節點後進行二叉樹的平衡操作 58 moveRootToFront(tab, balanceInsertion(root, x)); 59 return null; 60 } 61 }//end for 62 }//end putTreeVal 63 64 static int tieBreakOrder(Object a, Object b) { 65 int d; 66 //System.identityHashCode()實際是利用對象 a,b 的記憶體地址進行比較 67 if (a == null || b == null || 68 (d = a.getClass().getName(). 69 compareTo(b.getClass().getName())) == 0) 70 d = (System.identityHashCode(a) <= System.identityHashCode(b) ? 71 -1 : 1); 72 return d; 73 }
五、HashMap get 及其相關方法
1 public V get(Object key) { 2 Node<K,V> e; 3 //實際上是根據輸入節點的 hash 值和 key 值利用getNode 方法進行查找 4 return (e = getNode(hash(key), key)) == null ? null : e.value; 5 } 6 7 final Node<K,V> getNode(int hash, Object key) { 8 Node<K,V>[] tab; Node<K,V> first, e; int n; K k; 9 if ((tab = table) != null && (n = tab.length) > 0 && 10 (first = tab[(n - 1) & hash]) != null) { 11 if (first.hash == hash && // always check first node 12 ((k = first.key) == key || (key != null && key.equals(k)))) 13 return first; 14 if ((e = first.next) != null) { 15 if (first instanceof TreeNode) 16 //若定位到的節點是 TreeNode 節點，則在樹中進行查找 17 return ((TreeNode<K,V>)first).getTreeNode(hash, key); 18 do {//否則在鏈表中進行查找 19 if (e.hash == hash && 20 ((k = e.key) == key || (key != null && key.equals(k)))) 21 return e; 22 } while ((e = e.next) != null); 23 } 24 } 25 return null; 26 }
1 final TreeNode<K,V> getTreeNode(int h, Object k) { 2 //從根節點開始，調用 find 方法進行查找 3 return ((parent != null) ? root() : this).find(h, k, null); 4 } 5 6 final TreeNode<K,V> find(int h, Object k, Class<?> kc) { 7 TreeNode<K,V> p = this; 8 do { 9 int ph, dir; K pk; 10 TreeNode<K,V> pl = p.left, pr = p.right, q; 11 //首先進行hash 值的比較，若不同令當前節點變為它的左孩子或者右孩子 12 if ((ph = p.hash) > h) 13 p = pl; 14 else if (ph < h) 15 p = pr; 16 //hash 值相同，進行 key 值的比較 17 else if ((pk = p.key) == k || (k != null && k.equals(pk))) 18 return p; 19 else if (pl == null) 20 p = pr; 21 else if (pr == null) 22 p = pl; 23 //執行到這兒，意味著hash 值相同，key 值不同 24 //若k 是可比較的並且k.compareTo(pk) 返回結果不為０可進入下麵elseif 25 else if ((kc != null || 26 (kc = comparableClassFor(k)) != null) && 27 (dir = compareComparables(kc, k, pk)) != 0) 28 p = (dir < 0) ? pl : pr; 29 /*若 k 是不可比較的 或者 k.compareTo(pk) 返回結果為０則在整棵樹中進行查找，先找右子樹，右子樹沒有再找左子樹*/ 30 else if ((q = pr.find(h, k, kc)) != null) 31 return q; 32 else 33 p = pl; 34 } while (p != null); 35 return null; 36 }
七、HashMap 擴容方法 resize()
resize() 方法中比較重要的是鏈表和紅黑樹的 rehash 操作，先來說下 rehash 的實現原理：
我們在擴容的時候，一般是把長度擴為原來2倍，所以，元素的位置要麼是在原位置，要麼是在原位置再移動2次冪的位置。看下圖可以明白這句話的意思，n為table的長度，圖（a）表示擴容前的key1和key2兩種key確定索引位置的示例，圖（b）表示擴容後key1和key2兩種key確定索引位置的示例，其中hash1是key1對應的哈希與高位運算結果。
元素在重新計算hash之後，因為n變為2倍，那麼n-1的mask範圍在高位多1bit(紅色)，因此新的index就會發生這樣的變化：
因此，我們在擴充HashMap的時候，只需要看看原來的hash值新增的那個bit是1還是0就好了，是0的話索引沒變，是1的話索引變成“原索引+oldCap”，可以看看下圖為16擴充為32的resize示意圖：
