原創文章，轉載請務必将下面這段話置于文章開頭處（保留超連結）。
衆所周知，hashmap是非線程安全的。而hashmap的線程不安全主要展現在resize時的死循環及使用疊代器時的fast-fail上。
注：本章的代碼均基于jdk 1.7.0_67
常用的底層資料結構主要有數組和連結清單。數組存儲區間連續，占用記憶體較多，尋址容易，插入和删除困難。連結清單存儲區間離散，占用記憶體較少，尋址困難，插入和删除容易。
hashmap要實作的是哈希表的效果，盡量實作o(1)級别的增删改查。它的具體實作則是同時使用了數組和連結清單，可以認為最外層是一個數組，數組的每個元素是一個連結清單的表頭。
對于新插入的資料或者待讀取的資料，hashmap将key的哈希值對數組長度取模，結果作為該entry在數組中的index。在計算機中，取模的代價遠高于位操作的代價，是以hashmap要求數組的長度必須為2的n次方。此時将key的哈希值對2^n-1進行與運算，其效果即與取模等效。hashmap并不要求使用者在指定hashmap容量時必須傳入一個2的n次方的整數，而是會通過integer.highestonebit算出比指定整數小的最大的2^n值，其實作方法如下。
由于key的哈希值的分布直接決定了所有資料在哈希表上的分布或者說決定了哈希沖突的可能性，是以為防止糟糕的key的hashcode實作（例如低位都相同，隻有高位不相同，與2^n-1取與後的結果都相同），jdk 1.7的hashmap通過如下方法使得最終的哈希值的二進制形式中的1盡量均勻分布進而盡可能減少哈希沖突。
當hashmap的size超過capacity*loadfactor時，需要對hashmap進行擴容。具體方法是，建立一個新的，長度為原來capacity兩倍的數組，保證新的capacity仍為2的n次方，進而保證上述尋址方式仍适用。同時需要通過如下transfer方法将原來的所有資料全部重新插入（rehash）到新的數組中。
該方法并不保證線程安全，而且在多線程并發調用時，可能出現死循環。其執行過程如下。從步驟2可見，轉移時連結清單順序反轉。
周遊原數組中的元素
對連結清單上的每一個節點周遊：用next取得要轉移那個元素的下一個，将e轉移到新數組的頭部，使用頭插法插入節點
循環2，直到連結清單節點全部轉移
循環1，直到所有元素全部轉移
單線程情況下，rehash無問題。下圖示範了單線程條件下的rehash過程
這裡假設有兩個線程同時執行了put操作并引發了rehash，執行了transfer方法，并假設線程一進入transfer方法并執行完next = e.next後，因為線程排程所配置設定時間片用完而“暫停”，此時線程二完成了transfer方法的執行。此時狀态如下。
接着線程1被喚醒，繼續執行第一輪循環的剩餘部分
結果如下圖所示
接着執行下一輪循環，結果狀态圖如下所示
繼續下一輪循環，結果狀态圖如下所示
此時循環連結清單形成，并且key(11)無法加入到線程1的新數組。在下一次通路該連結清單時會出現死循環。
在使用疊代器的過程中如果hashmap被修改，那麼<code>concurrentmodificationexception</code>将被抛出，也即fast-fail政策。
當hashmap的iterator()方法被調用時，會構造并傳回一個新的entryiterator對象，并将entryiterator的expectedmodcount設定為hashmap的modcount（該變量記錄了hashmap被修改的次數）。
在通過該iterator的next方法通路下一個entry時，它會先檢查自己的expectedmodcount與hashmap的modcount是否相等，如果不相等，說明hashmap被修改，直接抛出<code>concurrentmodificationexception</code>。該iterator的remove方法也會做類似的檢查。該異常的抛出意在提醒使用者及早意識到線程安全問題。
單線程條件下，為避免出現<code>concurrentmodificationexception</code>，需要保證隻通過hashmap本身或者隻通過iterator去修改資料，不能在iterator使用結束之前使用hashmap本身的方法修改資料。因為通過iterator删除資料時，hashmap的modcount和iterator的expectedmodcount都會自增，不影響二者的相等性。如果是增加資料，隻能通過hashmap本身的方法完成，此時如果要繼續周遊資料，需要重新調用iterator()方法進而重新構造出一個新的iterator，使得新iterator的expectedmodcount與更新後的hashmap的modcount相等。
多線程條件下，可使用<code>collections.synchronizedmap</code>方法構造出一個同步map，或者直接使用線程安全的concurrenthashmap。
java 7中的concurrenthashmap的底層資料結構仍然是數組和連結清單。與hashmap不同的是，concurrenthashmap最外層不是一個大的數組，而是一個segment的數組。每個segment包含一個與hashmap資料結構差不多的連結清單數組。整體資料結構如下圖所示。
在讀寫某個key時，先取該key的哈希值。并将哈希值的高n位對segment個數取模進而得到該key應該屬于哪個segment，接着如同操作hashmap一樣操作這個segment。為了保證不同的值均勻分布到不同的segment，需要通過如下方法計算哈希值。
同樣為了提高取模運算效率，通過如下計算，ssize即為大于concurrencylevel的最小的2的n次方，同時segmentmask為2^n-1。這一點跟上文中計算數組長度的方法一緻。對于某一個key的哈希值，隻需要向右移segmentshift位以取高sshift位，再與segmentmask取與操作即可得到它在segment數組上的索引。
segment繼承自reentrantlock，是以我們可以很友善的對每一個segment上鎖。
擷取segment中的hashentry時也使用了類似方法
對于寫操作，并不要求同時擷取所有segment的鎖，因為那樣相當于鎖住了整個map。它會先擷取該key-value對所在的segment的鎖，擷取成功後就可以像操作一個普通的hashmap一樣操作該segment，并保證該segment的安全性。
同時由于其它segment的鎖并未被擷取，是以理論上可支援concurrencylevel（等于segment的個數）個線程安全的并發讀寫。
這裡使用自旋鎖是因為自旋鎖的效率比較高，但是它消耗cpu資源比較多，是以在自旋次數超過門檻值時切換為互斥鎖。
put、remove和get操作隻需要關心一個segment，而size操作需要周遊所有的segment才能算出整個map的大小。一個簡單的方案是，先鎖住所有sgment，計算完後再解鎖。但這樣做，在做size操作時，不僅無法對map進行寫操作，同時也無法進行讀操作，不利于對map的并行操作。
為更好支援并發操作，concurrenthashmap會在不上鎖的前提逐個segment計算3次size，如果某相鄰兩次計算擷取的所有segment的更新次數（每個segment都與hashmap一樣通過modcount跟蹤自己的修改次數，segment每修改一次其modcount加一）相等，說明這兩次計算過程中無更新操作，則這兩次計算出的總size相等，可直接作為最終結果傳回。如果這三次計算過程中map有更新，則對所有segment加鎖重新計算size。該計算方法代碼如下
concurrenthashmap與hashmap相比，有以下不同點
concurrenthashmap線程安全，而hashmap非線程安全
hashmap允許key和value為null，而concurrenthashmap不允許
hashmap不允許通過iterator周遊的同時通過hashmap修改，而concurrenthashmap允許該行為，并且該更新對後續的周遊可見
注：本章的代碼均基于jdk 1.8.0_111
java 7為實作并行通路，引入了segment這一結構，實作了分段鎖，理論上最大并發度與segment個數相等。java 8為進一步提高并發性，摒棄了分段鎖的方案，而是直接使用一個大的數組。同時為了提高哈希碰撞下的尋址性能，java 8在連結清單長度超過一定門檻值（8）時将連結清單（尋址時間複雜度為o(n)）轉換為紅黑樹（尋址時間複雜度為o(long(n))）。其資料結構如下圖所示
java 8的concurrenthashmap同樣是通過key的哈希值與數組長度取模确定該key在數組中的索引。同樣為了避免不太好的key的hashcode設計，它通過如下方法計算得到key的最終哈希值。不同的是，java 8的concurrenthashmap作者認為引入紅黑樹後，即使哈希沖突比較嚴重，尋址效率也足夠高，是以作者并未在哈希值的計算上做過多設計，隻是将key的hashcode值與其高16位作異或并保證最高位為0（進而保證最終結果為正整數）。
對于讀操作，由于數組被volatile關鍵字修飾，是以不用擔心數組的可見性問題。同時每個元素是一個node執行個體（java 7中每個元素是一個hashentry），它的key值和hash值都由final修飾，不可變更，無須關心它們被修改後的可見性問題。而其value及對下一個元素的引用由volatile修飾，可見性也有保障。
對于key對應的數組元素的可見性，由unsafe的getobjectvolatile方法保證。
put方法和remove方法都會通過addcount方法維護map的size。size方法通過sumcount擷取由addcount方法維護的map的size。
<a href="http://www.jasongj.com/2016/01/17/java1_">java進階（一）annotation（注解）</a>
<a href="http://www.jasongj.com/java/thread_safe">java進階（二）當我們說線程安全時，到底在說什麼</a>
<a href="http://www.jasongj.com/java/multi_thread">java進階（三）多線程開發關鍵技術</a>
<a href="http://www.jasongj.com/java/thread_communication">java進階（四）線程間通信方式對比</a>
<a href="http://www.jasongj.com/java/nio_reactor/">java進階（五）nio和reactor模式進階</a>
<a href="http://www.jasongj.com/java/concurrenthashmap/">java進階（六）從concurrenthashmap的演進看java多線程核心技術</a>