java中ConcurrentHashMap的使用及在Java 8中的沖突方案

kun_jian 發布于2019-08-14 14:36 / 2912人閱讀

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

java中ConcurrentHashMap的使用及在Java 8中的沖突方案 1、引言

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

CHM在Java中如何實現的

什么情況下應該使用CHM

在Java中使用CHM的例子

CHM的一些重要特性

2、Java中ConcurrentHashMap的實現

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

另一個重要點是在迭代遍歷CHM時，keySet返回的iterator是弱一致和fail-safe的，可能不會返回某些最近的改變，并且在遍歷過程中，如果已經遍歷的數組上的內容變化了，不會拋出ConcurrentModificationExceptoin的異常。

CHM默認的并發級別是16，但可以在創建CHM時通過構造函數改變。毫無疑問，并發級別代表著并發執行更新操作的數目，所以如果只有很少的線程會更新Map，那么建議設置一個低的并發級別。另外，CHM還使用了ReentrantLock來對segments加鎖。

3、Java中ConcurrentHashMap putifAbsent方法的例子

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

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

上面這段代碼在HashMap和HashTable中是好用的，但在CHM中是有出錯的風險的。這是因為CHM在put操作時并沒有對整個Map加鎖，所以一個線程正在put(k,v)的時候，另一個線程調用get(k)會得到null，這就會造成一個線程put的值會被另一個線程put的值所覆蓋。當然，你可以將代碼封裝到synchronized代碼塊中，這樣雖然線程安全了，但會使你的代碼變成了單線程。CHM提供的putIfAbsent(key,value)方法原子性的實現了同樣的功能，同時避免了上面的線程競爭的風險。

4、什么時候使用ConcurrentHashMap

CHM適用于讀者數量超過寫者時，當寫者數量大于等于讀者時，CHM的性能是低于Hashtable和synchronized Map的。這是因為當鎖住了整個Map時，讀操作要等待對同一部分執行寫操作的線程結束。CHM適用于做cache,在程序啟動時初始化，之后可以被多個請求線程訪問。正如Javadoc說明的那樣，CHM是HashTable一個很好的替代，但要記住，CHM的比HashTable的同步性稍弱。

5、使用小結

現在我們知道了什么是ConcurrentHashMap和什么時候該用ConcurrentHashMap，下面我們來復習一下CHM的一些關鍵點。

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

在執行寫操作時，CHM只鎖住部分的Map

并發的更新是通過內部根據并發級別將Map分割成小部分實現的

高的并發級別會造成時間和空間的浪費，低的并發級別在寫線程多時會引起線程間的競爭

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

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

CHM不允許null的鍵值

可以使用CHM代替HashTable，但要記住CHM不會鎖住整個Map

以上就是Java中CHM的實現和使用場景，下面做進一步深入探究。

6、沖突解決方案

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

在Java 8中使用常量TREEIFY_THRESHOLD來控制是否切換到平衡樹來存儲。目前，這個常量值是8，這意味著當有超過8個元素的索引一樣時，HashMap會使用樹來存儲它們。

這一改變是為了繼續優化常用類。大家可能還記得在Java 7中為了優化常用類對ArrayList和HashMap采用了延遲加載的機制，在有元素加入之前不會分配內存，這會減少空的鏈表和HashMap占用的內存。
這一動態的特性使得HashMap一開始使用鏈表，并在沖突的元素數量超過指定值時用平衡二叉樹替換鏈表。不過這一特性在所有基于hash table的類中并沒有，例如Hashtable和WeakHashMap。

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

7、什么時候會產生沖突

HashMap中調用hashCode()方法來計算hashCode。
由于在Java中兩個不同的對象可能有一樣的hashCode,所以不同的鍵可能有一樣hashCode，從而導致沖突的產生。

8、沖突解決小結

HashMap在處理沖突時使用鏈表存儲相同索引的元素。

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

當從鏈表切換到平衡樹時，HashMap迭代的順序將會改變。不過這并不會造成什么問題，因為HashMap并沒有對迭代的順序提供任何保證。

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

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

使用HashMap之所以會產生沖突是因為使用了鍵對象的hashCode()方法，而equals()和hashCode()方法不保證不同對象的hashCode是不同的。需要記住的是，相同對象的hashCode一定是相同的，但相同的hashCode不一定是相同的對象。

在HashTable和HashMap中，沖突的產生是由于不同對象的hashCode()方法返回了一樣的值。
以上就是Java中HashMap如何處理沖突。這種方法被稱為鏈地址法，因為使用鏈表存儲同一桶內的元素。通常情況HashMap，HashSet，LinkedHashSet，LinkedHashMap，ConcurrentHashMap，HashTable，IdentityHashMap和WeakHashMap均采用這種方法處理沖突。

從JDK 8開始，HashMap，LinkedHashMap和ConcurrentHashMap為了提升性能，在頻繁沖突的時候使用平衡樹來替代鏈表。因為HashSet內部使用了HashMap，LinkedHashSet內部使用了LinkedHashMap，所以他們的性能也會得到提升。

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

GPU云服務器云服務器 java中的指針使用 java開發中的趣事 java項目中的調度 java中的線程池使用

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65109.html

這幾道Java集合框架面試題在面試中幾乎必問

摘要：若遇到哈希沖突，則將沖突的值加到鏈表中即可。之后相比于之前的版本，之后在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值默認為時，將鏈表轉化為紅黑樹，以減少搜索時間。有序，唯一紅黑樹自平衡的排序二叉樹。本文是最最最常見Java面試題總結系列第三周的文章。主要內容： Arraylist 與 LinkedList 異同 ArrayList 與 Vector 區別 HashMap的底層...

bigdevil_s 2019-08-19 11:01 評論0 收藏0
HashMap ConcurrentHashMap

摘要：與中的類似，也是一個數組加鏈表，不過這個線程安全。線程安全，但是它的線程安全是依賴將所有修改的代碼塊都用修飾。這是中實現線程安全的思路，由個組成，每個就相當于一個數組鏈表。線程安全，但性能差，不推薦使用。問題描述翻翻別人的面試經歷這里在知乎上看到的，分享出了自己面試阿里Java崗的面試題。 showImg(https://segmentfault.com/img/bVbfSZ5?...

forrest23 2019-08-19 11:01 評論0 收藏0
Java 中的線程安全容器

摘要：一同步容器常用的一些容器例如都不是線程安全的，最簡單的將這些容器變為線程安全的方式，是給這些容器所有的方法都加上關鍵字。為了降低哈希沖突的成本，在鏈表長度超過時，將鏈表轉換為紅黑樹。一、同步容器常用的一些容器例如 ArrayList、HashMap、都不是線程安全的，最簡單的將這些容器變為線程安全的方式，是給這些容器所有的方法都加上 synchronized 關鍵字。 Java 的...

Seay 2019-08-16 17:38 評論0 收藏0
Java集合總結

摘要：概述集合類主要有大分支，及。不能保證元素的排列順序，順序有可能發生變化不是同步的集合元素可以是但只能放入一個是接口的唯一實現類，可以確保集合元素處于排序狀態。如果這兩個的通過比較返回，新添加的將覆蓋集合中原有的，但不會覆蓋。概述 Java集合類主要有2大分支，Collection及Map。Collection體系如下： https://upload-images.jianshu......

toddmark 2019-08-16 13:39 評論0 收藏0
Java多線程進階（二三）—— J.U.C之collections框架：ConcurrentHash

摘要：需要注意的是所鏈接的是一顆紅黑樹，紅黑樹的結點用表示，所以中實際上一共有五種不同類型的結點。時不再延續，轉而直接對每個桶加鎖，并用紅黑樹鏈接沖突結點。 showImg(https://segmentfault.com/img/bVbfTCY?w=1920&h=1080); 本文首發于一世流云專欄：https://segmentfault.com/blog... 一、Concurren...

Jason_Geng 2019-08-19 11:00 評論0 收藏0