探究并發包中ConcurrentHashMap中的put方法底層實作原理

put方法

public V put(K key, V value) {
		//回傳putVal
        return putVal(key, value, false);
    }

	//進入putVal
    final V putVal(K key, V value, boolean onlyIfAbsent) {
        //如果key或者value 為空，拋出空指標例外
		if (key == null || value == null) throw new NullPointerException();
		//通過spread計算key的hash，重新計算hash值 計算程序 高位不變 低位異或 符號位改為0
		//spread跟HashMap的hash演算法類似，只是把位數控制在int最大整數之內
        int hash = spread(key.hashCode());
		//用于統計節點個數
        int binCount = 0;
		//開始死回圈 定義一個節點陣列tab
        for (Node<K,V>[] tab = table;;) {
			//定義頭節點f的 容器長度n 碰撞位置i 頭節點的hash值fh
            Node<K,V> f; int n, i, fh;
			//在tab為空 或 長度為空時進入initTable()
            if (tab == null || (n = tab.length) == 0)
				//用于初始化節點陣列
                tab = initTable();
				//初始化結束 進入下次回圈
				
			//這個程序確定了頭節點的散列hash值位置 
			//tabAt的作用是尋找tab在記憶體中i位置的資料
			//i = (n - 1) & hash的意思是對hash % n ，采用二進制位操作相對于%能夠提高運算效率
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
				//如果此時頭節點為null
				
				//casTabAt 基于CAS嘗試更新 tab 中下標為 i 的結點的值為 v
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))//此時添值沒加鎖
					//如果失敗則說明期間有兩個以上的執行緒同時操作，需要進入一輪新的回圈
					//如果成功則本次 put 操作完成 跳出回圈
                    break;                   
            }
			//如果 Map 正在執行擴容操作（MOVED 哈希值表示正在擴容）
            else if ((fh = f.hash) == MOVED)
				//helpTransfer用于幫助擴容
                tab = helpTransfer(tab, f);
			//獲取到 hash 值對應下標的頭結點，且結點不為 null
            else {
				//宣告一個臨時變數
                V oldVal = null;
				//頭節點加鎖
                synchronized (f) {
					//再次判斷頭節點是否為f
                    if (tabAt(tab, i) == f) {
						//頭結點f的哈希值fh大于等于0，說明是鏈表，如果是樹的話應該是 -2
                        if (fh >= 0) {
							//必然最少一個值，因為f是一個值
                            binCount = 1;
							//開始回圈 創建節點e 每次binCount+1 ek為e的Key
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
								//判斷e的hash值是否等于之前的hash值
                                if (e.hash == hash &&
									//判斷ek是否為空，是否重復
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
									//如果是已經存在的 key，則就把已有的值替換為新的值
                                    oldVal = e.val;
									//如果不重復則不進入這個if
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
								//如果是不存在的 key，則直接在鏈表尾部插入一個新的結點
                                Node<K,V> pred = e;
								//e向后移動 并判斷e的next是不是為空
                                if ((e = e.next) == null) {
									//如果是空則創建新節點并放在pred的next
                                    pred.next = new Node<K,V>(hash, key,
                                                              value, null);
									//進入下一輪for回圈
                                    break;
                                }
                            }
                        }
						//如果已經樹化（紅黑樹）
                        else if (f instanceof TreeBin) {
                            Node<K,V> p;
                            binCount = 2;
							//呼叫紅黑樹的方法獲取到修改的結點，并插入或更新結點（如果允許）
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                if (binCount != 0) {
					//如果binCount大于等于8
                    if (binCount >= TREEIFY_THRESHOLD)
						//對鏈表執行轉換操作
							//如果 table 長度小于 64，則執行擴容
							//如果 table 長度大于等于 64，則轉換成紅黑樹
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
		//size+1
        addCount(1L, binCount);
        return null;
    }

initTable方法

初始化 table 的程序

    private final Node<K,V>[] initTable() {
		//宣告節點陣列 tab 臨時變數sc
        Node<K,V>[] tab; int sc;
		//如果此時tab為空 或 陣列長度為0 進入while回圈 
        while ((tab = table) == null || tab.length == 0) {
			//sizeCtl默認為0，用來控制table的初始化和擴容操作
            if ((sc = sizeCtl) < 0)
				//搶占執行緒失敗 yiede()讓出當前執行緒的執行權
                Thread.yield(); 
			//如果sc大于等于0 （U是一個非執行緒安全的工具類）
			//執行 CAS 操作，期望將sizeCtl替換為-1，sizeCtl為-1表示正在初始化
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                try {
					//對 table 進行初始化，再次判斷此時tab為空 或 陣列長度為0 
					//因為無法保證在上面的時間中有其他執行緒往table里放值
                    if ((tab = table) == null || tab.length == 0) {
						//sc大于0則 把sc給n 否則初始化長度為默認容量大小16
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                        @SuppressWarnings("unchecked")
						//創建節點陣列nt
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                        table = tab = nt;
						//指定下次擴容的長度，相當于 0.75 × n 
                        sc = n - (n >>> 2);
                    }
                } finally {
					//最終執行sc的值給sizeCtl
                    sizeCtl = sc;
                }
                break;
            }
        }
		//回傳tab 此時tab容量為16
        return tab;
    }

參考資料：
http://www.zhenchao.org/2019/01/31/java/cas-based-concurrent-hashmap/