你了解ConcurrentHashMap嗎？ConcurrentHashMap九連問
多線程環(huán)境下，使用Hashmap進(jìn)行put操作會造成數(shù)據(jù)覆蓋，應(yīng)該使用支持多線程的 ConcurrentHashMap。
HashMap為什么線程不安全
put的不安全
由于多線程對HashMap進(jìn)行put操作，調(diào)用了HashMap的putVal()，具體原因：
- 假設(shè)兩個線程A、B都在進(jìn)行put操作，并且hash函數(shù)計(jì)算出的插入下標(biāo)是相同的；
當(dāng)線程A執(zhí)行完第六行由于時間片耗盡導(dǎo)致被掛起，而線程B得到時間片后在該下標(biāo)處插入了元素，完成了正常的插入；
接著線程A獲得時間片，由于之前已經(jīng)進(jìn)行了hash碰撞的判斷，所有此時不會再進(jìn)行判斷，而是直接進(jìn)行插入；
最終就導(dǎo)致了線程B插入的數(shù)據(jù)被線程A覆蓋了，從而線程不安全。
- 代碼的第38行處有個++size，線程A、B，這兩個線程同時進(jìn)行put操作時，假設(shè)當(dāng)前HashMap的zise大小為10；
- 當(dāng)線程A執(zhí)行到第38行代碼時，從主內(nèi)存中獲得size的值為10后準(zhǔn)備進(jìn)行+1操作，但是由于時間片耗盡只好讓出CPU；
- 接著線程B拿到CPU后從主內(nèi)存中拿到size的值10進(jìn)行+1操作，完成了put操作并將size=11寫回主內(nèi)存；
- 接著線程A再次拿到CPU并繼續(xù)執(zhí)行(此時size的值仍為10)，當(dāng)執(zhí)行完put操作后，還是將size=11寫回內(nèi)存；
- 此時，線程A、B都執(zhí)行了一次put操作，但是size的值只增加了1，所有說還是由于數(shù)據(jù)覆蓋又導(dǎo)致了線程不安全。
1 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
2 boolean evict) {
3 Node <K, V> [] tab; Node <K, V> p; int n, i;
4 if ((tab = table) == null || (n = tab.length) == 0)
5 n = (tab = resize()).length;
6 if ((p = tab[i = (n - 1) & hash]) == null) //
tab[i] = newNode(hash, key, value, null);
else {
Node < K, V > e;
K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode <K, V> ) p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0;; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
38 if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}擴(kuò)容不安全
Java7中頭插法擴(kuò)容會導(dǎo)致死循環(huán)和數(shù)據(jù)丟失，Java8中將頭插法改為尾插法后死循環(huán)和數(shù)據(jù)丟失已經(jīng)得到解決，但仍然有數(shù)據(jù)覆蓋的問題。
這是jdk7中存在的問題
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry <K, V> e: table) {
while (null != e) {
Entry <K, V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}transfer過程如下：
- 對索引數(shù)組中的元素遍歷
- 對鏈表上的每一個節(jié)點(diǎn)遍歷：用 next 取得要轉(zhuǎn)移那個元素的下一個，將 e 轉(zhuǎn)移到新 Hash 表的頭部，使用頭插法插入節(jié)點(diǎn)。
- 循環(huán)2，直到鏈表節(jié)點(diǎn)全部轉(zhuǎn)移
- 循環(huán)1，直到所有索引數(shù)組全部轉(zhuǎn)移
注意 e.next = newTable[i] 和newTable[i] = e 這兩行代碼，就會導(dǎo)致鏈表的順序翻轉(zhuǎn)。
擴(kuò)容操作就是新生成一個新的容量的數(shù)組，然后對原數(shù)組的所有鍵值對重新進(jìn)行計(jì)算和寫入新的數(shù)組，之后指向新生成的數(shù)組。當(dāng)多個線程同時檢測到總數(shù)量超過門限值的時候就會同時調(diào)用resize操作，各自生成新的數(shù)組并rehash后賦給該map底層的數(shù)組table，結(jié)果最終只有最后一個線程生成的新數(shù)組被賦給table變量，其他線程的均會丟失。而且當(dāng)某些線程已經(jīng)完成賦值而其他線程剛開始的時候，就會用已經(jīng)被賦值的table作為原始數(shù)組，這樣也會有問題。
Map m = Collections.synchronizedMap(new LinkedHashMap(...));ConcurrentHashMap原理？put執(zhí)行流程？
回顧hashMap的put方法過程
- 計(jì)算出key的槽位
- 根據(jù)槽位類型進(jìn)行操作(鏈表，紅黑樹)
- 根據(jù)槽位中成員數(shù)量進(jìn)行數(shù)據(jù)轉(zhuǎn)換，擴(kuò)容等操作
圖片
如何高效的執(zhí)行并發(fā)操作：根據(jù)上面hashMap的數(shù)據(jù)結(jié)構(gòu)可以直觀的看到，如果以整個容器為一個資源進(jìn)行鎖定，那么就變?yōu)榱舜胁僮?。而根?jù)hash表的特性，具有沖突的操作只會出現(xiàn)在同一槽位，而與其它槽位的操作互不影響?；诖朔N判斷，那么就可以將資源鎖粒度縮小到槽位上，這樣熱點(diǎn)一分散，沖突的概率就大大降低，并發(fā)性能就能得到很好的增強(qiáng)。
圖片
總體上來說，就是采用 Node + CAS + synchronized 來保證并發(fā)安全。數(shù)據(jù)結(jié)構(gòu)跟 HashMap 1.8 的結(jié)構(gòu)類似，數(shù)組+鏈表/紅黑二叉樹。Java 8 在鏈表長度超過一定閾值（8）時將鏈表（尋址時間復(fù)雜度為 O(N)）轉(zhuǎn)換為紅黑樹（尋址時間復(fù)雜度為 O(log(N))）。
Java 8 中，鎖粒度更細(xì)，synchronized 只鎖定當(dāng)前鏈表或紅黑二叉樹的首節(jié)點(diǎn)，這樣只要 hash 不沖突，就不會產(chǎn)生并發(fā)，就不會影響其他 Node 的讀寫，效率大幅提升。
ConcurrentHashMap 的get 方法是否需要加鎖?
不需要加鎖。
通過 volatile 關(guān)鍵字，concurentHashmap能夠確保 get 方法的線程安全，即使在寫入發(fā)生時，讀取線程仍然能夠獲得最新的數(shù)據(jù)，不會引發(fā)并發(fā)問題
具體是通過 unsafe#getxxxvolatile 和用 volatile 來修飾節(jié)點(diǎn)的 val 和 next 指針來實(shí)現(xiàn)的。
ConcurrentHashMap 和 Hashtable 的區(qū)別？
相同點(diǎn)：ConcurrentHashMap 和 Hashtable 都是線程安全的，可以在多個線程同時訪問它們而不需要額外的同步措施。
不同點(diǎn)：
- Hashtable通過使用synchronized修飾方法的方式來實(shí)現(xiàn)多線程同步，因此，Hashtable的同步會鎖住整個數(shù)組。在高并發(fā)的情況下，性能會非常差。ConcurrentHashMap采用了使用數(shù)組+鏈表+紅黑樹數(shù)據(jù)結(jié)構(gòu)和CAS原子操作實(shí)現(xiàn)；synchronized鎖住桶，以及大量的CAS操作來保證線程安全。
- Hashtable 讀寫操作都加鎖，ConcurrentHashMap的讀操作不加鎖，寫操作加鎖
- Hashtable默認(rèn)的大小為11，當(dāng)達(dá)到閾值后，每次按照下面的公式對容量進(jìn)行擴(kuò)充：newCapacity = oldCapacity * 2 + 1。ConcurrentHashMap默認(rèn)大小是16，擴(kuò)容時容量擴(kuò)大為原來的2倍。
- Null 鍵和值： ConcurrentHashMap 不允許存儲 null 鍵或 null 值，如果嘗試存儲 null 鍵或值，會拋出 NullPointerException。 Hashtable 也不允許存儲 null 鍵和值。
為什么JDK8不用ReentrantLock而用synchronized
- 減少內(nèi)存開銷：如果使用ReentrantLock則需要節(jié)點(diǎn)繼承AQS來獲得同步支持，增加內(nèi)存開銷，而1.8中只有頭節(jié)點(diǎn)需要進(jìn)行同步。
- 內(nèi)部優(yōu)化：synchronized則是JVM直接支持的，JVM能夠在運(yùn)行時作出相應(yīng)的優(yōu)化措施：鎖粗化、鎖消除、鎖自旋等等。
為什么key 和 value 不允許為 null
HashMap中，null可以作為鍵或者值都可以。而在ConcurrentHashMap中，key和value都不允許為null。
ConcurrentHashMap的作者——Doug Lea的解釋如下：
圖片
主要意思就是說：
ConcurrentMap（如ConcurrentHashMap、ConcurrentSkipListMap）不允許使用null值的主要原因是，在非并發(fā)的Map中（如HashMap)，是可以容忍模糊性（二義性）的，而在并發(fā)Map中是無法容忍的。
假如說，所有的Map都支持null的話，那么map.get(key)就可以返回null，但是，這時候就會存在一個不確定性，當(dāng)你拿到null的時候，你是不知道他是因?yàn)楸緛砭痛媪艘粋€null進(jìn)去還是說就是因?yàn)闆]找到而返回了null。
在HashMap中，因?yàn)樗脑O(shè)計(jì)就是給單線程用的，所以當(dāng)我們map.get(key)返回null的時候，我們是可以通過map.contains(key)檢查來進(jìn)行檢測的，如果它返回true，則認(rèn)為是存了一個null，否則就是因?yàn)闆]找到而返回了null。
但是，像ConcurrentHashMap，它是為并發(fā)而生的，它是要用在并發(fā)場景中的，當(dāng)我們map.get(key)返回null的時候，是沒辦法通過map.contains(key)(ConcurrentHashMap有這個方法，但不可靠)檢查來準(zhǔn)確的檢測，因?yàn)樵跈z測過程中可能會被其他線程鎖修改，而導(dǎo)致檢測結(jié)果并不可靠。
所以，為了讓ConcurrentHashMap的語義更加準(zhǔn)確，不存在二義性的問題，他就不支持null。
使用了ConcurrentHashMap 就能保證業(yè)務(wù)的線程安全嗎？
需要知道的是，集合線程安全并不等于業(yè)務(wù)線程安全，并不是說使用了線程安全的集合 如ConcurrentHashMap 就能保證業(yè)務(wù)的線程安全。這是因?yàn)?，ConcurrentHashMap只能保證put時是安全的，但是在put操作前如果還有其他的操作，那業(yè)務(wù)并不一定是線程安全的。
例如存在復(fù)合操作，也就是存在多個基本操作(如put、get、remove、containsKey等)組成的操作，例如先判斷某個鍵是否存在containsKey(key)，然后根據(jù)結(jié)果進(jìn)行插入或更新put(key, value)。這種操作在執(zhí)行過程中可能會被其他線程打斷，導(dǎo)致結(jié)果不符合預(yù)期。
例如，有兩個線程 A 和 B 同時對 ConcurrentHashMap 進(jìn)行復(fù)合操作，如下：
// 線程 A
if (!map.containsKey(key)) {
map.put(key, value);
}
// 線程 B
if (!map.containsKey(key)) {
map.put(key, anotherValue);
}如果線程 A 和 B 的執(zhí)行順序是這樣：
- 線程 A 判斷 map 中不存在 key
- 線程 B 判斷 map 中不存在 key
- 線程 B 將 (key, anotherValue) 插入 map
- 線程 A 將 (key, value) 插入 map
那么最終的結(jié)果是 (key, value)，而不是預(yù)期的 (key, anotherValue)。這就是復(fù)合操作的非原子性導(dǎo)致的問題。
那如何保證 ConcurrentHashMap 復(fù)合操作的原子性呢？
ConcurrentHashMap 提供了一些原子性的復(fù)合操作，如 putIfAbsent、compute、computeIfAbsent 、computeIfPresent、merge等。這些方法都可以接受一個函數(shù)作為參數(shù)，根據(jù)給定的 key 和 value 來計(jì)算一個新的 value，并且將其更新到 map 中。
上面的代碼可以改寫為：
// 線程 A
map.putIfAbsent(key, value);
// 線程 B
map.putIfAbsent(key, anotherValue);或者：
// 線程 A
map.computeIfAbsent(key, k -> value);
// 線程 B
map.computeIfAbsent(key, k -> anotherValue);很多同學(xué)可能會說了，這種情況也能加鎖同步呀！確實(shí)可以，但不建議使用加鎖的同步機(jī)制，違背了使用 ConcurrentHashMap 的初衷。在使用 ConcurrentHashMap 的時候，盡量使用這些原子性的復(fù)合操作方法來保證原子性。
SynchronizedMap和ConcurrentHashMap有什么區(qū)別？
SynchronizedMap一次鎖住整張表來保證線程安全，所以每次只能有一個線程來訪問map。
JDK1.8 ConcurrentHashMap采用CAS和synchronized來保證并發(fā)安全。數(shù)據(jù)結(jié)構(gòu)采用數(shù)組+鏈表/紅黑二叉樹。synchronized只鎖定當(dāng)前鏈表或紅黑二叉樹的首節(jié)點(diǎn)，支持并發(fā)訪問、修改。 另外ConcurrentHashMap使用了一種不同的迭代方式。當(dāng)iterator被創(chuàng)建后集合再發(fā)生改變就不再是拋出ConcurrentModificationException，取而代之的是在改變時new新的數(shù)據(jù)從而不影響原有的數(shù)據(jù) ，iterator完成后再將頭指針替換為新的數(shù)據(jù) ，這樣iterator線程可以使用原來老的數(shù)據(jù)，而寫線程也可以并發(fā)的完成改變。
