并發(fā)環(huán)境下HashMap是不安全的,容易造成并發(fā)修改異掣蠼或者死鎖現(xiàn)象
而Collections下提供的synchionizedMap雖然因?yàn)榧恿藄ynchionized而變得安全,卻也因此極大的降低了性能
由于以上情況,就使得ConcurrentHashMap應(yīng)運(yùn)而生
如何優(yōu)化Hashtable添履？
-
通過鎖細(xì)粒度化角雷，將整鎖拆解成多個(gè)鎖進(jìn)行優(yōu)化將整鎖拆為十六個(gè)子鎖,一個(gè)線程每次只操作一個(gè)鎖并不干擾其他線程操作其他鎖,理論上性能提高了16倍
ConcurrentHashMap的擴(kuò)容因子SizeCtl是用volatile修飾的對(duì)其他線程可見
ConcurrentHashMap可以通過computreIfAbsent()和computre()構(gòu)建java本地緩存,降低程序計(jì)算量
ConcurrentHashMap:put方法的源碼邏輯
1.判斷Node[]數(shù)組是否初始化读跷，沒有則進(jìn)行初始化操作
2.通過hash定位數(shù)組的索引坐標(biāo)少漆，是否有Node節(jié)點(diǎn)逸嘀，如果沒有則使用CAS進(jìn)行添加（鏈表的頭節(jié)點(diǎn)）枉氮，添加失敗則進(jìn)入下次循環(huán)。
3.檢查到內(nèi)部正在擴(kuò)容抬旺，就幫助它一塊擴(kuò)容弊予。(主要做數(shù)據(jù)標(biāo)記,輔助遷移等)
4.如果f=null(頭節(jié)點(diǎn)不為空)，則使用synchronized鎖住元素（鏈表/紅黑二叉樹的頭元素）
??4.1如果是Node（鏈表結(jié)構(gòu)）則執(zhí)行鏈表的添加操作开财。
??4.2如果是TreeNode（樹型結(jié)構(gòu)）則執(zhí)行樹添加操作汉柒。
5.判斷鏈表長(zhǎng)度已經(jīng)達(dá)到臨界值8，當(dāng)然這個(gè)8是默認(rèn)值责鳍，大家也可以去做調(diào)整碾褂，當(dāng)節(jié)點(diǎn)數(shù)超過這個(gè)值就需要把鏈表轉(zhuǎn)換為樹結(jié)構(gòu)。
ConcurrentHashMap總結(jié)：比起分段鎖Segment历葛，鎖拆得更細(xì)
- 首先使用無鎖操作CAS插入頭節(jié)點(diǎn)正塌，失敗則循環(huán)重試
- 若頭節(jié)點(diǎn)已存在，則通過synronchized嘗試獲取頭節(jié)點(diǎn)的同步鎖恤溶，再進(jìn)行操作
public V put(K key, V value) {
return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
//onlyIfAbsent的意思是在put一個(gè)KV時(shí)传货，如果K已經(jīng)存在什么也不做則返回null
//如果不存在則put操作后返回V值
final V putVal(K key, V value, boolean onlyIfAbsent) {
//ConcurrentHashMap中是不能有空K或空V的
if (key == null || value == null) throw new NullPointerException();
//hash算法得到hash值
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
//如果table是空的，就去初始化宏娄，下一個(gè)循環(huán)就不是空的了
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//如果沒有取到值，即取i位的元素是空的逮壁，為什么i取值是(n-1)&hash??
//這是hash的精華所在孵坚，在這里可以先思考一下
//此時(shí)直接到KV包裝成Node節(jié)點(diǎn)放在i位置即可
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
//MOVED，定義為-1窥淆。標(biāo)記原table正在執(zhí)行擴(kuò)容任務(wù)卖宠，可以去幫忙(支持多線程擴(kuò)容)
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
//這種情況是，在i的位置找到了一個(gè)元素忧饭，說明此元素的K與之間的某個(gè)K的hash結(jié)果是一樣的
//
V oldVal = null;
synchronized (f) {//同步鎖住第一個(gè)元素
if (tabAt(tab, i) == f) {//為了安全起見扛伍，再一次判斷
if (fh >= 0) {//節(jié)點(diǎn)的hash值大于0，說明是一個(gè)鏈表結(jié)構(gòu)
binCount = 1;//記錄鏈表的元素個(gè)數(shù)
for (Node<K,V> e = f;; ++binCount) {
K ek;
//判斷給定的key是否與取出的key相同词裤，如果是則替換元素
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;//直接跳出刺洒，這是一種思想。在編程時(shí)可以減少一些if else判斷
}
//否則就是不相等吼砂，那就把此元素放在鏈表的最后一個(gè)元素
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
//如果不是鏈表逆航，而是紅黑樹
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
//把元素放入樹中的對(duì)應(yīng)位置
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
//鏈表的元素大于等于8時(shí)，就把鏈表轉(zhuǎn)換為紅黑樹
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
//新添加一個(gè)元素渔肩，size加1因俐，可能會(huì)觸發(fā)擴(kuò)容
addCount(1L, binCount);
return null;
}
CAS性能很高，但是我知道synchronized性能可不咋地，為啥jdk1.8升級(jí)之后反而多了synchronized抹剩？
synchronized之前一直都是重量級(jí)的鎖撑帖，但是后來java官方是對(duì)他進(jìn)行過升級(jí)的，他現(xiàn)在采用的是鎖升級(jí)的方式去做的澳眷。
針對(duì) synchronized 獲取鎖的方式胡嘿，JVM 使用了鎖升級(jí)的優(yōu)化方式，就是先使用偏向鎖優(yōu)先同一線程使用,然后再次獲取鎖境蔼，如果失敗灶平，就升級(jí)為 CAS 輕量級(jí)鎖，如果失敗就會(huì)短暫自旋箍土，防止線程被系統(tǒng)掛起逢享。最后如果一直都失敗就升級(jí)為重量級(jí)鎖。
所以是一步步升級(jí)上去的吴藻，最初也是通過很多輕量級(jí)的方式鎖定的瞒爬。
ConcurrentHashMap的get操作又是怎么樣子的呢？
- 根據(jù)計(jì)算出來的 hashcode 尋址沟堡，如果就在桶上那么直接返回值侧但。
- 如果是紅黑樹那就按照樹的方式獲取值。
- 就不滿足那就按照鏈表的方式遍歷獲取值航罗。
- 另外concurrenthashmap的值以及next指針等都是用volatile修飾的不用擔(dān)心線程之間可見性問題
關(guān)于ConcurrentHashMap主要注意的地方
1.size（）方法和mappingCount方法的異同禀横，兩者計(jì)算是否準(zhǔn)確？
??1.1 size最大返回 int 最大值粥血，但是這個(gè) Map 的長(zhǎng)度是有可能超過 int 最大值的
mappingCount 方法的返回值是 long 類型柏锄。所以不必限制最大值必須是Integer.MAX_VALUE
??1.2 public long mappingCount()返回映射的數(shù)量。應(yīng)該使用此方法而不是size（）复亏，因?yàn)镃oncurrentHashMap可能包含的映射數(shù)多于可以表示為int的映射趾娃。返回的值是估計(jì)值; 如果有并發(fā)插入或刪除，實(shí)際計(jì)數(shù)可能會(huì)有所不同缔御。
size()返回此映射中鍵 - 值映射的數(shù)量抬闷。2.CouncurrentHahsMap的并發(fā)擴(kuò)容問題
CouncurrentHahsMap在添加元素時(shí)候會(huì)判斷是否有線程在擴(kuò)容,如果有,它會(huì)調(diào)用一個(gè)helpTransfer()方法,在這個(gè)方法里會(huì)重新確認(rèn)一下,如果確實(shí)擴(kuò)容,會(huì)添加一個(gè)sizeCtl開啟一個(gè)輔助線程幫助擴(kuò)容.3我們這里保證了并發(fā)的寫put操作是安全的,那么get操作沒有加鎖,他是怎么保證并發(fā)讀寫線程安全的呢???
答案:
get操作可以無鎖是由于Node的元素val和指針next都是用volatile修飾的，在多線程環(huán)境下線程A修改結(jié)點(diǎn)的val或者新增節(jié)點(diǎn)的時(shí)候是對(duì)線程B可見的耕突。- putval里的addCount原理https://blog.csdn.net/u010285974/article/details/106301938/
HashMap笤成、Hashtable、ConccurentHashMap三者區(qū)別
參考
https://blog.csdn.net/xpsallwell/article/details/88071038
https://blog.csdn.net/qq_27037443/article/details/94441885
