并發安全的 ConcurrentHashMap 實作原理詳解
哈希表是中非常高效，複雜度為O(1)的資料結構，在Java開發中，我們最常見到最頻繁使用的就是HashMap和HashTable，但是線上程競争激烈的并發場景中使用都不夠合理。
HashMap ：先說HashMap，HashMap是線程不安全的，在并發環境下，可能會形成環狀連結清單（擴容時可能造成，具體原因自行百度google或檢視源碼分析），導緻get操作時，cpu空轉，是以，在并發環境中使用HashMap是非常危險的。
HashTable ： HashTable和HashMap的實作原理幾乎一樣，差别無非是1.HashTable不允許key和value為null；2.HashTable是線程安全的。但是HashTable線程安全的政策實作代價卻太大了，簡單粗暴，get/put所有相關操作都是synchronized的，這相當于給整個哈希表加了一把大鎖，多線程通路時候，隻要有一個線程通路或操作該對象，那其他線程隻能阻塞，相當于将所有的操作串行化，在競争激烈的并發場景中性能就會非常差。
HashTable性能差主要是由于所有操作需要競争同一把鎖，而如果容器中有多把鎖，每一把鎖鎖一段資料，這樣在多線程通路時不同段的資料時，就不會存在鎖競争了，這樣便可以有效地提高并發效率。這就是ConcurrentHashMap所采用的"分段鎖?imageView2/2/w/1620"思想。
ConcurrentHashMap源碼分析
ConcurrentHashMap采用了非常精妙的"分段鎖"政策，ConcurrentHashMap的主幹是個Segment數組。
final Segment<K,V>[] segments; 複制
Segment繼承了ReentrantLock，是以它就是一種可重入鎖（ReentrantLock)。在ConcurrentHashMap，一個Segment就是一個子哈希表，Segment裡維護了一個HashEntry數組，并發環境下，對于不同Segment的資料進行操作是不用考慮鎖競争的。（就按預設的ConcurrentLeve為16來講，理論上就允許16個線程并發執行，有木有很酷）
是以，對于同一個Segment的操作才需考慮線程同步，不同的Segment則無需考慮。
Segment類似于HashMap，一個Segment維護着一個HashEntry數組
transient volatile HashEntry<K,V>[] table;
HashEntry是目前我們提到的最小的邏輯處理單元了。一個ConcurrentHashMap維護一個Segment數組，一個Segment維護一個HashEntry數組。
不變(Immutable)和易變(Volatile)
ConcurrentHashMap完全允許多個讀操作并發進行，讀操作并不需要加鎖。如果使用傳統的技術，如HashMap中的實作，如果允許可以在hash鍊的中間添加或删除元素，讀操作不加鎖将得到不一緻的資料。ConcurrentHashMap實作技術是保證HashEntry幾乎是不可變的。HashEntry代表每個hash鍊中的一個節點，其結構如下所示：
static final class HashEntry<K,V> {
final K key;
final int hash;
volatile V value;
final HashEntry<K,V> next;
} 複制
可以看到除了value不是final的，其它值都是final的，這意味着不能從hash鍊的中間或尾部添加或删除節點，因為這需要修改next 引用值，所有的節點的修改隻能從頭部開始。
對于put操作，可以一律添加到Hash鍊的頭部。但是對于remove操作，可能需要從中間删除一個節點，這就需要将要删除節點的前面所有節點整個複制一遍，最後一個節點指向要删除結點的下一個結點。這在講解删除操作時還會詳述。為了確定讀操作能夠看到最新的值，将value設定成volatile，這避免了加鎖。
定位段
為了加快定位段以及段中hash槽的速度，每個段hash槽的的個數都是2^n，這使得通過位運算就可以定位段和段中hash槽的位置。當并發級别為預設值16時，也就是段的個數，hash值的高4位決定配置設定在哪個段中。
但是我們也不要忘記《算法導論》給我們的教訓：hash槽的的個數不應該是 2^n，這可能導緻hash槽配置設定不均，這需要對hash值重新再hash一次。