資訊專(zhuān)欄INFORMATION COLUMN
摘要：那么，如果之后不是簡(jiǎn)單的操作，而是還有其它業(yè)務(wù)操作，之后才是，比如下面這樣，這該怎么辦呢其它業(yè)務(wù)操作這時(shí)候就沒(méi)辦法使用提供的方法了，只能業(yè)務(wù)自己來(lái)保證線程安全了，比如下面這樣其它業(yè)務(wù)操作這樣雖然不太友好，但是最起碼能保證業(yè)務(wù)邏輯是正確的。
刪除元素
刪除元素跟添加元素一樣，都是先找到元素所在的桶，然后采用分段鎖的思想鎖住整個(gè)桶，再進(jìn)行操作。
public V remove(Object key) {
// 調(diào)用替換節(jié)點(diǎn)方法
return replaceNode(key, null, null);
}
final V replaceNode(Object key, V value, Object cv) {
// 計(jì)算hash
int hash = spread(key.hashCode());
// 自旋
for (Node[] tab = table;;) {
Node f; int n, i, fh;
if (tab == null || (n = tab.length) == 0 ||
(f = tabAt(tab, i = (n - 1) & hash)) == null)
// 如果目標(biāo)key所在的桶不存在，跳出循環(huán)返回null
break;
else if ((fh = f.hash) == MOVED)
// 如果正在擴(kuò)容中，協(xié)助擴(kuò)容
tab = helpTransfer(tab, f);
else {
V oldVal = null;
// 標(biāo)記是否處理過(guò)
boolean validated = false;
synchronized (f) {
// 再次驗(yàn)證當(dāng)前桶第一個(gè)元素是否被修改過(guò)
if (tabAt(tab, i) == f) {
if (fh >= 0) {
// fh>=0表示是鏈表節(jié)點(diǎn)
validated = true;
// 遍歷鏈表尋找目標(biāo)節(jié)點(diǎn)
for (Node e = f, pred = null;;) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
// 找到了目標(biāo)節(jié)點(diǎn)
V ev = e.val;
// 檢查目標(biāo)節(jié)點(diǎn)舊value是否等于cv
if (cv == null || cv == ev ||
(ev != null && cv.equals(ev))) {
oldVal = ev;
if (value != null)
// 如果value不為空則替換舊值
e.val = value;
else if (pred != null)
// 如果前置節(jié)點(diǎn)不為空
// 刪除當(dāng)前節(jié)點(diǎn)
pred.next = e.next;
else
// 如果前置節(jié)點(diǎn)為空
// 說(shuō)明是桶中第一個(gè)元素，刪除之
setTabAt(tab, i, e.next);
}
break;
}
pred = e;
// 遍歷到鏈表尾部還沒(méi)找到元素，跳出循環(huán)
if ((e = e.next) == null)
break;
}
}
else if (f instanceof TreeBin) {
// 如果是樹(shù)節(jié)點(diǎn)
validated = true;
TreeBin t = (TreeBin)f;
TreeNode r, p;
// 遍歷樹(shù)找到了目標(biāo)節(jié)點(diǎn)
if ((r = t.root) != null &&
(p = r.findTreeNode(hash, key, null)) != null) {
V pv = p.val;
// 檢查目標(biāo)節(jié)點(diǎn)舊value是否等于cv
if (cv == null || cv == pv ||
(pv != null && cv.equals(pv))) {
oldVal = pv;
if (value != null)
// 如果value不為空則替換舊值
p.val = value;
else if (t.removeTreeNode(p))
// 如果value為空則刪除元素
// 如果刪除后樹(shù)的元素個(gè)數(shù)較少則退化成鏈表
// t.removeTreeNode(p)這個(gè)方法返回true表示刪除節(jié)點(diǎn)后樹(shù)的元素個(gè)數(shù)較少
setTabAt(tab, i, untreeify(t.first));
}
}
}
}
}
// 如果處理過(guò)，不管有沒(méi)有找到元素都返回
if (validated) {
// 如果找到了元素，返回其舊值
if (oldVal != null) {
// 如果要替換的值為空，元素個(gè)數(shù)減1
if (value == null)
addCount(-1L, -1);
return oldVal;
}
break;
}
}
}
// 沒(méi)找到元素返回空
return null;
}
計(jì)算hash；
如果所在的桶不存在，表示沒(méi)有找到目標(biāo)元素，返回；
如果正在擴(kuò)容，則協(xié)助擴(kuò)容完成后再進(jìn)行刪除操作；
如果是以鏈表形式存儲(chǔ)的，則遍歷整個(gè)鏈表查找元素，找到之后再刪除；
如果是以樹(shù)形式存儲(chǔ)的，則遍歷樹(shù)查找元素，找到之后再刪除；
如果是以樹(shù)形式存儲(chǔ)的，刪除元素之后樹(shù)較小，則退化成鏈表；
如果確實(shí)刪除了元素，則整個(gè)map元素個(gè)數(shù)減1，并返回舊值；
如果沒(méi)有刪除元素，則返回null；
獲取元素獲取元素，根據(jù)目標(biāo)key所在桶的第一個(gè)元素的不同采用不同的方式獲取元素，關(guān)鍵點(diǎn)在于find()方法的重寫(xiě)。
public V get(Object key) {
Node[] tab; Node e, p; int n, eh; K ek;
// 計(jì)算hash
int h = spread(key.hashCode());
// 如果元素所在的桶存在且里面有元素
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
// 如果第一個(gè)元素就是要找的元素，直接返回
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
// hash小于0，說(shuō)明是樹(shù)或者正在擴(kuò)容
// 使用find尋找元素，find的尋找方式依據(jù)Node的不同子類(lèi)有不同的實(shí)現(xiàn)方式
return (p = e.find(h, key)) != null ? p.val : null;
// 遍歷整個(gè)鏈表尋找元素
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
hash到元素所在的桶；
如果桶中第一個(gè)元素就是該找的元素，直接返回；
如果是樹(shù)或者正在遷移元素，則調(diào)用各自Node子類(lèi)的find()方法尋找元素；
如果是鏈表，遍歷整個(gè)鏈表尋找元素；
獲取元素沒(méi)有加鎖；
獲取元素個(gè)數(shù)元素個(gè)數(shù)的存儲(chǔ)也是采用分段的思想，獲取元素個(gè)數(shù)時(shí)需要把所有段加起來(lái)。
public int size() {
// 調(diào)用sumCount()計(jì)算元素個(gè)數(shù)
long n = sumCount();
return ((n < 0L) ? 0 :
(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
(int)n);
}
final long sumCount() {
// 計(jì)算CounterCell所有段及baseCount的數(shù)量之和
CounterCell[] as = counterCells; CounterCell a;
long sum = baseCount;
if (as != null) {
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
return sum;
}
元素的個(gè)數(shù)依據(jù)不同的線程存在在不同的段里；（見(jiàn)addCounter()分析）
計(jì)算CounterCell所有段及baseCount的數(shù)量之和；
獲取元素個(gè)數(shù)沒(méi)有加鎖；
總結(jié)（1）ConcurrentHashMap是HashMap的線程安全版本；
（2）ConcurrentHashMap采用（數(shù)組 + 鏈表 + 紅黑樹(shù)）的結(jié)構(gòu)存儲(chǔ)元素；
（3）ConcurrentHashMap相比于同樣線程安全的HashTable，效率要高很多；
（4）ConcurrentHashMap采用的鎖有 synchronized，CAS，自旋鎖，分段鎖，volatile等；
（5）ConcurrentHashMap中沒(méi)有threshold和loadFactor這兩個(gè)字段，而是采用sizeCtl來(lái)控制；
（6）sizeCtl = -1，表示正在進(jìn)行初始化；
（7）sizeCtl = 0，默認(rèn)值，表示后續(xù)在真正初始化的時(shí)候使用默認(rèn)容量；
（8）sizeCtl > 0，在初始化之前存儲(chǔ)的是傳入的容量，在初始化或擴(kuò)容后存儲(chǔ)的是下一次的擴(kuò)容門(mén)檻；
（9）sizeCtl = (resizeStamp << 16) + (1 + nThreads)，表示正在進(jìn)行擴(kuò)容，高位存儲(chǔ)擴(kuò)容郵戳，低位存儲(chǔ)擴(kuò)容線程數(shù)加1；
（10）更新操作時(shí)如果正在進(jìn)行擴(kuò)容，當(dāng)前線程協(xié)助擴(kuò)容；
（11）更新操作會(huì)采用synchronized鎖住當(dāng)前桶的第一個(gè)元素，這是分段鎖的思想；
（12）整個(gè)擴(kuò)容過(guò)程都是通過(guò)CAS控制sizeCtl這個(gè)字段來(lái)進(jìn)行的，這很關(guān)鍵；
（13）遷移完元素的桶會(huì)放置一個(gè)ForwardingNode節(jié)點(diǎn)，以標(biāo)識(shí)該桶遷移完畢；
（14）元素個(gè)數(shù)的存儲(chǔ)也是采用的分段思想，類(lèi)似于LongAdder的實(shí)現(xiàn)；
（15）元素個(gè)數(shù)的更新會(huì)把不同的線程hash到不同的段上，減少資源爭(zhēng)用；
（16）元素個(gè)數(shù)的更新如果還是出現(xiàn)多個(gè)線程同時(shí)更新一個(gè)段，則會(huì)擴(kuò)容段（CounterCell）；
（17）獲取元素個(gè)數(shù)是把所有的段（包括baseCount和CounterCell）相加起來(lái)得到的；
（18）查詢(xún)操作是不會(huì)加鎖的，所以ConcurrentHashMap不是強(qiáng)一致性的；
（19）ConcurrentHashMap中不能存儲(chǔ)key或value為null的元素；
學(xué)習(xí)重點(diǎn)ConcurrentHashMap中值得學(xué)習(xí)的技術(shù)
（1）CAS + 自旋，樂(lè)觀鎖的思想，減少線程上下文切換的時(shí)間；
（2）分段鎖的思想，減少同一把鎖爭(zhēng)用帶來(lái)的低效問(wèn)題；
（3）CounterCell，分段存儲(chǔ)元素個(gè)數(shù)，減少多線程同時(shí)更新一個(gè)字段帶來(lái)的低效；
（4）@sun.misc.Contended（CounterCell上的注解），避免偽共享；
（5）多線程協(xié)同進(jìn)行擴(kuò)容；
ConcurrentHashMap 并發(fā)下使用問(wèn)題看下面的使用例子：
