摘要：中的使用及在中的沖突方案引言簡(jiǎn)稱是在作為的替代選擇新引入的，是包的重要成員。為了解決在頻繁沖突時(shí)性能降低的問題，中使用平衡樹來替代鏈表存儲(chǔ)沖突的元素。目前，只有和會(huì)在頻繁沖突的情況下使用平衡樹。

ConcurrentHashMap(簡(jiǎn)稱CHM)是在Java 1.5作為Hashtable的替代選擇新引入的，是concurrent包的重要成員。在Java 1.5之前，如果想要實(shí)現(xiàn)一個(gè)可以在多線程和并發(fā)的程序中安全使用的Map,只能在HashTable和synchronized Map中選擇，因?yàn)镠ashMap并不是線程安全的。但再引入了CHM之后，我們有了更好的選擇。CHM不但是線程安全的，而且比HashTable和synchronizedMap的性能要好。相對(duì)于HashTable和synchronizedMap鎖住了整個(gè)Map，CHM只鎖住部分Map。CHM允許并發(fā)的讀操作，同時(shí)通過同步鎖在寫操作時(shí)保持?jǐn)?shù)據(jù)完整性。在這篇博客中我將介紹以下幾點(diǎn)：

CHM在Java中如何實(shí)現(xiàn)的

什么情況下應(yīng)該使用CHM

在Java中使用CHM的例子

CHM的一些重要特性

CHM引入了分割，并提供了HashTable支持的所有的功能。在CHM中，支持多線程對(duì)Map做讀操作，并且不需要任何的blocking。這得益于CHM將Map分割成了不同的部分，在執(zhí)行更新操作時(shí)只鎖住一部分。根據(jù)默認(rèn)的并發(fā)級(jí)別(concurrency level)，Map被分割成16個(gè)部分，并且由不同的鎖控制。這意味著，同時(shí)最多可以有16個(gè)寫線程操作Map。試想一下，由只能一個(gè)線程進(jìn)入變成同時(shí)可由16個(gè)寫線程同時(shí)進(jìn)入(讀線程幾乎不受限制)，性能的提升是顯而易見的。但由于一些更新操作，如put(),remove(),putAll(),clear()只鎖住操作的部分，所以在檢索操作不能保證返回的是最新的結(jié)果。

另一個(gè)重要點(diǎn)是在迭代遍歷CHM時(shí)，keySet返回的iterator是弱一致和fail-safe的，可能不會(huì)返回某些最近的改變，并且在遍歷過程中，如果已經(jīng)遍歷的數(shù)組上的內(nèi)容變化了，不會(huì)拋出ConcurrentModificationExceptoin的異常。

CHM默認(rèn)的并發(fā)級(jí)別是16，但可以在創(chuàng)建CHM時(shí)通過構(gòu)造函數(shù)改變。毫無疑問，并發(fā)級(jí)別代表著并發(fā)執(zhí)行更新操作的數(shù)目，所以如果只有很少的線程會(huì)更新Map，那么建議設(shè)置一個(gè)低的并發(fā)級(jí)別。另外，CHM還使用了ReentrantLock來對(duì)segments加鎖。

很多時(shí)候我們希望在元素不存在時(shí)插入元素，我們一般會(huì)像下面那樣寫代碼

synchronized(map){
  if (map.get(key) == null){
  return map.put(key, value);
  } else{
  return map.get(key);
  }
}

上面這段代碼在HashMap和HashTable中是好用的，但在CHM中是有出錯(cuò)的風(fēng)險(xiǎn)的。這是因?yàn)镃HM在put操作時(shí)并沒有對(duì)整個(gè)Map加鎖，所以一個(gè)線程正在put(k,v)的時(shí)候，另一個(gè)線程調(diào)用get(k)會(huì)得到null，這就會(huì)造成一個(gè)線程put的值會(huì)被另一個(gè)線程put的值所覆蓋。當(dāng)然，你可以將代碼封裝到synchronized代碼塊中，這樣雖然線程安全了，但會(huì)使你的代碼變成了單線程。CHM提供的putIfAbsent(key,value)方法原子性的實(shí)現(xiàn)了同樣的功能，同時(shí)避免了上面的線程競(jìng)爭(zhēng)的風(fēng)險(xiǎn)。

CHM適用于讀者數(shù)量超過寫者時(shí)，當(dāng)寫者數(shù)量大于等于讀者時(shí)，CHM的性能是低于Hashtable和synchronized Map的。這是因?yàn)楫?dāng)鎖住了整個(gè)Map時(shí)，讀操作要等待對(duì)同一部分執(zhí)行寫操作的線程結(jié)束。CHM適用于做cache,在程序啟動(dòng)時(shí)初始化，之后可以被多個(gè)請(qǐng)求線程訪問。正如Javadoc說明的那樣，CHM是HashTable一個(gè)很好的替代，但要記住，CHM的比HashTable的同步性稍弱。

現(xiàn)在我們知道了什么是ConcurrentHashMap和什么時(shí)候該用ConcurrentHashMap，下面我們來復(fù)習(xí)一下CHM的一些關(guān)鍵點(diǎn)。

CHM允許并發(fā)的讀和線程安全的更新操作

在執(zhí)行寫操作時(shí)，CHM只鎖住部分的Map

并發(fā)的更新是通過內(nèi)部根據(jù)并發(fā)級(jí)別將Map分割成小部分實(shí)現(xiàn)的

高的并發(fā)級(jí)別會(huì)造成時(shí)間和空間的浪費(fèi)，低的并發(fā)級(jí)別在寫線程多時(shí)會(huì)引起線程間的競(jìng)爭(zhēng)

CHM的所有操作都是線程安全

CHM返回的迭代器是弱一致性，fail-safe并且不會(huì)拋出ConcurrentModificationException異常

CHM不允許null的鍵值

可以使用CHM代替HashTable，但要記住CHM不會(huì)鎖住整個(gè)Map

以上就是Java中CHM的實(shí)現(xiàn)和使用場(chǎng)景，下面做進(jìn)一步深入探究。

在Java 8 之前，HashMap和其他基于map的類都是通過鏈地址法解決沖突，它們使用單向鏈表來存儲(chǔ)相同索引值的元素。在最壞的情況下，這種方式會(huì)將HashMap的get方法的性能從O(1)降低到O(n)。為了解決在頻繁沖突時(shí)hashmap性能降低的問題，Java 8中使用平衡樹來替代鏈表存儲(chǔ)沖突的元素。這意味著我們可以將最壞情況下的性能從O(n)提高到O(logn)。

在Java 8中使用常量TREEIFY_THRESHOLD來控制是否切換到平衡樹來存儲(chǔ)。目前，這個(gè)常量值是8，這意味著當(dāng)有超過8個(gè)元素的索引一樣時(shí)，HashMap會(huì)使用樹來存儲(chǔ)它們。

這一改變是為了繼續(xù)優(yōu)化常用類。大家可能還記得在Java 7中為了優(yōu)化常用類對(duì)ArrayList和HashMap采用了延遲加載的機(jī)制，在有元素加入之前不會(huì)分配內(nèi)存，這會(huì)減少空的鏈表和HashMap占用的內(nèi)存。
這一動(dòng)態(tài)的特性使得HashMap一開始使用鏈表，并在沖突的元素?cái)?shù)量超過指定值時(shí)用平衡二叉樹替換鏈表。不過這一特性在所有基于hash table的類中并沒有，例如Hashtable和WeakHashMap。

目前，只有ConcurrentHashMap,LinkedHashMap和HashMap會(huì)在頻繁沖突的情況下使用平衡樹。

HashMap中調(diào)用hashCode()方法來計(jì)算hashCode。
由于在Java中兩個(gè)不同的對(duì)象可能有一樣的hashCode,所以不同的鍵可能有一樣hashCode，從而導(dǎo)致沖突的產(chǎn)生。

HashMap在處理沖突時(shí)使用鏈表存儲(chǔ)相同索引的元素。

從Java 8開始，HashMap，ConcurrentHashMap和LinkedHashMap在處理頻繁沖突時(shí)將使用平衡樹來代替鏈表，當(dāng)同一hash桶中的元素?cái)?shù)量超過特定的值便會(huì)由鏈表切換到平衡樹，這會(huì)將get()方法的性能從O(n)提高到O(logn)。

當(dāng)從鏈表切換到平衡樹時(shí)，HashMap迭代的順序?qū)?huì)改變。不過這并不會(huì)造成什么問題，因?yàn)镠ashMap并沒有對(duì)迭代的順序提供任何保證。

從Java 1中就存在的Hashtable類為了保證迭代順序不變，即便在頻繁沖突的情況下也不會(huì)使用平衡樹。這一決定是為了不破壞某些較老的需要依賴于Hashtable迭代順序的Java應(yīng)用。

除了Hashtable之外，WeakHashMap和IdentityHashMap也不會(huì)在頻繁沖突的情況下使用平衡樹。

使用HashMap之所以會(huì)產(chǎn)生沖突是因?yàn)槭褂昧随I對(duì)象的hashCode()方法，而equals()和hashCode()方法不保證不同對(duì)象的hashCode是不同的。需要記住的是，相同對(duì)象的hashCode一定是相同的，但相同的hashCode不一定是相同的對(duì)象。

在HashTable和HashMap中，沖突的產(chǎn)生是由于不同對(duì)象的hashCode()方法返回了一樣的值。
以上就是Java中HashMap如何處理沖突。這種方法被稱為鏈地址法，因?yàn)槭褂面湵泶鎯?chǔ)同一桶內(nèi)的元素。通常情況HashMap，HashSet，LinkedHashSet，LinkedHashMap，ConcurrentHashMap，HashTable，IdentityHashMap和WeakHashMap均采用這種方法處理沖突。

從JDK 8開始，HashMap，LinkedHashMap和ConcurrentHashMap為了提升性能，在頻繁沖突的時(shí)候使用平衡樹來替代鏈表。因?yàn)镠ashSet內(nèi)部使用了HashMap，LinkedHashSet內(nèi)部使用了LinkedHashMap，所以他們的性能也會(huì)得到提升。

http://javarevisited.blogspot.com/2013/02/concurrenthashmap-in-java-example-tutorial-working.html 
http://javarevisited.blogspot.jp/2016/01/how-does-java-hashmap-or-linkedhahsmap-handles.html