結合一些文章閱讀源碼後整理的Java容器常見知識點。對於一些代碼細節，本文不展開來講，有興趣可以自行閱讀參考文獻。

1. 思維導圖

各個容器的知識點比較分散，沒有在思維導圖上體現，因此看上去右半部分很像類的繼承關係。

2. 容器對比

操作的時間複雜度

• ArrayList下標查找O(1)，插入O(n)
• 涉及到樹，查找和插入都可以看做log(n)
• 鏈表查找O(n)，插入O(1)
• Hash直接查找hash值為 O(1)

註1：關於容器的線程安全

複合操作

無論是Vetcor還是SynchronizedCollection甚至是ConcurrentHashMap，複合操作都不是線程安全的。如下麵的代碼^[1]在併發環境中可能會不符合預期：

if (!vector.contains(element)) 
    vector.add(element); 
    ...
}

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap();
map.put("key", 1);

// 多線程環境下執行
Integer currentVal = map.get("key");
map.put("key", currentVal + 1);

在複合操作的場景下，通用解法是對容器加鎖，但這樣會大幅降低性能。根據具體的場景來解決效果更好，如第二段代碼的場景，可以改寫為^[1]

ConcurrentHashMap<String, AtomicInteger> map = new ConcurrentHashMap();
// 多線程環境下執行
map.get("key").incrementAndGet();

modCount和迭代器Iterator問題

modCount是大多數容器（比如ConcurrentHashMap就沒有）用來檢測是否發生了併發操作，從而判斷是否需要拋出異常通知程式員去處理的一個簡單的變數，也被稱為fast-fail。
一開始我註意到，Vector也有modCount這個屬性，這個欄位用來檢測對於容器的操作期間是否併發地進行了其他操作，如果有會拋出併發異常。既然Vector是線程安全的，為什麼還會有modCount？順藤摸瓜，我發現雖然Vector的Iterator()方法是synchronized的，但是迭代器本身的方法並不是synchronized的。這就意味著在使用迭代器操作時，對Vector的增刪等操作可能導致併發異常。
為了避免這個問題，應該在使用Iterator時對Vector加鎖。
同理可以推廣到Collecitons.synchronizedCollection()方法，可以看到這個方法創建的容器，對於迭代器和stream方法，都有一行// Must be manually synched by user!的註釋。

註2：TreeMap的comparator和key

comparator是可以為空的，此時使用key的compare介面比較。因此，這種情況下如果key==null會拋NPE。

註3：

JDK8的HashMap中有afterNodeAccess()、afterNodeInsertion()、afterNodeRemoval()三個空方法，在LinkedHashMap中覆蓋，用於回調。

註4：LinkedHashMap插入順序和訪問順序

插入順序不必解釋。訪問順序指的是，每次訪問一個節點，都將它插入到雙向鏈表的末尾。

註5：Traverser

其實現類EntryIterator的構造方法實際上是有bug的^[5]：它與子類的參數表順序不一致。
它能確保在擴容期間，每個節點只訪問一次。這個原理比較複雜，我沒有深入去看，可以參考本小節的參考文獻。

3. Hashtable & HashMap & ConcurrentHashMap

這是一個老生常談的話題了，但是涉及面比較廣，本節好好總結一下。
本節不列出具體的源碼，大部分直接給出結論，源碼部分分析可以參考文獻[7][8]。
table表示Map的hash值桶，即每一個元素對應所有同一個hash值的key-value對。

相同點

• keySet、values、entrySet()首次使用時初始化

差異點

說明

1. HashMap和ConcurrentHashMap的key桶大小都是2的冪，便於將計算下標的取模操作轉化為按位與操作
2. Map的key建議使用不可變類如String、Integer等包裝類型，其值是final的，這樣可以防止key的hash發生變化
3. 1.8以後，鏈表轉紅黑樹的閾值為8，紅黑樹轉回鏈表的閾值位6。8是鏈表和紅黑樹平均查找時間(n/2和logn)的閾值，不在7轉回是為了防止反覆轉換。
4. 1.7的HashMap的Entry和1.8中的Node幾乎是一樣的，區別在於：後者的equals()使用了Objects.equals()做了封裝，而不是對象本身的equals()。另外鏈表節點Node和紅黑樹節點TreeNode沒有關係，後者是extends LinkedHashMap的Node，通過紅黑樹查找演算法找value。1.7的ConcurrentHashMap的Node中value、next是用volatile修飾的。但是，1.8的ConcurrentHashMap有TreeNode<K,V> extends Node<K,V>，遍歷查找值時是用Node的next進行的。
5. 擴容的依據是k-v容量>=擴容閾值threshold，而threshold= table數組大小 * 裝載因數。擴容前後hash值沒有變，但是取模(^length)變了，所以在新的table中所在桶的下標可能會變
6. HashMap1.7的頭插法在併發場景下reszie()容易導致鏈表迴圈，具體的執行場景見文獻[7][9]。這一步不太好理解，我個人是用[9]的示意圖自己完整在紙上推演了一遍才理解。關鍵點在於，被中斷的線程，對同一個節點遍歷了兩次。雖然1.8改用了尾插法，仍然有迴圈引用的可能^[10][11]。
7. 1.8的HashMap在resize()時，要將節點分開，根據擴容後多計算hash的那一位是0還是1來決定放在原來的桶[i]還是桶[i+原始length]中。
8. 1.7中計算出hash值後，還會使用它計算所在的Segement
9. put(key,value)時鎖定分段鎖，先用非阻塞tryLock()自旋，超過次數上限後升級為阻塞Lock()。
10. 1.8的ConcurrentHashMap拋棄了Segement，使用synchronized+CAS（使用tabAt()計算所在桶的下標，實際是用UNSAFE類計算記憶體偏移量）^[12]進行寫入。具體來說，當桶[i]為空時，CAS寫值；非空則對桶[i]加鎖^[13]。

ConcurrentHashMap的死鎖問題

1.7場景

對於跨段操作，如size()、containsValue()，是需要按Segement的下標遞增逐段加鎖、統計，然後按原先順序解鎖的。這樣就有一個很嚴重的隱患：如果線程A在跨段操作時，中間的Segement[i]被
線程B鎖定，B又要去鎖定Segement[j] （i>j），此時就發生了死鎖。

1.8場景

由於沒有段，也就沒有了跨段。但是size()還是要統計各個桶的數目，仍然有跨桶的可能。如何計算？如果沒有衝突發生，只將 size 的變化寫入 baseCount。一旦發生衝突，就用一個數組（counterCells）來存儲後續所有 size 的變化^[14]。
而containsValue()則藉助了Traverser（見第2節註5及參考文獻[15]），但是返回值不是最新的

參考文獻

沒有在文中特殊標註的文章，是參考了其結構或部分內容，進行了重新組織。

1. Vector 是線程安全的？
2. 使用ConcurrentHashMap一定線程安全？
3. TreeMap原理實現及常用方法
4. Java容器常見面試題
5. Java高級程式員必備ConcurrentHashMap實現原理：擴容遍歷與計數
6. Java容器面試總結
7. Java：手把手帶你源碼分析 HashMap 1.7
8. Java源碼分析：關於 HashMap 1.8 的重大更新 註：本篇的resize()源碼和我本地JDK8的不一致！
9. HashMap底層詳解-003-resize、併發下的安全問題
10. JDK8中HashMap依然會死迴圈！
11. HashMap在jdk1.8中也會死迴圈
12. ConcurrentHashMap中tabAt方法分析
13. HashMap？ConcurrentHashMap？相信看完這篇沒人能難住你！
14. ConcurrentHashMap 1.8 計算 size 的方式
15. Java集合類框架學習 5.3—— ConcurrentHashMap(JDK1.8)