轉載自?http://blog.csdn.net/qq_24451605/article/details/51125946

CocurrentHashMap的優勢

首先常用三種HashMap包括HashMap,HashTable和CocurrentHashMap：

• HashMap在并發編程過程中使用可能導致死循環，因為插入過程不是原子操作，每個HashEntry是一個鏈表節點，很可能在插入的過程中，已經設置了后節點，實際還未插入，最終反而插入在后節點之后，造成鏈中出現環，破壞了鏈表的性質，失去了尾節點，出現死循環。
• HashTable因為內部是采用synchronized來保證線程安全的，但在線程競爭激烈的情況下HashTable的效率下降得很快因為synchronized關鍵字會造成代碼塊或方法成為為臨界區(對同一個對象加互斥鎖)，當一個線程訪問臨界區的代碼時，其他線程也訪問同一臨界區時，會進入阻塞或輪詢狀態。究其原因，實際上是有獲取鎖意向的線程的數目增加，但是鎖還是只有單個，導致大量的線程處于輪詢或阻塞，導致同一時間段有效執行的線程的增量遠不及線程總體增量。?
  
  • 在查詢時，尤其能夠體現出CocurrentHashMap在效率上的優勢，HashTable使用Sychronized關鍵字，會導致同時只能有一個查詢在執行，而Cocurrent則不采取加鎖的方法，而是采用volatile關鍵字，雖然也會犧牲效率，但是由于Sychronized，于該文末尾繼續討論。
• CocurrentHashMap利用鎖分段技術增加了鎖的數目，從而使爭奪同一把鎖的線程的數目得到控制。?
  
  • 鎖分段技術就是對數據集進行分段，每段競爭一把鎖，不同數據段的數據不存在鎖競爭，從而有效提高?高并發訪問效率。
  • CocurrentHashMap在get方法是無需加鎖的，因為用到的共享變量都采用volatile關鍵字修飾，巴證共享變量在線程之間的可見性(每次讀取都先同步緩存和內存，直接從內存中獲取值，雖然不是原子操作，但根據JAVA內存模型的happen before原則，對volatile字段的寫入操作先于讀操作，能夠保證不會臟讀),volatile為了讓變量提供線程之間的內存可見性，會禁止程序執行結果的重排序（導致緩存優化的效果降低）

CocurrentHashMap的結構

• CocurrentHashMap是由Segment數組和HashEntry數組組成。
• Segment是重入鎖(ReentrantLock),作為一個數據段競爭鎖，每個HashEntry一個鏈表結構的元素，利用Hash算法得到索引確定歸屬的數據段，也就是對應到在修改時需要競爭獲取的鎖。

segments數組的初始化

• 首先簡單描述一下源代碼中變量的含義:

變量名稱 描述

cocurrencyLevel	能夠滿足的并發訪問數量，即最多同時可以有多少線程同時訪問一個CocurrencyHashMap對象（個人的理解）
ssize	segments數組的長度(因為要利用位運算和hash算法獲取索引，故必須是2n)，而且在確定長度時能夠保證復雜度在O(logn2)
segmentShift	散列后的32中的高位表示segments的索引，代表作無符號右移的偏移量
segmentMask	對應與segment的ssize-1,有效的二進制位都為1，可以通過與散列后的數值與運算得到segment的索引
threshold	一個segment的容量
initialCapacity	CocurrentHashMap的初始化容量
cap	一個segment中HashEntry數組的長度
loadFactor	負載因子，我理解的是負載因子越大會導致出現沖突的概率增大，設置的過小又會浪費空間，所以應該根據實際情況考慮空間和時間上的平衡

• 首先計算出segment數組的長度ssize，并且計算出與ssize關聯的segmentShift和segmentMask

if ( cocurrencyLevel > MAX_SEGMENTS )cocurrencyLevel = MAX_SEGMENTS; //如果cocurrencyLevel大于上限，那么取值為上限， //上限定義為65535，決定了重入鎖的segments的數目 int sshift = 0; int ssize = 1; //找到大于等于concurrencyLevel的最小的2^n作為segments的大小 while ( ssize < concurrencyLevel ){++sshift;//記錄偏移量，為了以后通過與運算獲取segment的索引ssize <<=1; } segmentShift = 32 - sshift;//說明只有高sshift位作為segment的索引 segmentMask = ssize - 1;//能直接通過與運算獲取segment的索引 this.segments = Segment.newArray(ssize); //靜態工廠方法構造ssize大小的segment數組

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15

• 初始化每個segment,因為已經知道segment數組的規模，將ConcurrentHashMap的邏輯上持有的HashEntry均分到每個Segment上，因為是散列，所以要loadFactor來定義負載率，來保證segment適時的拓充，來避免散列表和數據規模相近時，沖突加重的風險。

if ( initialCapacity > MAXIMUM_CAPACITY )initialCapacity = MAXIMUM_CAPACITY; int c = initCapacity / ssize; //整個cocurrentHashMap的容量由所有的segment均攤 if ( c * ssize < initCapacity )++c; int cap = 1;//segment中的hashEntry數組的長度 while ( cap < c )cap <<= 1; //設置loadFactor,保證散列的高效性的同時也保證空間浪費相對有限 for ( int i = 0 ; i < this.segments.length ; i++ )this.segments[i] = new Segments<K,V>(cap , loadFactor); //最終計算出segment的容量threshold=(int)cap*loadFactor;

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13

• 定位segment，定位segment尤其重要，如果太多元素集中在少數幾個segment中會導致CocurrentHashMap的效率得不到優化，因為同一個segment中的修改還是要競爭鎖，所以選擇合適的hash算法盡可能地將元素分到不同的segment中是目標。?
  
  • CocurrentHashMap采用的是對元素的HashCode進行再Hash來減少沖突
  • CocurrentHashMap采用的是根據Wang/JenkinsHash改進的hash算法，該算法具有雪崩性(參數一位數字變化，結果都有半數左右(二進制位)發生變化)

final Segment<K,V> segmentFor ( int hash ){//首先根據segmentShift無符號右移，得到表示segment所以的高位，//然后與掩碼邏輯與得到segment的索引，定位到segmentreturn segments[(hash>>>segmentShift)&segmentMask]; }

• 1
• 2
• 3
• 4
• 5

CocurrentHashMap的操作

• Segment的get操作是不需要加鎖的。因為volatile修飾的變量保證了線程之間的可見性
• Segment的put操作是需要加鎖的，在插入時會先判斷Segment里的HashEntry數組是否會超過容量(threshold),如果超過需要對數組擴容，翻一倍。然后在新的數組中重新hash，為了高效，CocurrentHashMap只會對需要擴容的單個Segment進行擴容
• CocurrentHashMap獲取size的時候要統計Segments中的HashEntry的和，如果不對他們都加鎖的話，無法避免數據的修改造成的錯誤，但是如果都加鎖的話，效率又很低。所以CoccurentHashMap在實現的時候，巧妙地利用了在累加過程中發生變化的幾率很小的客觀條件，在獲取count時，不加鎖的計算兩次，如果兩次不相同，在采用加鎖的計算方法。采用了一個高效率的剪枝防止很大概率地減少了不必要額加鎖。

一點理解

synchronized(其實感覺是可以被重入鎖和Condition完全取代的)和volatile的取舍：

• 首先的區別就在于是否是原子操作，也就是單一的不可分割的操作，在多線程中，原子操作能夠保證不受到其他線程的影響
• synchonized就實現了原子性操作，不同的線程互斥地進入臨界代碼區，而且是內存可見的，也就是每個線程進入臨界區時，都是從內存中獲取的值，不會因為緩存而出現臟讀。
• volatile實現了內存可見性，會將修改的值直接寫入內容，并且注銷掉之前對于該變量的緩存，而且禁止了指令的排序。但是它不是原子操作！！

參考書目

• Java多線程編程實戰指南
• Java并發編程的藝術
• Java多線程編程核心技術

總結

以上是生活随笔為你收集整理的Java并发容器(一) CocurrentHashMap的应用及实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。