HashMap在并發(fā)時不是線程安全的，當(dāng)多個線程對map進(jìn)行擴容會導(dǎo)致鏈表成環(huán)。不單單是這個問題，當(dāng)多個線程向同一個槽中插入數(shù)據(jù)，也不是線程安全的。
接下來分析一下ConcurrentHashMap的put方法
1.檢驗 key value值是否為null，為null直接拋出異常，hash map是允許null的存在的
2.得到key的hash值
3.死循環(huán)并更新tab變量的值。
4.如果容器沒有初始化，則初始化，調(diào)用initTable方法，該方法是通過一個調(diào)用unself中的CAS來控制并發(fā)
5.根據(jù)hash值來找到數(shù)組的下標(biāo)，如果對應(yīng)的位置為空，就創(chuàng)建一個Node對象用CAS方式添加到容器，并跳出循環(huán)
6.如果hash沖突了，即對應(yīng)的位置不為null，則判斷該槽是否被擴容了(-1表示被擴容了)，如果被擴容了，則返回新的數(shù)組
7.如果 hash 沖突 且 hash 值不是 -1，表示沒有被擴容。則進(jìn)行鏈表操作或者紅黑樹操作，注意，這里的 f 頭節(jié)點被鎖住了，保證了同時只有一個線程修改鏈表。防止出現(xiàn)鏈表成環(huán)。
8.和 HashMap 一樣，如果鏈表樹超過8，則修改鏈表為紅黑樹。
9.將數(shù)組加1（CAS方式），如果需要擴容，則調(diào)用 transfer 方法（非常復(fù)雜，以后再詳解）進(jìn)行移動和重新散列，該方法中，如果是槽中只有單個節(jié)點，則使用CAS直接插入，如果不是，則使用 synchronized 進(jìn)行同步，防止并發(fā)成環(huán)。
initTable 方法
該方法為了在并發(fā)環(huán)境下的安全，加入了一個 sizeCtl 變量來進(jìn)行判斷，只有當(dāng)一個線程通過CAS修改該變量成功后（默認(rèn)為0，改成 -1），該線程才能初始化數(shù)組。保證了初始化數(shù)組時的安全性。
hash算法的原由
Hash算法就是通過一種運算將Key值映射為Int型的hashcode，之后再對hashcode進(jìn)行高位運算（1.8New），取模運算，將其映射成一個小于Map數(shù)組大小的int值之后將鍵值對存入對應(yīng)的數(shù)組位置。為什么要這么做呢？當(dāng)HashMap中的數(shù)據(jù)數(shù)量較小時，經(jīng)過計算可以使得鍵值對較為均勻的存入數(shù)組的不同位置，盡量不生成鏈表。鏈表的時間復(fù)雜度為O（n），數(shù)組的時間復(fù)雜度是O（1），所以為了提高HashMap的效率，在數(shù)據(jù)量較小的時候盡可能的不生成鏈表。這也可以用來解釋為什么在鏈表長度過長的時候使用紅黑樹代替鏈表，紅黑樹的時間復(fù)雜度為O（log2(n)），在數(shù)據(jù)量較大時遠(yuǎn)遠(yuǎn)小于鏈表。
hash算法
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
ConcurrentHashMap的重要變量
//Map對應(yīng)的Hash桶數(shù)組
transient volatile Node<K,V>[] table;
//擴容時候新建的Hash桶數(shù)組，注意transient關(guān)鍵字，該字段不會被序列化
private transient volatile Node<K,V>[] nextTable;
//用于節(jié)點計數(shù)
private transient volatile long baseCount;
//非常非常非常重要的一個參數(shù)，統(tǒng)御全局
//sizeCtl = -1，表示有線程正在進(jìn)行初始化操作，防止多線程同時初始化Map
//sizeCtl = -(1 + nThreads)，表示有nThreads個線程正在進(jìn)行擴容操作
//sizeCtl > 0，表示接下來的初始化操作中的Map容量，或者表示初始化/擴容完成后的閾值
//sizeCtl = 0，默認(rèn)值
private transient volatile int sizeCtl;
//用以維護(hù)多線程擴容時候的線程安全
private transient volatile int transferIndex;
鎖的方式
部分鎖定+CAS算法來進(jìn)行實現(xiàn)線程安全的。CAS算法也可以認(rèn)為是樂觀鎖的一種,其中拋棄了原有的 Segment 分段鎖，而采用了 CAS + synchronized 來保證并發(fā)安全性。
