Java中的ConcurrentHashMap原理分析節選

集合是程式設計中最常用的資料結構。而談到并發，幾乎總是離不開集合這類進階資料結構的支援。比如兩個線程需要同時通路一個中間臨界區queue，比如常會用緩存作為外部檔案的副本hashmap。這篇文章主要分析jdk1.5的3種并發集合類型concurrent，copyonright，queue中的concurrenthashmap，讓我們從原理上細緻的了解它們，能夠讓我們在深度項目開發中獲益非淺。

在tiger之前我們使用得最多的資料結構之一就是hashmap和hashtable。大hashmap中未進行同步考慮，而hashtable則使用了synchronized，帶來的直接影響就是可選擇，我們可以在單線程時使用hashmap提高效率，而多線程時用hashtable來保證安全。

當享受着jdk帶來的便利時同樣承受它帶來的不幸惡果。通過分析hashtable就知道，synchronized是針對整張hash表的，即每次鎖住整張表讓線程獨占，安全的背後是巨大的浪費，慧眼獨具的doug lee立馬拿出了解決方案----concurrenthashmap。

concurrenthashmap和hashtable主要差別就是圍繞着鎖的粒度以及如何鎖。

左邊便是hashtable的實作方式---鎖整個hash表；而右邊則是concurrenthashmap的實作方式---鎖桶（或段）。concurrenthashmap将hash表分為16個桶（預設值），諸如get,put,remove等常用操作隻鎖目前需要用到的桶。試想，原來隻能一個線程進入，現在卻能同時16個寫線程進入（寫線程才需要鎖定，而讀線程幾乎不受限制，之後會提到），并發性的提升是顯而易見的。

更令人驚訝的是concurrenthashmap的讀取并發，因為在讀取的大多數時候都沒有用到鎖定，是以讀取操作幾乎是完全的并發操作，而寫操作鎖定的粒度又非常細，比起之前又更加快速（這一點在桶更多時表現得更明顯些）。隻有在求size等操作時才需要鎖定整個表。而在疊代時，concurrenthashmap使用了不同于傳統集合的快速失敗疊代器（見之前的文章《java api備忘---集合》）的另一種疊代方式，我們稱為弱一緻疊代器。在這種疊代方式中，當iterator被建立後集合再發生改變就不再是抛出concurrentmodificationexception，取而代之的是在改變時new新的資料進而不影響原有的資料，iterator完成後再将頭指針替換為新的資料，這樣iterator線程可以使用原來老的資料，而寫線程也可以并發的完成改變，更重要的，這保證了多個線程并發執行的連續性和擴充性，是性能提升的關鍵。

原帖位址：http://blog.csdn.net/liuzhengkang/article/details/2916620