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