基于JDK1.8的HashMap分析
HashMap的強大功能，相信大家都了解一二。之前看過HashMap的源代碼，都是基于JDK1.6的，并且知其然不知其所以然，現在趁著寒假有時間，溫故而知新。文章大概有以下幾個方面：
- HashMap的數據結構
- put方法
- get方法
（一）HashMap的底層數據結構
1 static class Node<K,V> implements Map.Entry<K,V> { 2 final int hash; 3 final K key; 4 V value; 5 Node<K,V> next; 6 7 Node(int hash, K key, V value, Node<K,V> next) { 8 this.hash = hash; 9 this.key = key; 10 this.value = value; 11 this.next = next; 12 } 13 14 public final K getKey() { return key; } 15 public final V getValue() { return value; } 16 public final String toString() { return key + "=" + value; } 17 18 //hashCode等其他代碼 19 }
首先，HashMap 是 Map 的一個實現類，它代表的是一種鍵值對的數據存儲形式。Key 不允許重復出現，Value 隨意。jdk 8 之前，其內部是由數組+鏈表來實現的，而 jdk 8 對于鏈表長度超過 8 的鏈表將轉儲為紅黑樹。
底層數據結構就是 數組 + 鏈表 + 紅黑樹（長度>8），其中有一個靜態內部類
1 static class Node<K,V> implements Map.Entry<K,V>
這個靜態內部類就是一個小的方塊，在jdk1.8之前只在構造方法里面初始化的，現在是在第一次put的時候初始化的。
(二)HashMap的put方法
put 方法的源碼分析是本篇的一個重點，因為通過該方法我們可以窺探到 HashMap 在內部是如何進行數據存儲的，所謂的數組+鏈表+紅黑樹的存儲結構是如何形成的，又是在何種情況下將鏈表轉換成紅黑樹來優化性能的。帶著一系列的疑問，我們看這個 put 方法：
1 public V put(K key, V value) { 2 return putVal(hash(key), key, value, false, true); 3 }
也就是put方法調用了putVal方法，其中傳入一個參數位hash(key)，我們首先來看看hash這個方法。
1 static final int hash(Object key) { 2 int h; 3 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 4 }
是一個靜態final方法。這是為什么key可以位null的原因了，當插入的key值為null，他會自動把他當作0進行處理
并且調用了key的hashcode，這就是為什么map的key一定要重寫hashcode和equals方法。
并且與h右移16位異或。我們來詳細看看這里為什么這樣做。
我們知道，按位異或就是把兩個數按二進制，相同就取0，不同就取1。
比如：0101 ^ 1110 的結果為 1011。異或的速度是非常快的。
把一個數右移16位即丟棄低16為，就是任何小于2^16的數，右移16后結果都為0（2的16次方再右移剛好就是1）。
任何一個數，與0按位異或的結果都是這個數本身（很好驗證）。
所以這個hash()函數對于非null的hash值，僅在其大于等于2^16的時候才會重新調整其值，小于2^16不做調整直接取他的hashcode值。
至于為什么右移16位異或，這是知乎上面的一幅圖片
看到沒有，變得“松散”了很多，至于為什么，我也不是很清楚。我們繼續往下看putVal這個方法。
1 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) { 2 Node<K,V>[] tab; Node<K,V> p; int n, i; 3 //如果 table 還未被初始化，那么初始化它 4 if ((tab = table) == null || (n = tab.length) == 0) 5 n = (tab = resize()).length; 6 //根據鍵的 hash 值找到該鍵對應到數組中存儲的索引 7 //如果為 null，那么說明此索引位置并沒有被占用 8 if ((p = tab[i = (n - 1) & hash]) == null) 9 tab[i] = newNode(hash, key, value, null); 10 //不為 null，說明此處已經被占用，只需要將構建一個節點插入到這個鏈表的尾部即可 11 else { 12 Node<K,V> e; K k; 13 //當前結點和將要插入的結點的 hash 和 key 相同，說明這是一次修改操作 14 if (p.hash == hash && 15 ((k = p.key) == key || (key != null && key.equals(k)))) 16 e = p; 17 //如果 p 這個頭結點是紅黑樹結點的話，以紅黑樹的插入形式進行插入 18 else if (p instanceof TreeNode) 19 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 20 //遍歷此條鏈表，將構建一個節點插入到該鏈表的尾部 21 else { 22 for (int binCount = 0; ; ++binCount) { 23 if ((e = p.next) == null) { 24 p.next = newNode(hash, key, value, null); 25 //如果插入后鏈表長度大于等于 8 ，將鏈表裂變成紅黑樹 26 if (binCount >= TREEIFY_THRESHOLD - 1) 27 treeifyBin(tab, hash); 28 break; 29 } 30 //遍歷的過程中，如果發現與某個結點的 hash和key，這依然是一次修改操作 31 if (e.hash == hash && 32 ((k = e.key) == key || (key != null && key.equals(k)))) 33 break; 34 p = e; 35 } 36 } 37 //e 不是 null，說明當前的 put 操作是一次修改操作并且e指向的就是需要被修改的結點 38 if (e != null) { 39 V oldValue = e.value; 40 if (!onlyIfAbsent || oldValue == null) 41 e.value = value; 42 afterNodeAccess(e); 43 return oldValue; 44 } 45 } 46 ++modCount; 47 //如果添加后，數組容量達到閾值，進行擴容 48 if (++size > threshold) 49 resize(); 50 afterNodeInsertion(evict); 51 return null; 52 }
注釋已經很清楚了，我想說下這個初始化的問題
//如果 table 還未被初始化，那么初始化它 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;
這個resize()方法既可以初始化，也可以擴容，都是這個函數完成的。并且在多線程下，不會出現之前的死鎖導致cpu飆升至100%，只會出現數據丟失的問題。
首先，我們看 resize 這個方法是如何對 table 進行初始化的
1 //第一部分 2 final Node<K,V>[] resize() { 3 Node<K,V>[] oldTab = table; 4 //拿到舊數組的長度 5 int oldCap = (oldTab == null) ? 0 : oldTab.length; 6 int oldThr = threshold; 7 int newCap, newThr = 0; 8 //說明舊數組已經被初始化完成了，此處需要給舊數組擴容 9 if (oldCap > 0) { 10 //極限的限定，達到容量限定的極限將不再擴容 11 if (oldCap >= MAXIMUM_CAPACITY) { 12 threshold = Integer.MAX_VALUE; 13 return oldTab; 14 } 15 //未達到極限，將數組容量擴大兩倍，閾值也擴大兩倍 16 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 17 oldCap >= DEFAULT_INITIAL_CAPACITY) 18 newThr = oldThr << 1; 19 } 23 else if (oldThr > 0) 24 newCap = oldThr; 25 //數組未初始化并且閾值也為0，說明一切都以默認值進行構造 26 else { 27 newCap = DEFAULT_INITIAL_CAPACITY; 28 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 29 } 32 if (newThr == 0) { 33 float ft = (float)newCap * loadFactor; 34 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 35 (int)ft : Integer.MAX_VALUE); 36 } 37 threshold = newThr; 38 //根據新的容量初始化一個數組 39 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; 40 table = newTab; 41 //舊數組不為 null，這次的 resize 是一次擴容行為 42 if (oldTab != null) { 43 //將舊數組中的每個節點位置相對靜止地拷貝值新數組中 44 for (int j = 0; j < oldCap; ++j) { 45 Node<K,V> e; 46 //獲取頭結點 47 if ((e = oldTab[j]) != null) { 48 oldTab[j] = null; 49 //說明鏈表或者紅黑樹只有一個頭結點，轉移至新表 50 if (e.next == null) 51 newTab[e.hash & (newCap - 1)] = e; 52 //如果 e 是紅黑樹結點，紅黑樹分裂，轉移至新表 53 else if (e instanceof TreeNode) 54 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 55 //這部分是將鏈表中的各個節點原序地轉移至新表中 56 else { 57 Node<K,V> loHead = null, loTail = null;// 代表原來的地方 58 Node<K,V> hiHead = null, hiTail = null;// 代表高位 59 Node<K,V> next; 60 do { 61 next = e.next;
62 if ((e.hash & oldCap) == 0) { // 以oldCap來區分將數據放到原來的地方還是放到高位 63 if (loTail == null) 64 loHead = e; 65 else 66 loTail.next = e; 67 loTail = e; 68 } 69 else { 70 if (hiTail == null) 71 hiHead = e; 72 else 73 hiTail.next = e; 74 hiTail = e; 75 } 76 } while ((e = next) != null); 77 if (loTail != null) { 78 loTail.next = null; 79 newTab[j] = loHead; 80 } 81 if (hiTail != null) { 82 hiTail.next = null; 83 newTab[j + oldCap] = hiHead; 84 } 85 } 86 } 87 } 88 } 89 //不論你是擴容還是初始化，都可以返回 newTab 90 return newTab;
JDK大神真的是太厲害了，膜拜啊膜拜。
將沖突多的，比如鏈表或者紅黑樹，放到擴容后的那一半，那么以后沖突就會減少很多。
就是判斷舊的數組那一位到底為不為一。比如4(0100)，只要第二位為1，全部放到highHead那里，否則lowHead.
我們看上面代碼的第62行
這個oldCap表示擴容之前數組的長度，一定是為2的倍數。即二進制中只有一位為1，其他位都位0
1 if ((e.hash & oldCap) == 0)
如果原 oldCap 為 10000 的話，那么擴容后的 newCap 則為 100000，會比原來多出一位。所以我們只要知道原索引值的前一位是 0 還是 1 即可，如果是 0，那么它和新容量與后還是 0 并不改變索引的值，如果是 1 的話，那么索引值會增加 oldCap。
這樣就分兩步拆分當前鏈表，一條鏈表是不需要移動的，依然保存在當前索引值的結點上，另一條則需要變動到 index + oldCap 的索引位置上。
既假如原數組前一位是0那么還是原index位置，否則就是兩倍。
這一塊真的寫的很好，如下圖擴容
table[1] = 1 -> 5 -> 9 -> 13
擴容后，1，9留在了原來的地方、
5，13去了高位 table[5] = 1 + 4
至此，put方法就差不多了。可以詳細的看下代碼的注釋，結合jdk來理解。
ps. 我其實看的時候有一個疑問。為何不把沖突的全部放到擴容的另外一半呢。這也許就是JDK1.8的新特性吧
我去網上找了找1.8之前的擴容，就是把鏈表全部放進后面。
所以會產生死循環。而你1.8以后，分成了兩個，肯定不會出現指向同一個元素，所以不會出現死循環。
不過我覺得這是一個雞肋，HashMap線程不安全，沒必要考慮這些。
將沖突多的全部放到擴容后的另外一半，我覺得是最好的。(只是個人建議哈)
(三)HashMap的get方法
相對于put方法，get方法就簡單很多了。
public V get(Object key) { Node<K,V> e; //直接調用了getNode() return (e = getNode(hash(key), key)) == null ? null : e.value; }
1 final Node<K,V> getNode(int hash, Object key) { 2 Node<K,V>[] tab; Node<K,V> first, e; int n; K k; 3 //先判斷數組是否為空，長度是否大于0，那個node節點是否存在 4 if ((tab = table) != null && (n = tab.length) > 0 && 5 (first = tab[(n - 1) & hash]) != null) { 6 //如果找到，直接返回 7 if (first.hash == hash && // always check first node 8 ((k = first.key) == key || (key != null && key.equals(k)))) 9 return first; 10 if ((e = first.next) != null) { 11 //如果是紅黑樹，去紅黑樹找 12 if (first instanceof TreeNode) 13 return ((TreeNode<K,V>)first).getTreeNode(hash, key); 14 //鏈表找 15 do { 16 if (e.hash == hash && 17 ((k = e.key) == key || (key != null && key.equals(k)))) 18 return e; 19 } while ((e = e.next) != null); 20 } 21 } 22 return null; 23 }
總結：
終于寫完了，也是自己的第一篇博文，寫了自己比較熟悉的HashMap，花了自己挺久的時間。
之前一直在github wenbochang888 上面寫，發覺排版很是麻煩，所以來到了博客園，博客園也是我經常逛的博客之一，沒有廣告，博文質量高，反正就是非常的喜歡。
希望自己可以堅持下去，無聊就去寫寫，沒有必要說一天幾篇，幾天幾篇什么的，自己開心就好。
自己文筆不好，很多東西表達不出來，望見諒。
浙公網安備 33010602011771號