关于上上文hashmap的深入-hashmap产生死锁的详解
一、HashMap 的底層實現?
這個可以參考上一篇文章：HashMap 源碼剖析，具體介紹了 HashMap 的底層實現：
數組：充當索引?
鏈表：處理碰撞
簡單地說一下：
HashMap通常會用一個指針數組（假設為 table[]）來做分散所有的 key，當一個 key 被加入時，會通過 Hash 算法通過 key 算出這個數組的下標 i，然后就把這個 key, value 插到 table[i]中，如果有兩個不同的 key 被算在了同一個 i，那么就叫沖突，又叫碰撞，這樣會在 table[i]上形成一個鏈表。
我們知道，如果 table[]的尺寸很小，比如只有2個，如果要放進10個 keys 的話，那么碰撞非常頻繁，于是一個 O(1)的查找算法，就變成了鏈表遍歷，性能變成了 O(n)，這是 Hash 表的缺陷。
所以，Hash 表的尺寸和容量非常的重要。一般來說，Hash 表這個容器當有數據要插入時，都會檢查容量有沒有超過設定的 thredhold，如果超過，需要增大 Hash 表的尺寸，但是這樣一來，整個 Hash 表里的無素都需要被重算一遍。這叫 rehash，這個成本相當的大。
二、源碼剖析?
首先來猜下，神馬情況會造成死鎖呢？
我們知道，如果要造成死循環，肯定和鏈表鏈表有關，因為只有鏈表才有指針。但是在源碼剖析中我們知道，每次添加元素都是在鏈表頭部添加元素，怎么會造成死鎖呢？
其實，關鍵就在于rehash過程。在前面我們說了是 HashMap 的get()方法造成的死鎖。既然是 get()造成的死鎖，一定是跟put()進去元素的位置有關，所以我們從 put()方法開始看起。
1 public V put(K key, V value) {2 if (table == EMPTY_TABLE) {3 inflateTable(threshold);4 }5 if (key == null)6 return putForNullKey(value);7 int hash = hash(key);8 int i = indexFor(hash, table.length);9 //如果該 key 存在，就替換舊值 10 for (Entry<K,V> e = table[i]; e != null; e = e.next) { 11 Object k; 12 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 13 V oldValue = e.value; 14 e.value = value; 15 e.recordAccess(this); 16 return oldValue; 17 } 18 } 19 20 modCount++; 21 //如果沒有這個 key，就插入一個新元素！跟進去看看 22 addEntry(hash, key, value, i); 23 return null; 24 } 25 26 void addEntry(int hash, K key, V value, int bucketIndex) { 27 //查看當前的size是否超過了我們設定的閾值threshold，如果超過，需要resize 28 if ((size >= threshold) && (null != table[bucketIndex])) { 29 resize(2 * table.length); 30 hash = (null != key) ? hash(key) : 0; 31 bucketIndex = indexFor(hash, table.length); 32 } 33 34 createEntry(hash, key, value, bucketIndex); 35 } 36 37 //新建一個更大尺寸的hash表，把數據從老的Hash表中遷移到新的Hash表中。 38 void resize(int newCapacity) { 39 Entry[] oldTable = table; 40 int oldCapacity = oldTable.length; 41 if (oldCapacity == MAXIMUM_CAPACITY) { 42 threshold = Integer.MAX_VALUE; 43 return; 44 } 45 46 //創建一個新的 Hash 表 47 Entry[] newTable = new Entry[newCapacity]; 48 //轉移！！！！跟進去 49 transfer(newTable, initHashSeedAsNeeded(newCapacity)); 50 table = newTable; 51 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); 52 } 53 54 //高能預警！！！！重點全在這個函數中 55 void transfer(Entry[] newTable, boolean rehash) { 56 int newCapacity = newTable.length; 57 for (Entry<K,V> e : table) { 58 while(null != e) { 59 Entry<K,V> next = e.next; 60 if (rehash) { 61 e.hash = null == e.key ? 0 : hash(e.key); 62 } 63 int i = indexFor(e.hash, newCapacity); 64 e.next = newTable[i]; 65 newTable[i] = e; 66 e = next; 67 } 68 } 69 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
看到最后這個函數transfer()，就算到達了問題的關鍵。我們先大概看下它的意思：
經過這幾步，我們會發現轉移的時候是逆序的。假如轉移前鏈表順序是1->2->3，那么轉移后就會變成3->2->1。這時候就有點頭緒了，死鎖問題不就是因為1->2的同時2->1造成的嗎？所以，HashMap 的死鎖問題就出在這個transfer()函數上。
三、單線程 rehash 詳細演示?
單線程情況下，rehash 不會出現任何問題：
假設hash算法就是最簡單的 key mod table.length（也就是數組的長度）。?
最上面的是old hash 表，其中的Hash表的 size = 2, 所以 key = 3, 7, 5，在 mod 2以后碰撞發生在 table[1]接下來的三個步驟是 Hash表 resize 到4，并將所有的 key,value 重新rehash到新 Hash 表的過程?
如圖所示：
四、多線程 rehash 詳細演示?
首先我們把關鍵代碼貼出來，如果在演示過程中忘了該執行哪一步，就退回來看看：
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
上面代碼就是重中之重，不過我們可以再簡化一下，因為中間的 i 就是判斷新表的位置，我們可以跳過。簡化后代碼：
1 while(null != e) { 2 Entry<K,V> next = e.next; 3 e.next = newTable[i]; 4 newTable[i] = e; 5 e = next; 6 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
去掉了一些與本過程冗余的代碼，意思就非常清晰了：
Entry<K,V> next = e.next;- 1
- 2
——因為是單鏈表，如果要轉移頭指針，一定要保存下一個結點，不然轉移后鏈表就丟了
e.next = newTable[i];- 1
- 2
——e 要插入到鏈表的頭部，所以要先用 e.next 指向新的 Hash 表第一個元素（為什么不加到新鏈表最后？因為復雜度是 O（N））
newTable[i] = e;- 1
- 2
——現在新 Hash 表的頭指針仍然指向 e 沒轉移前的第一個元素，所以需要將新 Hash 表的頭指針指向 e
e = next- 1
- 2
——轉移 e 的下一個結點?
好了，代碼層面已經全部 ok，下面開始演示：
假設這里有兩個線程同時執行了put()操作，并進入了transfer()環節?
粉紅色代表線程1，淺藍色代碼線程2?
1. 初始狀態?
現在假設線程1的工作情況如下代碼所示，而線程2完成了整個transfer()過程，所以就完成了 rehash。
- 1
- 2
- 3
- 4
- 5
- 6
- 7
那么現在的狀態為：?
從上面的圖我們可以看到，因為線程1的 e 指向了 key(3)，而 next 指向了 key(7)，在線程2 rehash 后，就指向了線程2 rehash 后的鏈表。
第一步?
然后線程1被喚醒了：
執行e.next = newTable[i]，于是 key(3)的 next 指向了線程1的新 Hash 表，因為新 Hash 表為空，所以e.next = null，
執行e = next，將 e 指向 next，所以新的 e 是 key(7)?
狀態圖為：?
第二步?
然后該執行 key(3)的 next 節點 key(7)了:
現在的 e 節點是 key(7)，首先執行Entry<K,V> next = e.next?,那么 next 就是 key(3)了
執行e = next，將 e 指向 next，所以新的 e 是 key(3)?
這時候的狀態圖為：?
第三步?
然后又該執行 key(7)的 next 節點 key(3)了：
現在的 e 節點是 key(3)，首先執行Entry<K,V> next = e.next,那么 next 就是 null
這時候的狀態如圖所示：?
很明顯，環形鏈表出現了！！當然，現在還沒有事情，因為下一個節點是 null，所以transfer()就完成了，等put()的其余過程搞定后，HashMap 的底層實現就是線程1的新 Hash 表了。
沒錯，put()過程雖然造成了環形鏈表，但是它沒有發生錯誤。它靜靜的等待著get()這個冤大頭的到來。
現在程序被執行了一個hashMap.get(11)，這時候會調用getEntry()，這個函數就是去找對應索引的鏈表中有沒有這個 key。然后。。。。悲劇了。。。Infinite Loop~~
五、啟示?
通過上面的講解，我們就弄明白了 HashMap 死鎖的原因，其實在很久以前這個 Bug 就被提交給了 Sun，但是 Sun 認為這不是一個 Bug，因為文檔中明確說了 HashMap 不是線程安全的。要并發就使用 ConcurrentHashMap。
因為 HashMap 為了性能考慮，沒有使用鎖機制。所以就是非線程安全的，而 ConcurrentHashMap 使用了鎖機制，所以是線程安全的。當然，要知其然知其所以然。最好是去看一下 ConcurrentHashMap 是如何實現鎖機制的（其實是分段鎖，不然所有的 key 在鎖的時候都無法訪問）。就像侯捷在《STL 源碼剖析》中說的：
源碼面前，了無秘密。?
對我們的啟示在前面的文章踩坑記中就提到過：
使用新類、新函數時，一定一定要過一遍文檔?
不要望文生義或者憑直覺“猜”，不然坑的不僅僅是自己。
轉自：http://github.thinkingbar.com/hashmap-infinite-loop/
總結
以上是生活随笔為你收集整理的关于上上文hashmap的深入-hashmap产生死锁的详解的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： selenium之 chromedriv
- 下一篇： 深入研究 Java Synchroniz