JDK集合

---

目錄

集合

1. List

2. Map

3. Set

4. Queue

5. 常見面試問題

4.1 ArrayList和LinkedList兩者的區別和使用場景

4.2 HashMap的實現原理

4.3 JDK7和JDK8對HashMap實現的不同

4.4 HashMap是否為線程安全？

4.5?ConcurrentHashMap的實現原理

---

集合

JDK的集合主要有List、Map及Set

1. List

我們先通過是否線程安全分為兩大類。

線程不安全的List：

常用的有ArrayList和LinkedList

ArrayList：

底層為數組，初始化為空數組，當開始add時，初始化為長度10的數組。

擴容機制：通過arrayCopy將數組擴容，擴容長度為原長度的1.5倍

優勢：通過下標訪問，效率相對高。但add或remove時，因為需要對下標后所有元素都需移動，效率較低。

風險：當申請的數組大小超出剩余內存大小時，拋出OOM:異常

LinkedList：

底層為雙向鏈表

擴容機制：因為是通過鏈表組織，無需擴容

優勢：需通過頭節點或尾節點訪問指定節點，效率較低。但add或remove時，因為只需要對前后節點的指向做變更，效率較高。

風險：當鏈表長度過長，超出剩余內存大小時，拋出OOM:異常

線程安全的List：

常用的有Vector、Collections.synchronizedList和CopyOnWriteArrayList

Vector：

底層與ArrayList類似，但是方法加了synchronized保證線程安全

擴容機制、優勢、風險：與ArrayList類似

Collections.synchronizedList：

通過synchronized對傳入的list保證線程安全，鎖對象可通過參數傳入，或默認this

擴容機制、優勢、風險：與傳入list一致

CopyOnWriteArrayList：

底層為數組，初始化為空數組，每次add或remove在會創建一個新數組，在新數組執行完操作后，再設置為當前數組，通過ReentrantLock實現線程安全。

擴容機制：因為每次add都會創建一個新數組，故無擴容機制

優勢：前兩種在get時都加了鎖，導致get效率差。而CopyOnWriteArrayList的get無需加鎖，效率較高。

風險：每次add都需創建一個新數組，針對寫多讀少的場景效率差。

2. Map

我們同樣先通過是否線程安全分為兩大類。

線程不安全的Map：

常用的有HashMap、LinkedHashMap和TreeMap

HashMap：

底層為數組+單鏈表，初始化為長度為16的數組，通過對key的hashCode進行hash，分配至不同的下標元素中，如下標元素已有節點，則作為鏈表節點插入。

jdk7使用頭插法，但該方法在多線程時會導致環形鏈表，jdk8改用尾插法。

因為鏈表長度過長時，查詢效率差，jdk8在鏈表長度超過8時，轉化為紅黑樹結構。

擴容機制：將數組長度擴充為原來的兩倍。jdk7通過對每個節點重hash進行分配，jdk8優化為通過多出的高位，判斷節點是位于原位置還是原位置+擴充長度的位置。

風險：當申請的數組大小超出剩余內存大小時，拋出OOM:異常

LinkedHashMap：

在hashmap的基礎上，對每個節點增加了前后指針，用雙向鏈表將每個節點組織起來，可通過插入順序或訪問順序來進行遍歷。

擴容機制：與HashMap類似

優勢：可通過節點的前后指針順序遍歷，可作為LRU緩存。

風險：與HashMap類似

TreeMap：

底層為紅黑樹，通過傳入的Comparator實現排序

擴容機制：無需擴容

優勢：實現自定義排序算法的map

風險：與HashMap類似

線程安全的Map：

常用的有Hashtable、Collections.synchronizedMap和ConcurrentHashMap

Hashtable：

底層與HashMap類似，但是方法加了synchronized保證線程安全

擴容機制、優勢、風險：與HashMap類似

Collections.synchronizedMap：

通過synchronized對傳入的map保證線程安全，鎖對象可通過參數傳入，或默認this

擴容機制、優勢、風險：與傳入map一致

ConcurrentHashMap：

jdk7底層為分段鎖，分段鎖繼承ReentrantLock，通過lock實現線程安全，初始化為16個分段鎖，每個分段鎖持有一個長度為2的數組。

該結構存在每個分段鎖都需對數組長度擴容的耗費，jdk8底層為數組+單鏈表+紅黑樹，與HashMap相似，利用CAS+volatile+synchronized保證線程安全

擴容機制：jdk7每個分段鎖的數組會自行擴容，擴容規則與HashMap相似。

優勢：前兩種在get時都加了鎖，導致get效率差。而ConcurrentHashMap的get無需加鎖，效率較高。

風險：

3. Set

Set的底層通過持有Map實現，key存傳入的集合值，value則存Object，我們同樣先通過是否線程安全分為兩大類。

線程不安全的Set：

常用的有HashSet、LinkedHashSet和TreeSet

底層對應的HashMap、LinkedHashMap和TreeMap，擴容機制、優勢與風險一致。

線程安全的Set：

常用的有Collections.synchronizedSet和CopyOnWriteArraySet

Collections.synchronizedSet：

通過synchronized對傳入的set保證線程安全，鎖對象可通過參數傳入，或默認this

擴容機制、優勢、風險：與傳入set一致

CopyOnWriteArraySet：

底層為CopyOnWriteArrayList，利用addIfAbsent實現去重，擴容機制、優勢與風險和CopyOnWriteArrayList一致。

4. Queue

//TODO

5. 常見面試問題

4.1 ArrayList和LinkedList兩者的區別和使用場景

4.2 HashMap的實現原理

4.3 JDK7和JDK8對HashMap實現的不同

JDK8中，對HashMap的實現進行優化，如鏈表長度超過指定長度（默認15），則會轉化為紅黑樹進行存儲。

4.4 HashMap是否為線程安全？

ConcurrentHashMap在JDK7中

4.5?ConcurrentHashMap的實現原理

總結

以上是生活随笔為你收集整理的JDK集合的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。