HashMap在put的時候掷贾，插入的元素超過了容量（由負(fù)載因子決定）的范圍就會觸發(fā)擴(kuò)容操作睛榄，就是rehash，這個會重新將原數(shù)組的內(nèi)容重新hash到新的擴(kuò)容數(shù)組中想帅，在多線程的環(huán)境下场靴，存在同時其他的元素也在進(jìn)行put操作，如果hash值相同港准，可能出現(xiàn)同時在同一數(shù)組下用鏈表表示旨剥，造成閉環(huán)，導(dǎo)致在get時會出現(xiàn)死循環(huán)浅缸，所以HashMap是線程不安全的轨帜。
線程安全的HashTable
HashTable容器使用synchronized來保證線程安全，但在線程競爭激烈的情況下HashTable的效率非常低下疗杉。因為當(dāng)一個線程訪問HashTable的同步方法時阵谚，其他線程訪問HashTable的同步方法時，可能會進(jìn)入阻塞或輪詢狀態(tài)烟具。如線程A使用put進(jìn)行添加元素梢什，線程B不但不能使用put方法添加元素，并且也不能使用get方法來獲取元素朝聋，所以競爭越激烈效率越低嗡午。
ConcurrentHashMap的鎖分段技術(shù)
HashTable容器在競爭激烈的并發(fā)環(huán)境下表現(xiàn)出效率低下的原因，是因為所有訪問HashTable的線程都必須競爭同一把鎖冀痕，那假如容器里有多把鎖荔睹，每一把鎖用于鎖容器其中一部分?jǐn)?shù)據(jù)狸演，那么當(dāng)多線程訪問容器里不同數(shù)據(jù)段的數(shù)據(jù)時，線程間就不會存在鎖競爭僻他，從而可以有效的提高并發(fā)訪問效率宵距，這就是ConcurrentHashMap所使用的鎖分段技術(shù)，首先將數(shù)據(jù)分成一段一段的存儲吨拗，然后給每一段數(shù)據(jù)配一把鎖满哪，當(dāng)一個線程占用鎖訪問其中一個段數(shù)據(jù)的時候，其他段的數(shù)據(jù)也能被其他線程訪問劝篷。
在JDK1.7版本中哨鸭，ConcurrentHashMap的數(shù)據(jù)結(jié)構(gòu)是由一個Segment數(shù)組和多個HashEntry組成，如下圖所示：
Segment數(shù)組的意義就是將一個大的table分割成多個小的table來進(jìn)行加鎖娇妓，也就是上面的提到的鎖分段技術(shù)像鸡，而每一個Segment元素存儲的是HashEntry數(shù)組+鏈表，這個和HashMap的數(shù)據(jù)存儲結(jié)構(gòu)一樣
ConcurrentHashMap實現(xiàn)存儲和讀取
1哈恰、存儲put()
ConcurrentHashMap的put操作是直接委托給Segment的put方法只估，直接看Segment的put方法：
V put(K key, int hash, V value, boolean onlyIfAbsent) {
lock();
try {
int c = count;
if (c++ > threshold) // ensure capacity
rehash();
HashEntry<K,V>[] tab = table;
int index = hash & (tab.length - 1);
HashEntry<K,V> first = tab[index];
HashEntry<K,V> e = first;
while (e != null && (e.hash != hash || !key.equals(e.key)))
e = e.next;
V oldValue;
if (e != null) {
oldValue = e.value;
if (!onlyIfAbsent)
e.value = value;
}
else {
oldValue = null;
++modCount;
tab[index] = new HashEntry<K,V>(key, hash, first, value);
count = c; // write-volatile
}
return oldValue;
} finally {
unlock();
}
}
該方法也是在持有段鎖(鎖定整個segment)的情況下執(zhí)行的，這當(dāng)然是為了并發(fā)的安全蕊蝗，修改數(shù)據(jù)是不能并發(fā)進(jìn)行的仅乓，必須得有個判斷是否超限的語句以確保容量不足時能夠rehash。接著是找是否存在同樣一個key的結(jié)點蓬戚，如果存在就直接替換這個結(jié)點的值。否則創(chuàng)建一個新的結(jié)點并添加到hash鏈的頭部宾抓，這時一定要修改modCount和count的值子漩，同樣修改count的值一定要放在最后一步。put方法調(diào)用了rehash方法石洗，原來segment里面才是真正的HashTable幢泼，即每個segment是一個傳統(tǒng)意義上的HashTable
由于put方法里需要對共享變量進(jìn)行寫入操作，所以為了線程安全讲衫，在操作共享變量時必須得加鎖缕棵。Put方法首先定位到Segment，然后在Segment里進(jìn)行插入操作涉兽。插入操作需要經(jīng)歷兩個步驟招驴，第一步判斷是否需要對Segment里的HashEntry數(shù)組進(jìn)行擴(kuò)容，第二步定位添加元素的位置然后放在HashEntry數(shù)組里枷畏。
是否需要擴(kuò)容别厘。在插入元素前會先判斷Segment里的HashEntry數(shù)組是否超過容量（threshold），如果超過閥值拥诡，數(shù)組進(jìn)行擴(kuò)容触趴。值得一提的是氮发，Segment的擴(kuò)容判斷比HashMap更恰當(dāng)，因為HashMap是在插入元素后判斷元素是否已經(jīng)到達(dá)容量的冗懦，如果到達(dá)了就進(jìn)行擴(kuò)容爽冕，但是很有可能擴(kuò)容之后沒有新元素插入，這時HashMap就進(jìn)行了一次無效的擴(kuò)容披蕉。
如何擴(kuò)容颈畸。擴(kuò)容的時候首先會創(chuàng)建一個兩倍于原容量的數(shù)組，然后將原數(shù)組里的元素進(jìn)行再hash后插入到新的數(shù)組里嚣艇。為了高效ConcurrentHashMap不會對整個容器進(jìn)行擴(kuò)容承冰，而只對某個segment進(jìn)行擴(kuò)容。
2食零、讀取get()
ConcurrentHashMap的get操作也是委托給Segment的get方法困乒，直接看Segment的get方法：
V get(Object key, int hash) {
if (count != 0) { // read-volatile 當(dāng)前桶的數(shù)據(jù)個數(shù)是否為0
HashEntry<K,V> e = getFirst(hash); 得到頭節(jié)點
while (e != null) {
if (e.hash == hash && key.equals(e.key)) {
V v = e.value;
if (v != null)
return v;
return readValueUnderLock(e); // recheck
}
e = e.next;
}
}
returnnull;
}
get操作的高效之處在于整個get過程不需要加鎖，除非讀到的值是空的才會加鎖重讀贰谣，我們知道HashTable容器的get方法是需要加鎖的娜搂，那么ConcurrentHashMap的get操作是如何做到不加鎖的呢？原因是它的get方法里將要使用的共享變量都定義成volatile吱抚，如用于統(tǒng)計當(dāng)前Segement大小的count字段和用于存儲值的HashEntry的value百宇。定義成volatile的變量，能夠在線程之間保持可見性秘豹，能夠被多線程同時讀携御，并且保證不會讀到過期的值，但是只能被單線程寫（有一種情況可以被多線程寫既绕，就是寫入的值不依賴于原值）啄刹，在get操作里只需要讀不需要寫共享變量count和value，所以可以不用加鎖凄贩。
3誓军、操作size()
ConcurrentHashMap的做法是先嘗試2次通過不鎖住Segment的方式來統(tǒng)計各個Segment大小，如果統(tǒng)計的過程中疲扎，容器的count發(fā)生了變化昵时，則再采用加鎖的方式來統(tǒng)計所有Segment的大小。那么ConcurrentHashMap是如何判斷在統(tǒng)計的時候容器是否發(fā)生了變化呢椒丧？使用modCount變量壹甥，在put , remove和clean方法里操作元素前都會將變量modCount進(jìn)行加1，那么在統(tǒng)計size前后比較modCount是否發(fā)生變化瓜挽，從而得知容器的大小是否發(fā)生變化盹廷。
