文章目錄
-
- 1 介紹
- 2 ConcurrentHashMap
-
- 2.1 JDK1.8版本以前的ConcurrentHashMap内部結構
- 2.2 JDK1.8版本ConcurrentHashMap的内部結構
- 3 ConcurrentSkipListMap簡介
1 介紹
Map是一個接口，它的實作方式有很多種，比如常見的HashMap、LinkedHashMap，但是這些Map的實作并不是線程安全的，在多線程高并發的環境中會出現線程安全的問題。Hashtable或者SynchronizedMap雖然是線程安全的，但是在多線程高并發的環境中，簡單粗暴的排他式加鎖方式效率并不是很高。
Doug Lea自JDK 1.5版本起在Java中引入了ConcurrentHashMap并且在随後的JDK版本疊代中都在不遺餘力地為性能提升做出努力，除了ConcurrentHashMap之外，大師Doug Lea也在JDK 1.6版本中引入了另外一個高并發Map的解決方案ConcurrentSkipListMap。
這些新的Map在使用上與HashMap并沒有很大的不同，但是其内部的實作卻是非常複雜的
2 ConcurrentHashMap
ConcurrentHashMap的内部實作幾乎在每次JDK版本更新的過程中都會随之更新優化，總體來講，ConcurrentHashMap是專門為多線程高并發場景而設計的Map，它的get()操作基本上是lock-free的，同時put()方法又将鎖的粒度控制在很小的範圍之内，是以它非常适合于多線程的應用程式之中。
2.1 JDK1.8版本以前的ConcurrentHashMap内部結構
在JDK1.6、1.7版本中，ConcurrentHashMap采用的是分段鎖的機制（可以在確定線程安全的同時最小化鎖的粒度）實作并發的更新操作，在ConcurrentHashMap中包含兩個核心的靜态内部類Segment和HashEntry，前者是一個實作自ReentrantLock的顯式鎖，每一個Segment鎖對象均可用于同步每個散列映射表的若幹個桶（HashBucket），後者主要用于存儲映射表的鍵值對。與此同時，若幹個HashEntry通過連結清單結構形成了HashBucket，而最終的ConcurrentHashMap則是由若幹個（預設是16個）Segment對象數組構成的
Segment可用于實作減小鎖的粒度，ConcurrentHashMap被分割成若幹個Segment，在put的時候隻需要鎖住一個Segment即可，而get時候則幹脆不加鎖，而是使用volatile屬性以保證被其他線程同時修改後的可見性。
2.2 JDK1.8版本ConcurrentHashMap的内部結構
在JDK 1.8版本中幾乎重構了ConcurrentHashMap的内部實作，摒棄了segment的實作方式，直接用table數組存儲鍵值對，在JDK1.6中，每個bucket中鍵值對的組織方式都是單向連結清單，查找複雜度是O(n)，JDK1.8中當連結清單長度超過8時，連結清單轉換為紅黑樹，查詢複雜度可以降低到O(log n)，改進了性能。利用CAS+Synchronized可以保證并發更新的安全性，底層則采用數組+連結清單+紅黑樹（提高檢索效率）的存儲結構
3 ConcurrentSkipListMap簡介
ConcurrentSkipListMap提供了一種線程安全的并發通路的排序映射表。内部是SkipList（跳表）結構實作，在理論上，其能夠在O(log(n))時間内完成查找、插入、删除操作。調用ConcurrentSkipListMap的size時，由于多個線程可以同時對映射表進行操作，是以映射表需要周遊整個連結清單才能傳回元素的個數，這個操作是個O(log(n))的操作。
在讀取性能上，雖然ConcurrentSkipListMap不能與ConcurrentHashMap相提并論，但是ConcurrentSkipListMap存在着如下兩大天生的優越性是ConcurrentSkipListMap所不具備的。
- 由于基于跳表的資料結構，是以ConcurrentSkipListMap的key是有序的。
- ，ConcurrentSkipListMap支援更高的并發，ConcurrentSkipListMap的存取時間複雜度是O（log（n）），與線程數幾乎無關，也就是說，在資料量一定的情況下，并發的線程越多，ConcurrentSkipListMap越能展現出它的優勢。