淺談ConcurrentHashMap實現原理

我們都知道HashTable是線程安全的類，因為使用了Synchronized來鎖整張Hash表來實現線程安全，讓線程獨占；

ConcurrentHashMap的鎖分離技術就是用多個鎖來控制對Hash表的不同部分進行修改，因為我可能只需要對一小塊部分進行操作，而如果鎖整張表開銷太大了，其內部實現就是用Semgent來控制的，每個Semgent都是一個小的HashTable，他們有自己的鎖；

然後有些方法需要訪問整個表，比如Size，ContainsValue肯定是要訪問整個表的數據，這個時候就需要鎖整張表，ConcurrentHashMap就會按順序鎖定每個Segment，操作完畢之後再按順序釋放每個Segment，按順序是為了防止出現死鎖；

引用一張圖片解釋ConcurrentHashMap的結構：

可以看出就是在HashMap的基礎上多了一個數組(暫且這樣理解)，數組的每個元素就是Segment；Segment<K,V> extends ReentrantLock implements Serializable；

ConcurrentHahsMap進行Put操作的時候，對Key需要進行3次Hash運算才能確定最終的位置：hash1(key) -> x1(得到一個值)；hash2(x1) -> x2(確定Segment位置，第二次hash是為了減少hash碰撞)；hash3(x2) -> x3(確定元素放入哪個HashEntry)；這裡只是用比較好理解的白話說，下麵會說原理；

ConcurrentHashMap中主要實體類就是三個：ConcurrentHashMap(整個Hash表),Segment(桶)，HashEntry(節點)；

 static final class HashEntry<K,V> {  
     final K key;  
     final int hash;  
     volatile V value;  
     final HashEntry<K,V> next;  
 } 

可以看出，除了value不是final，其next屬性都是final，說明不能從hash鏈的中間或尾部添加或刪除節點；對於Put操作，可以一律將元素添加到hash鏈的頭部，而對於remove操作，從中間刪除一個節點，將該節點的前面所有節點複製一份並指向刪除節點的下一節點；這會產生兩條Hash鏈，這也是為了保證多線程訪問的同步性；將value設置成volatile，這樣避免了加鎖；因為一個線程在執行get，另一個線程在執行remove，remove還沒有執行完的時候，get能看到remove之前的值，如下圖：

下麵說說Segment的數據結構：

static final class Segment<K,V> extends ReentrantLock implements Serializable {    
         /** 
          * count用來統計該段數據的個數，它是volatile，如增加/刪除節點，都要寫count值，每次讀取操作開始都要讀取count的值。
          */
         transient volatileint count;  
         /** 
          * modCount統計段結構改變的次數，主要是為了檢測對多個段進行遍歷過程中某個段是否發生改變
          */
         transient int modCount;  
         /** 
          * rehash界限值
          */
         transient int threshold;  
         /** 
          * 就是上面的HashEntry
          */
         transient volatile HashEntry<K,V>[] table;  
         /** 
          * 負載因數
          */
         final float loadFactor;  
 }

未完待續。。。