2019獨角獸企業(yè)重金招聘Python工程師標(biāo)準(zhǔn)>>>

##Map體系## Hashtable是JDK 5之前Map唯一線程安全的內(nèi)置實現(xiàn)（Collections.synchronizedMap不算）。Hashtable繼承的是Dictionary（Hashtable是其唯一公開的子類），并不繼承AbstractMap或者HashMap.盡管Hashtable和HashMap的結(jié)構(gòu)非常類似，但是他們之間并沒有多大聯(lián)系。 ConcurrentHashMap是HashMap的線程安全版本，ConcurrentSkipListMap是TreeMap的線程安全版本。 最終可用的線程安全版本Map實現(xiàn)是ConcurrentHashMap、ConcurrentSkipListMap、Hashtable、Properties四個，但是Hashtable是過時的類庫，因此如果可以的應(yīng)該盡可能的使用ConcurrentHashMap和ConcurrentSkipListMap.

##簡介## ConcurrentHashMap 是 java.util.concurrent 包的重要成員。本文將結(jié)合 Java 內(nèi)存模型，分析 JDK 源代碼，探索 ConcurrentHashMap 高并發(fā)的具體實現(xiàn)機制。 由于 ConcurrentHashMap 的源代碼實現(xiàn)依賴于 Java 內(nèi)存模型，所以閱讀本文需要讀者了解 Java 內(nèi)存模型。同時，ConcurrentHashMap 的源代碼會涉及到散列算法和鏈表數(shù)據(jù)結(jié)構(gòu)，所以，讀者需要對散列算法和基于鏈表的數(shù)據(jù)結(jié)構(gòu)有所了解。

###Java 內(nèi)存模型### Java 語言的內(nèi)存模型由一些規(guī)則組成，這些規(guī)則確定線程對內(nèi)存的訪問如何排序以及何時可以確保它們對線程是可見的。下面我們將分別介紹 Java 內(nèi)存模型的重排序，內(nèi)存可見性和 happens-before 關(guān)系。 ####重排序#### 內(nèi)存模型描述了程序的可能行為。具體的編譯器實現(xiàn)可以產(chǎn)生任意它喜歡的代碼 -- 只要所有執(zhí)行這些代碼產(chǎn)生的結(jié)果，能夠和內(nèi)存模型預(yù)測的結(jié)果保持一致。這為編譯器實現(xiàn)者提供了很大的自由，包括操作的重排序。 編譯器生成指令的次序，可以不同于源代碼所暗示的“顯然”版本。重排序后的指令，對于優(yōu)化執(zhí)行以及成熟的全局寄存器分配算法的使用，都是大有脾益的，它使得程序在計算性能上有了很大的提升。 重排序類型包括：

• 編譯器生成指令的次序，可以不同于源代碼所暗示的“顯然”版本。
• 處理器可以亂序或者并行的執(zhí)行指令。
• 緩存會改變寫入提交到主內(nèi)存的變量的次序。 ####內(nèi)存可見性#### 由于現(xiàn)代可共享內(nèi)存的多處理器架構(gòu)可能導(dǎo)致一個線程無法馬上（甚至永遠(yuǎn)）看到另一個線程操作產(chǎn)生的結(jié)果。所以 Java 內(nèi)存模型規(guī)定了 JVM 的一種最小保證：什么時候?qū)懭胍粋€變量對其他線程可見。 在現(xiàn)代可共享內(nèi)存的多處理器體系結(jié)構(gòu)中每個處理器都有自己的緩存，并周期性的與主內(nèi)存協(xié)調(diào)一致。假設(shè)線程 A 寫入一個變量值 V，隨后另一個線程 B 讀取變量 V 的值，在下列情況下，線程 B 讀取的值可能不是線程 A 寫入的最新值：
• 執(zhí)行線程 A 的處理器把變量 V 緩存到寄存器中。
• 執(zhí)行線程 A 的處理器把變量 V 緩存到自己的緩存中，但還沒有同步刷新到主內(nèi)存中去。
• 執(zhí)行線程 B 的處理器的緩存中有變量 V 的舊值。 ####Happens-before 關(guān)系#### happens-before 關(guān)系保證：如果線程 A 與線程 B 滿足 happens-before 關(guān)系，則線程 A 執(zhí)行動作的結(jié)果對于線程 B 是可見的。如果兩個操作未按 happens-before 排序，JVM 將可以對他們?nèi)我庵嘏判颉?下面介紹幾個與理解 ConcurrentHashMap 有關(guān)的 happens-before 關(guān)系法則：
• 程序次序法則：如果在程序中，所有動作 A 出現(xiàn)在動作 B 之前，則線程中的每動作 A 都 happens-before 于該線程中的每一個動作 B。
• 監(jiān)視器鎖法則：對一個監(jiān)視器的解鎖 happens-before 于每個后續(xù)對同一監(jiān)視器的加鎖。
• Volatile 變量法則：對 Volatile 域的寫入操作 happens-before 于每個后續(xù)對同一 Volatile 的讀操作。
• 傳遞性：如果 A happens-before 于 B，且 B happens-before C，則 A happens-before C。 ##ConcurrentHashMap結(jié)構(gòu)分析## 通過ConcurrentHashMap的類圖來分析ConcurrentHashMap的結(jié)構(gòu)。 ConcurrentHashMap是由Segment數(shù)組結(jié)構(gòu)和HashEntry數(shù)組結(jié)構(gòu)組成。Segment是一種可重入鎖ReentrantLock,在ConcurrentHashMap里扮演鎖的角色，HashEntry則用于存儲鍵值對數(shù)據(jù)。一個ConcurrentHashMap里包含一個Segment數(shù)組，Segment的結(jié)構(gòu)和HashMap類似，是一種數(shù)組和鏈表結(jié)構(gòu)， 一個Segment里包含一個HashEntry數(shù)組，每個HashEntry是一個鏈表結(jié)構(gòu)的元素， 每個Segment守護者一個HashEntry數(shù)組里的元素，當(dāng)對HashEntry數(shù)組的數(shù)據(jù)進行修改時，必須首先獲得它對應(yīng)的Segment鎖。 ConcurrentHashMap 類中包含兩個靜態(tài)內(nèi)部類 HashEntry 和 Segment.HashEntry 用來封裝映射表的鍵 / 值對；Segment 用來充當(dāng)鎖的角色，每個 Segment 對象守護整個散列映射表的若干個桶。每個桶是由若干個 HashEntry 對象鏈接起來的鏈表。一個 ConcurrentHashMap 實例中包含由若干個 Segment 對象組成的數(shù)組。

##ConcurrentHashMap原理實現(xiàn)## ###鎖分離 （Lock Stripping）### 比如HashTable是一個過時的容器類，通過使用synchronized來保證線程安全，在線程競爭激烈的情況下HashTable的效率非常低下。原因是所有訪問HashTable的線程都必須競爭同一把鎖。那假如容器里有多把鎖，每一把鎖用于鎖容器其中一部分?jǐn)?shù)據(jù)，那么當(dāng)多線程訪問容器里不同數(shù)據(jù)段的數(shù)據(jù)時，線程間就不會存在鎖競爭，從而可以有效的提高并發(fā)訪問效率，這就是ConcurrentHashMap所使用的鎖分段技術(shù)。 ConcurrentHashMap內(nèi)部使用段（Segment）來表示這些不同的部分，每個段其實就是一個小的hash table,它們有自己的鎖。只要多個修改操作發(fā)生在不同的段上，它們就可以并發(fā)進行。同樣當(dāng)一個線程占用鎖訪問其中一個段數(shù)據(jù)的時候，其他段的數(shù)據(jù)也能被其他線程訪問。 ConcurrentHashMap有些方法需要跨段，比如size（）和containsValue（），它們可能需要鎖定整個表而而不僅僅是某個段，這需要按順序鎖定所有段，操作完畢后，又按順序釋放所有段的鎖。這里"按順序"是很重要的，否則極有可能出現(xiàn)死鎖，在ConcurrentHashMap內(nèi)部，段數(shù)組是final的，并且其成員變量實際上也是final的，但是，僅僅是將數(shù)組聲明為final的并不保證數(shù)組成員也是final的，這需要實現(xiàn)上的保證。這可以確保不會出現(xiàn)死鎖，因為獲得鎖的順序是固定的。不變性是多線程編程占有很重要的地位，下面還要談到。 final Segment<K,V>[] segments; ###不變（Immutable）和易變（Volatile）### ConcurrentHashMap完全允許多個讀操作并發(fā)進行，讀操作并不需要加鎖。如果使用傳統(tǒng)的技術(shù)，如HashMap中的實現(xiàn)，如果允許可以在hash鏈的中間添加或刪除元素，讀操作不加鎖將得到不一致的數(shù)據(jù)。ConcurrentHashMap實現(xiàn)技術(shù)是保證HashEntry幾乎是不可變的。HashEntry代表每個hash鏈中的一個節(jié)點，其結(jié)構(gòu)如下所示：

static final class HashEntry<K,V> { final K key; // 聲明 key 為 final 型final int hash; // 聲明 hash 值為 final 型 volatile V value; // 聲明 value 為 volatile 型final HashEntry<K,V> next; // 聲明 next 為 final 型 HashEntry(K key, int hash, HashEntry<K,V> next, V value) { this.key = key; this.hash = hash; this.next = next; this.value = value; }}

可以看到除了value不是final的，其它值都是final的，這意味著不能從hash鏈的中間或尾部添加或刪除節(jié)點，因為這需要修改next引用值，所有的節(jié)點的修改只能從頭部開始。對于put操作，可以一律添加到Hash鏈的頭部。但是對于remove操作，可能需要從中間刪除一個節(jié)點，這就需要將要刪除節(jié)點的前面所有節(jié)點整個復(fù)制一遍，最后一個節(jié)點指向要刪除結(jié)點的下一個結(jié)點。這在講解刪除操作時還會詳述。為了確保讀操作能夠看到最新的值，將value設(shè)置成volatile,這避免了加鎖。

##ConcurrentHashMap具體實現(xiàn)## ###ConcurrentHashMap初始化### ConcurrentHashMap初始化方法是通過initialCapacity,loadFactor, concurrencyLevel幾個參數(shù)來初始化segments數(shù)組，段偏移量segmentShift,段掩碼segmentMask和每個segment里的HashEntry數(shù)組，初始化segments數(shù)組。讓我們來看一下初始化segmentShift,segmentMask和segments數(shù)組的源代碼。

http://java.chinaitlab.com/line/914247.html http://www.ibm.com/developerworks/cn/java/java-lo-concurrenthashmap http://www.blogjava.net/DLevin/archive/2013/10/18/405030.html

轉(zhuǎn)載于:https://my.oschina.net/xianggao/blog/212060

總結(jié)

以上是生活随笔為你收集整理的ConcurrentHashMap深入分析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。