ConcurrentHashMap是實(shí)現(xiàn)了線程安全的HashMap芥丧，在JDK1.7和1.8中實(shí)現(xiàn)的原理有所區(qū)別
Jdk1.7 基于分段鎖的實(shí)現(xiàn)原理
整個 ConcurrentHashMap 由一個個 Segment 組成非区，Segment 代表”部分“或”一段“的意思充活，所以很多地方都會將其描述為分段鎖。注意物蝙，行文中，我很多地方用了“槽”來代表一個 segment。
簡單理解就是杭隙，ConcurrentHashMap 是一個 Segment 數(shù)組，Segment 通過繼承 ReentrantLock 來進(jìn)行加鎖因妙，所以每次需要加鎖的操作鎖住的是一個 segment痰憎，這樣只要保證每個 Segment 是線程安全的票髓，也就實(shí)現(xiàn)了全局的線程安全。
concurrencyLevel：并行級別铣耘、并發(fā)數(shù)洽沟、Segment 數(shù)，怎么翻譯不重要蜗细，理解它裆操。默認(rèn)是 16，也就是說 ConcurrentHashMap 有 16 個 Segments炉媒，所以理論上踪区，這個時候，最多可以同時支持 16 個線程并發(fā)寫橱野，只要它們的操作分別分布在不同的 Segment 上朽缴。這個值可以在初始化的時候設(shè)置為其他值，但是一旦初始化以后水援，它是不可以擴(kuò)容的密强。每個 Segment 內(nèi)部，其實(shí)每個 Segment 很像之前介紹的 HashMap蜗元，不過它要保證線程安全或渤，所以處理起來要麻煩些
- 查詢操作：
- 過程中是沒有加鎖的，那自然我們就需要去考慮并發(fā)問題
- 更新操作：
- 添加節(jié)點(diǎn)的操作 put 和刪除節(jié)點(diǎn)的操作 remove 都是要加 segment 上的獨(dú)占鎖的奕扣，所以它們之間自然不會有問題薪鹦，我們需要考慮的問題就是 get 的時候在同一個 segment 中發(fā)生了 put 或 remove 操作。
- 初始化槽惯豆，這個我們之前就說過了池磁，使用了 CAS 來初始化 Segment 中的數(shù)組。
- 添加節(jié)點(diǎn)到鏈表的操作是插入到表頭的楷兽，所以地熄，如果這個時候 get 操作在鏈表遍歷的過程已經(jīng)到了中間，是不會影響的芯杀。當(dāng)然端考，另一個并發(fā)問題就是 get 操作在 put 之后，需要保證剛剛插入表頭的節(jié)點(diǎn)被讀取揭厚，這個依賴于 setEntryAt 方法中使用的 UNSAFE.putOrderedObject却特。
- 擴(kuò)容。擴(kuò)容是新創(chuàng)建了數(shù)組筛圆，然后進(jìn)行遷移數(shù)據(jù)裂明，最后面將 newTable 設(shè)置給屬性 table。所以太援，如果 get 操作此時也在進(jìn)行闽晦，那么也沒關(guān)系轰绵，如果 get 先行，那么就是在舊的 table 上做查詢操作尼荆；而 put 先行，那么 put 操作的可見性保證就是 table 使用了 volatile 關(guān)鍵字唧垦。
- 刪除操作：
- get 操作需要遍歷鏈表捅儒，但是 remove 操作會”破壞”鏈表。
如果 remove 破壞的節(jié)點(diǎn) get 操作已經(jīng)過去了振亮，那么這里不存在任何問題巧还。
如果 remove 先破壞了一個節(jié)點(diǎn)，分兩種情況考慮坊秸。 1麸祷、如果此節(jié)點(diǎn)是頭結(jié)點(diǎn)，那么需要將頭結(jié)點(diǎn)的 next 設(shè) 置為數(shù)組該位置的元素褒搔，table 雖然使用了 volatile 修飾阶牍，但是 volatile 并不能提供數(shù)組內(nèi)部操作的可見性保證，所以源碼中使用了 UNSAFE 來操作數(shù)組星瘾，請看方法 setEntryAt走孽。2、如果要刪除的節(jié)點(diǎn)不是頭結(jié)點(diǎn)琳状，它會將要刪除節(jié)點(diǎn)的后繼節(jié)點(diǎn)接到前驅(qū)節(jié)點(diǎn)中磕瓷，這里的并發(fā)保證就是 next 屬性是 volatile 的。
- get 操作需要遍歷鏈表捅儒，但是 remove 操作會”破壞”鏈表。
Jdk 1.8基于CAS的實(shí)現(xiàn)原理
Java 7為實(shí)現(xiàn)并行訪問念逞，引入了Segment這一結(jié)構(gòu)困食，實(shí)現(xiàn)了分段鎖，理論上最大并發(fā)度與Segment個數(shù)相等翎承。Java 8為進(jìn)一步提高并發(fā)性硕盹，摒棄了分段鎖的方案，而是直接使用一個大的數(shù)組审洞。同時為了提高哈希碰撞下的尋址性能莱睁，Java 8在鏈表長度超過一定閾值（8）時將鏈表（尋址時間復(fù)雜度為O(N)）轉(zhuǎn)換為紅黑樹（尋址時間復(fù)雜度為O(long(N))）。其數(shù)據(jù)結(jié)構(gòu)如下圖所示：
Java 8的ConcurrentHashMap同樣是通過Key的哈希值與數(shù)組長度取模確定該Key在數(shù)組中的索引芒澜。同樣為了避免不太好的Key的hashCode設(shè)計(jì)仰剿，它通過如下方法計(jì)算得到Key的最終哈希值。不同的是痴晦，Java 8的ConcurrentHashMap作者認(rèn)為引入紅黑樹后南吮，即使哈希沖突比較嚴(yán)重，尋址效率也足夠高誊酌，所以作者并未在哈希值的計(jì)算上做過多設(shè)計(jì)部凑，只是將Key的hashCode值與其高16位作異或并保證最高位為0（從而保證最終結(jié)果為正整數(shù)）露乏。
更新操作
- 對于put操作，如果Key對應(yīng)的數(shù)組元素為null涂邀，則通過CAS操作將其設(shè)置為當(dāng)前值瘟仿。如果Key對應(yīng)的數(shù)組元素（也即鏈表表頭或者樹的根元素）不為null，則對該元素使用synchronized關(guān)鍵字申請鎖比勉，然后進(jìn)行操作劳较。如果該put操作使得當(dāng)前鏈表長度超過一定閾值，則將該鏈表轉(zhuǎn)換為樹浩聋，從而提高尋址效率观蜗。
查詢操作 - 對于讀操作，由于數(shù)組被volatile關(guān)鍵字修飾衣洁，因此不用擔(dān)心數(shù)組的可見性問題墓捻。同時每個元素是一個Node實(shí)例（Java 7中每個元素是一個HashEntry），它的Key值和hash值都由final修飾坊夫，不可變更砖第，無須關(guān)心它們被修改后的可見性問題。而其Value及對下一個元素的引用由volatile修飾环凿，可見性也有保障厂画。
