ConcurrentHashMap詳解什么時候CAS什么時候synchronized

jdk:1.7 segment數組+hashEntry數組+鏈表實現

jdk版本：1.8：hashEntry+數組+紅黑樹實現

1、基本參數

//**1、最大容量**  hashmap的最大容量也是這個，菜鳥一面被問到了
private static final int MAXIMUM_CAPACITY = 1 << 30;//數組默認為16
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;//float浮點數，LOAD_FACTOR為final 不可更改
private static final float LOAD_FACTOR = 0.75f;

2、初始化1

也就是說不是你輸入什么就是什么容量，內部還有一個算法優化用戶的輸入。（防止用戶輸入參數太差）  
//邏輯：如果init>max的一半，則返回max，否則返回tableSizeFor(init + (initialCapacity >>> 1) + 1)); 
public ConcurrentHashMap(int init) {if (init < 0)throw new IllegalArgumentException();int cap = ((init >= (MAXIMUM_CAPACITY >>> 1)) ?MAXIMUM_CAPACITY :tableSizeFor(init + (init >>> 1) + 1));this.sizeCtl = cap;    //`sizeCtl` 表示容量
}//c=2返回2，c=3返回4，c=9返回16
//tableSizeFor 方法通過一系列位操作，將輸入值 c 轉換為大于或等于 c 的最小 2 的冪次方。這是為了確保哈希表的數組大小總是 2 的冪次方，從而優化哈希分布和查找性能。private static final int tableSizeFor(int c) {int n = c - 1;n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

初始化2

 public ConcurrentHashMap(int initialCapacity,float loadFactor, int concurrencyLevel) {if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)throw new IllegalArgumentException();if (initialCapacity < concurrencyLevel)   // Use at least as many binsinitialCapacity = concurrencyLevel;   // as estimated threads//非常神奇啊，傳入的loadFactor不會改變裝填因子，但是會改變傳入的容量參數，影響最終容量long size = (long)(1.0 + (long)initialCapacity / loadFactor);int cap = (size >= (long)MAXIMUM_CAPACITY) ?MAXIMUM_CAPACITY : tableSizeFor((int)size);this.sizeCtl = cap;}

3、sizeCtl 不太理解

sizeCtl 是 ConcurrentHashMap 中一個非常重要且復雜的控制字段，其作用有很多個。

addCount()里面判斷是否要擴容是和sizeCtl比較，而不是和裝填因子比較。為什么使用 sizeCtl 而不是直接使用負載因子？

簡化計算：
- 通過將負載因子的計算隱式地包含在 sizeCtl 中，可以避免每次插入或刪除元素時重新計算負載因子，從而減少了計算開銷。
并發控制：
- 使用 sizeCtl 可以有效地協調多個線程同時進行擴容操作。負值表示正在擴容，并且包含擴容的狀態信息。這樣，可以避免多個線程重復觸發擴容。
性能優化：
- 在高并發環境下，頻繁訪問和修改共享變量（如負載因子）會帶來性能瓶頸。通過使用 sizeCtl，可以減少這種共享變量的訪問次數，從而提高性能。

// Unsafe mechanicsprivate static final long SIZECTL;
//初始化map時候，this.sizectl = cap; //cap為容量//比如public ConcurrentHashMap(Map<? extends K, ? extends V> m) {this.sizeCtl = DEFAULT_CAPACITY;putAll(m);}在擴容期間：當擴容開始時，sizeCtl 被設置為一個負值，表示當前參與擴容的線程數量。這樣其他線程可以知道表正在擴容并可以協同進行擴容操作。

4、put 重點

public V put(K key, V value) {return putVal(key, value, false);}/** Implementation for put and putIfAbsent */final V putVal(K key, V value, boolean onlyIfAbsent) {//1、數據檢查if (key == null || value == null) throw new NullPointerException();//2、求key哈希int hash = spread(key.hashCode());int binCount = 0;  //記錄遍歷的節點數，可以用于判斷是否要鏈表轉化為紅黑樹for (Node<K,V>[] tab = table;;) {  //死循環Node<K,V> f; int n, i, fh;if (tab == null || (n = tab.length) == 0)  //檢查 table 是否初始化tab = initTable();//使用哈希值計算索引 i 并檢查該位置是否為空。如果為空，使用 CAS 操作插入新節點，并跳出循環。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}else if ((fh = f.hash) == MOVED) // MOVEDd標志用于判斷是否已經節點遷移//當一個桶（bin）中的所有節點都被遷移到新的數組中后，原來的位置上會放置一個特殊的轉發節點，表示這個桶已經處理完畢。此時，轉發節點的 hash 字段會被設置為 MOVED（即 -1）。tab = helpTransfer(tab, f);//協助遷移else {   //如果碰撞了  需要使用synchronized，放棄cas,f是table那個碰撞節點V oldVal = null;synchronized (f) {if (tabAt(tab, i) == f) { // 經典的雙重檢查，防止當前線程獲取table鎖之前，tabAt(tab, i)被其它線程改變了if (fh >= 0) {// 哈希值>=0代表是鏈表，<0代表是紅黑樹binCount = 1;for (Node<K,V> e = f;; ++binCount) {K ek;if (e.hash == hash &&((ek = e.key) == key ||(ek != null && key.equals(ek)))) {  // 三比較，hashcode==hashcode，key==key,key.equals(key)oldVal = e.val;if (!onlyIfAbsent)e.val = value;break;}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;  //binCount 被初始化為 2，因為紅黑樹中的節點數計算方式不同于鏈表。 具體原因我不知道if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,value)) != null) {oldVal = p.val;if (!onlyIfAbsent)p.val = value;}}}}if (binCount != 0) {   // 判斷是否要擴容 TREEIFY_THRESHOLD=8if (binCount >= TREEIFY_THRESHOLD)treeifyBin(tab, i);if (oldVal != null)return oldVal;break;}}}addCount(1L, binCount);  //計數 里面通過cas維護元素個數。return null;}

總結：

判斷key value是否合法判null
求key哈希
判斷table是否初始化，如果沒有就初始化
找到key哈希在table中的位置，判斷是否為null
1. 如果是Null則cas直接添加節點
2. 如果碰撞了需要使用synchronized（f）{}，放棄cas,f是table那個碰撞節點
  1. 如果f.hash>=0，則說明是鏈表，遍歷查找，當(hashhash && keykey && key.equals(key))的時候返回元素。下一個節點為null還沒有找到，則插入節點
  2. 如果f.hash<0, 則說明是紅黑樹，遍歷查找。找不到就插入。
3. 判斷是否要轉化為紅黑樹
調用addCount（）計算map總的元素個數，內部通過cas來實現。
1. 這里面會檢查table要不要擴容

**5、remove(Object key) **和put差不多

 final V replaceNode(Object key, V value, Object cv) {int hash = spread(key.hashCode());for (Node<K,V>[] tab = table;;) {Node<K,V> f; int n, i, fh;if (tab == null || (n = tab.length) == 0 ||(f = tabAt(tab, i = (n - 1) & hash)) == 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) {  // hash>=0 鏈表validated = true;for (Node<K,V> e = f, pred = null;;) {K ek;if (e.hash == hash &&((ek = e.key) == key ||(ek != null && key.equals(ek)))) {V ev = e.val;if (cv == null || cv == ev ||(ev != null && cv.equals(ev))) {oldVal = ev;if (value != null)e.val = value;else if (pred != null)pred.next = e.next;elsesetTabAt(tab, i, e.next);}break;}pred = e;if ((e = e.next) == null //找不到break;}}else if (f instanceof TreeBin) {validated = true;TreeBin<K,V> t = (TreeBin<K,V>)f;TreeNode<K,V> r, p;if ((r = t.root) != null &&(p = r.findTreeNode(hash, key, null)) != null) {V pv = p.val;if (cv == null || cv == pv ||(pv != null && cv.equals(pv))) {oldVal = pv;if (value != null)p.val = value;else if (t.removeTreeNode(p))setTabAt(tab, i, untreeify(t.first));}}}}}if (validated) {     // 計數if (oldVal != null) {if (value == null)addCount(-1L, -1);return oldVal;}break;}}}return null;}

6、get(Object key)

public V get(Object key) {// 定義一些局部變量Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;// 計算鍵的哈希值，并進行哈希值擴散以減少碰撞int h = spread(key.hashCode());// 如果哈希表不為空并且哈希表長度大于0if ((tab = table) != null && (n = tab.length) > 0 &&// 計算哈希表索引，取出對應位置的節點(e = tabAt(tab, (n - 1) & h)) != null) {// 如果找到的節點的哈希值等于目標哈希值if ((eh = e.hash) == h) {// 并且鍵也相等（引用相等或 equals 相等），則返回該節點的值if ((ek = e.key) == key || (ek != null && key.equals(ek)))return e.val;}// 如果節點的哈希值小于0，表示該節點是一個特殊節點（如紅黑樹節點或轉移節點）else if (eh < 0)// 調用 find 方法在該節點中查找目標鍵對應的值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;}}// 如果沒有找到，返回 nullreturn null;
}