為什么需要 ConcurrentHashMap

Java 早期的同步類 HashTable 和 Collections 提供的同步包裝器為我們提供了線程安全的容器，但是因?yàn)檫@兩種方式都是在整個大操作 put、get、size 級別上加鎖實(shí)現(xiàn)的。并發(fā)效率很低。作為改進(jìn)，Java 提供了更為高效的并發(fā)容器——ConcurrentHashMap。

jdk 1.7 ConcurrentHashMap 分析

ConcurrentHashMap 的設(shè)計(jì)其實(shí)一直在演化，早期的 ConcurrentHashMap，其實(shí)現(xiàn)是基于：

• 分離鎖，也就是將內(nèi)部進(jìn)行分段（Segment），里面則是 HashEntry 的數(shù)組，和 HashMap 類似，哈希相同的條目也是以鏈表的形式存放。
• HashEntry 內(nèi)部使用 volatile 的 value 字段來保證可見性，也利用了不可變對象的機(jī)制以改進(jìn)利用 Unsafe 提供的底層能力，比如 volatile access，去直接完成部分操作，以最優(yōu)化性能，畢竟 Unsafe 中的很多操作都是 JVM intrinsic 優(yōu)化過的。

這個版本的核心是利用分段設(shè)計(jì)，在進(jìn)行并發(fā)操作時，鎖住相應(yīng)的 Segment，來避免鎖住整個表，大大提高了性能。

構(gòu)造時，Segment 的數(shù)量由所謂的concurrentcyLevel 決定，默認(rèn)是 16，可以通過構(gòu)造函數(shù)顯式指定，這個輸入的值會被 Java 自動調(diào)整為最近的 2 的冪數(shù)值，比如輸入 15，就會被自動調(diào)整為 16。之所以這樣調(diào)整，是因?yàn)?2 的冪次方減一就是一個二進(jìn)制低位全是 1 的“掩碼”，在確定元素在哪個 Segment 時會利用到。

在進(jìn)行并發(fā)寫操作時：

• ConcurrentHashMap 會獲取再入鎖，以保證數(shù)據(jù)一致性，Segment 本身就是基于 ReentrantLock 的擴(kuò)展實(shí)現(xiàn)的，所以，在并發(fā)修改期間，相應(yīng)的 Segment 是被鎖定的。
• 在最初階段，進(jìn)行重復(fù)性的掃描，以確定相應(yīng)的 key 的值是否已經(jīng)在數(shù)組里面，進(jìn)而決定是更新還是放置操作。重復(fù)掃描、檢測沖突是 ConcurrentHashMap 的常見技巧。

另一個需要關(guān)注的點(diǎn)是 size 方法，它的實(shí)現(xiàn)涉及分離鎖的一個副作用。

如果不加鎖直接計(jì)算所有 Segment 的總值，在并發(fā) put 的情況下，就可能導(dǎo)致結(jié)果不準(zhǔn)確，但是直接鎖定所有 Segment 進(jìn)行計(jì)算，代價就很昂貴。其實(shí)，分離鎖也限制了 Map 的初始化等操作。

這個版本的 ConcurrentHashMap 是通過重試機(jī)制（RETRIES_BEFORE_LOCK，指定重試次數(shù) 2），來試圖獲得可靠值。如果沒有監(jiān)控到發(fā)生變化（通過對比 Segment.modCount)，就直接返回，否則獲取鎖進(jìn)行操作。

jdk 1.8 ConcurrentHashMap 分析

• 總體結(jié)構(gòu)上，它的內(nèi)部存儲結(jié)構(gòu)變得和 HashMap 相似，同樣是大的桶（bucket）數(shù)組，然后內(nèi)部也是一個個所謂的鏈表結(jié)構(gòu)（bin），同步的力度要更細(xì)致一些。在單個桶中數(shù)據(jù)過多時，會進(jìn)行樹化。
• 其內(nèi)部保留了 Segment 定義，目的是為了保證序列化時的兼容性，不再有任何結(jié)構(gòu)上的用處。
• 因?yàn)椴辉偈褂?Segment，初始化操作大大簡化，修改為 lazy-load 形式，有效避免了初始開銷，解決了老版本很多人抱怨的這一點(diǎn)。
• 數(shù)據(jù)存儲利用 volatile 來保證可見性。
• 使用 CAS 等操作，在特定場景進(jìn)行無鎖并發(fā)操作。
• 使用 Unsafe、LongAdder 之類的底層手段，進(jìn)行極端情況的優(yōu)化。