轉(zhuǎn)載自??ConcurrentHashMap能完全替代HashTable嗎？

????關(guān)于ConcurrentHashMap在之前的ConcurrentHashMap原理分析中已經(jīng)解釋了原理，而HashTable其實(shí)大抵上只是對(duì)HashMap的線程安全的封裝，在JDK7與JDK8中HashMap的實(shí)現(xiàn)中解釋了HashMap的原理。

至此你應(yīng)該能夠明白，ConcurrentHashMap與HashTable都可以用于多線程的環(huán)境，但是當(dāng)Hashtable的大小增加到一定的時(shí)候，性能會(huì)急劇下降，因?yàn)榈鷷r(shí)需要被鎖定很長(zhǎng)的時(shí)間。因?yàn)镃oncurrentHashMap引入了分割(segmentation)，不論它變得多么大，僅僅需要鎖定map的某個(gè)部分，而其它的線程不需要等到迭代完成才能訪問map。簡(jiǎn)而言之，在迭代的過程中，ConcurrentHashMap僅僅鎖定map的某個(gè)部分，而Hashtable則會(huì)鎖定整個(gè)map。

那么既然ConcurrentHashMap那么優(yōu)秀，為什么還要有Hashtable的存在呢？ConcurrentHashMap能完全替代HashTable嗎？

HashTable雖然性能上不如ConcurrentHashMap，但并不能完全被取代，兩者的迭代器的一致性不同的，HashTable的迭代器是強(qiáng)一致性的，而ConcurrentHashMap是弱一致的。 ConcurrentHashMap的get，clear，iterator 都是弱一致性的。 Doug Lea 也將這個(gè)判斷留給用戶自己決定是否使用ConcurrentHashMap。

那么什么是強(qiáng)一致性和弱一致性呢？

get方法是弱一致的，是什么含義？可能你期望往ConcurrentHashMap底層數(shù)據(jù)結(jié)構(gòu)中加入一個(gè)元素后，立馬能對(duì)get可見，但ConcurrentHashMap并不能如你所愿。換句話說，put操作將一個(gè)元素加入到底層數(shù)據(jù)結(jié)構(gòu)后，get可能在某段時(shí)間內(nèi)還看不到這個(gè)元素，若不考慮內(nèi)存模型，單從代碼邏輯上來看，卻是應(yīng)該可以看得到的。

下面將結(jié)合代碼和java內(nèi)存模型相關(guān)內(nèi)容來分析下put/get方法。put方法我們只需關(guān)注Segment#put，get方法只需關(guān)注Segment#get，在繼續(xù)之前，先要說明一下Segment里有兩個(gè)volatile變量：count和table；HashEntry里有一個(gè)volatile變量：value。

Segment#put

V put(K key, int hash, V value, boolean onlyIfAbsent) {lock();try {int c = count;if (c++ > threshold) // ensure capacityrehash();HashEntry[] tab = table;int index = hash & (tab.length - 1);HashEntry first = tab[index];HashEntry e = first;while (e != null && (e.hash != hash || !key.equals(e.key)))e = e.next;V oldValue;if (e != null) {oldValue = e.value;if (!onlyIfAbsent)e.value = value;}else {oldValue = null;++modCount;tab[index] = new HashEntry(key, hash, first, value);count = c; // write-volatile}return oldValue;} finally {unlock();} }

Segment#get

V get(Object key, int hash) {if (count != 0) { // read-volatileHashEntry e = getFirst(hash);while (e != null) {if (e.hash == hash && key.equals(e.key)) {V v = e.value;if (v != null)return v;return readValueUnderLock(e); // recheck}e = e.next;}}return null; }

我們?nèi)绾未_定線程1放入某個(gè)變量的值是否對(duì)線程2可見？當(dāng)a hb（happen before） c時(shí)，a對(duì)c可見，那么我們接下來我們只要尋找put和get之間所有可能的執(zhí)行軌跡上的hb關(guān)系。要找出hb關(guān)系，我們需要先找出與hb相關(guān)的Action。為方便，這里將兩段代碼放到了一張圖片上。

可以注意到，同一個(gè)Segment實(shí)例中的put操作是加了鎖的，而對(duì)應(yīng)的get卻沒有。根據(jù)hb關(guān)系中的線程間Action類別，可以從上圖中找出這些Action，主要是volatile讀寫和加解鎖，也就是圖中畫了橫線的那些。

put操作可以分為兩種情況，一是key已經(jīng)存在，修改對(duì)應(yīng)的value；二是key不存在，將一個(gè)新的Entry加入底層數(shù)據(jù)結(jié)構(gòu)。

key已經(jīng)存在的情況比較簡(jiǎn)單，即if (e != null)部分，前面已經(jīng)說過HashEntry的value是個(gè)volatile變量，當(dāng)線程1給value賦值后，會(huì)立馬對(duì)執(zhí)行g(shù)et的線程2可見，而不用等到put方法結(jié)束。

key不存在的情況稍微復(fù)雜一些，新加一個(gè)Entry的邏輯在else中。那么將new HashEntry賦值給tab[index]是否能立刻對(duì)執(zhí)行g(shù)et的線程可見呢？我們只需分析寫tab[index]與讀取tab[index]之間是否有hb關(guān)系即可。

假設(shè)執(zhí)行put的線程與執(zhí)行g(shù)et的線程的軌跡是這樣的

執(zhí)行put的線程	執(zhí)行g(shù)et的線程
⑧tab[index] = new HashEntry<K,V>(key, hash, first, value)	?
②count = c	?
?	③if (count != 0)
?	⑨HashEntry e = getFirst(hash);

tab變量是一個(gè)普通的變量，雖然給它賦值的是volatile的table。另外，雖然引用類型（數(shù)組類型）的變量table是volatile的，但table中的元素不是volatile的，因此⑧只是一個(gè)普通的寫操作；count變量是volatile的，因此②是一個(gè)volatile寫；③很顯然是一個(gè)volatile讀；⑨中g(shù)etFirst方法中讀取了table，因此包含一個(gè)volatile讀。

根據(jù)Synchronization Order，對(duì)同一個(gè)volatile變量，有volatile寫 hb volatile讀。在這個(gè)執(zhí)行軌跡中，時(shí)間上②在③之前發(fā)生，且②是寫count，③是讀count，都是針對(duì)同一個(gè)volatile變量count，因此有② hb ③；又因?yàn)棰嗪廷谑峭粋€(gè)線程中的，③和⑨是同一個(gè)線程中的，根據(jù)Program Order，有⑧ hb ②，③ hb ⑨。目前我們有了三組關(guān)系了⑧ hb ②，② hb ③，③ hb ⑨，再根據(jù)hb關(guān)系是可傳遞的（即若有x hb y且y hb z，可得出x hb z），可以得出⑧ hb ⑨。因此，如果按照上述執(zhí)行軌跡，⑧中寫入的數(shù)組元素對(duì)⑨中的讀取操作是可見的。

再考慮這樣一個(gè)執(zhí)行軌跡：

執(zhí)行put的線程	執(zhí)行g(shù)et的線程
⑧tab[index] = new HashEntry<K,V>(key, hash, first, value)	?
?	③if (count != 0)
②count = c	?
?	⑨HashEntry e = getFirst(hash);

這里只是變換了下執(zhí)行順序。每條語句的volatile讀寫含義同上，但它們之間的hb關(guān)系卻改變了。Program Order是我們一直擁有的，即我們有⑧ hb ②，③ hb ⑨。但這次對(duì)volatile的count的讀時(shí)間上發(fā)生在對(duì)count的寫之前，我們無法得出② hb ⑨這層關(guān)系了。因此，通過count變量，在這個(gè)軌跡上是無法得出⑧ hb ⑨的。那么，存不存在其它可替換關(guān)系，讓我們?nèi)阅艿贸觫?hb ⑨呢？

我們要找的是，在⑧之后有一條語句或指令x，在⑨之前有一條語句或指令y，存在x hb y。這樣我們可以有⑧ hb x，x hb y， y hb ⑨。就讓我們來找一下是否存在這樣的x和y。圖中的⑤、⑥、⑦、①存在volatile讀寫，但是它們?cè)冖嘀?#xff0c;因此對(duì)確立⑧ hb ⑨這個(gè)關(guān)系沒有用處；同理，④在⑨之后，我們要找的是⑨之前的，因此也對(duì)這個(gè)問題無益。前面已經(jīng)分析過了②，③之間沒法確立hb關(guān)系。

在⑧之后，我們發(fā)現(xiàn)一個(gè)unlock操作，如果能在⑨之前找到一個(gè)lock操作，那么我們要找的x就是unlock，要找的y就是lock，因?yàn)镾ynchronization Order中有unlock hb lock的關(guān)系。但是，很不幸運(yùn)，⑨之前沒有l(wèi)ock操作。因此，對(duì)于這樣的軌跡，是沒有⑧ hb ⑨關(guān)系的，也就是說，如果某個(gè)Segment實(shí)例中的put將一個(gè)Entry加入到了table中，在未執(zhí)行count賦值操作之前有另一個(gè)線程執(zhí)行了同一個(gè)Segment實(shí)例中的get，來獲取這個(gè)剛加入的Entry中的value，那么是有可能取不到的！

此外，如果getFirst(hash)先執(zhí)行，tab[index] = new HashEntry<K,V>(key, hash, first, value)后執(zhí)行，那么，這個(gè)get操作也是看不到put的結(jié)果的。

……

正是因?yàn)間et操作幾乎所有時(shí)候都是一個(gè)無鎖操作（get中有一個(gè)readValueUnderLock調(diào)用，不過這句執(zhí)行到的幾率極小），使得同一個(gè)Segment實(shí)例上的put和get可以同時(shí)進(jìn)行，這就是get操作是弱一致的根本原因。Java API中對(duì)此有一句簡(jiǎn)單的描述:

Retrievals reflect the results of the most recently?completed?update operations holding upon their onset.

也就是說API上保證get操作一定能看到已完成的put操作。已完成的put操作肯定在get讀取count之前對(duì)count做了寫入操作。因此，也就是我們第一個(gè)軌跡分析的情況。

ConcurrentHashMap#clear

clear方法很簡(jiǎn)單，看下代碼即知。

public void clear() {for (int i = 0; i < segments.length; ++i)segments[i].clear(); }

因?yàn)闆]有全局的鎖，在清除完一個(gè)segments之后，正在清理下一個(gè)segments的時(shí)候，已經(jīng)清理segments可能又被加入了數(shù)據(jù)，因此clear返回的時(shí)候，ConcurrentHashMap中是可能存在數(shù)據(jù)的。因此，clear方法是弱一致的。

ConcurrentHashMap中的迭代器

ConcurrentHashMap中的迭代器主要包括entrySet、keySet、values方法。它們大同小異，這里選擇entrySet解釋。當(dāng)我們調(diào)用entrySet返回值的iterator方法時(shí)，返回的是EntryIterator，在EntryIterator上調(diào)用next方法時(shí)，最終實(shí)際調(diào)用到了HashIterator.advance()方法，看下這個(gè)方法：

final void advance() {if (nextEntry != null && (nextEntry = nextEntry.next) != null)return;while (nextTableIndex >= 0) {if ( (nextEntry = currentTable[nextTableIndex--]) != null)return;}while (nextSegmentIndex >= 0) {Segment<K,V> seg = segments[nextSegmentIndex--];if (seg.count != 0) {currentTable = seg.table;for (int j = currentTable.length - 1; j >= 0; --j) {if ( (nextEntry = currentTable[j]) != null) {nextTableIndex = j - 1;return;}}}} }

這個(gè)方法在遍歷底層數(shù)組。在遍歷過程中，如果已經(jīng)遍歷的數(shù)組上的內(nèi)容變化了，迭代器不會(huì)拋出ConcurrentModificationException異常。如果未遍歷的數(shù)組上的內(nèi)容發(fā)生了變化，則有可能反映到迭代過程中。這就是ConcurrentHashMap迭代器弱一致的表現(xiàn)。

總結(jié)

ConcurrentHashMap的弱一致性主要是為了提升效率，是一致性與效率之間的一種權(quán)衡。要成為強(qiáng)一致性，就得到處使用鎖，甚至是全局鎖，這就與Hashtable和同步的HashMap一樣了。

Reference：

1.?http://blog.csdn.net/kobejayandy/article/details/16834311

2.?http://ifeve.com/concurrenthashmap-vs-hashtable/

3.?http://ifeve.com/concurrenthashmap-weakly-consistent/

總結(jié)

以上是生活随笔為你收集整理的ConcurrentHashMap能完全替代HashTable吗？的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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