public class ConcurrentHashMapTest {
    public static void main(String[] args) {
        ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();
        map.put("test1", "1");
        map.put("test2", "2");
        map.put("test3", "3");
        map.remove("test1");
        System.out.println(map.get("test1"));
        System.out.println(map.get("test2"));
    }
}

public ConcurrentHashMap() {}

public ConcurrentHashMap(int initialCapacity) {
    // 假如哥們傳進(jìn)來入?yún)⑿∮?
    if (initialCapacity < 0)
        // 直接拋出異常，說明哥們?cè)诟阈?
        throw new IllegalArgumentException();
    // 用傳進(jìn)來的數(shù)值與 MAXIMUM_CAPACITY >>> 1 進(jìn)行對(duì)比
    // 若大于則使用MAXIMUM_CAPACITY
    // 小于則使用距離initialCapacity最近的2次冪
    int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
               MAXIMUM_CAPACITY :
               tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
    this.sizeCtl = cap;
}

// 根據(jù)傳進(jìn)的C的數(shù)值,找到其距離最近的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;
}

public V put(K key, V value) {
    // 在調(diào)用put方法時(shí)，會(huì)調(diào)用putVal，第三個(gè)參數(shù)默認(rèn)傳遞為false
    // 在調(diào)用putIfAbsent時(shí)，會(huì)調(diào)用putVal方法，第三個(gè)參數(shù)傳遞的為true
    // 如果傳遞為false，代表key一致時(shí)，直接覆蓋數(shù)據(jù)
    // 如果傳遞為true，代表key一致時(shí)，什么都不做，key不存在，正常添加（Redis，setnx）
    return putVal(key, value, false);
}

final V putVal(K key, V value, boolean onlyIfAbsent) {
    // 如果當(dāng)前的key或者value是空的話,直接拋出異常
    if (key == null || value == null){
        throw new NullPointerException();
    }
    // 獲取其下標(biāo)
    int hash = spread(key.hashCode());
    int binCount = 0;
}

// 作用：用高16位與低16位進(jìn)行^運(yùn)算,讓高位的數(shù)值可以進(jìn)行計(jì)算
// 為什么原來的高位沒有辦法計(jì)算呢？
// 我們后面的 (n - 1) & hash 的數(shù)據(jù),&數(shù)據(jù)如下：
// 00000000 00000000 00000000 01010101
// 0000000  00000000 00000000 00011111
// 我們這里看到,如果高16位不與低16位^運(yùn)算的話,那么基本我們的高位永遠(yuǎn)也參加不了計(jì)算
// 為什么需要&HASH_BITS:
// 保證最終的結(jié)果大于0,因?yàn)槿绻Y(jié)果小于0的話，代表不同的意義：
// static final int MOVED     = -1; // 代表當(dāng)前hash位置的數(shù)據(jù)正在擴(kuò)容！
// static final int TREEBIN   = -2; // 代表當(dāng)前hash位置下掛載的是一個(gè)紅黑樹
// static final int RESERVED  = -3; // 預(yù)留當(dāng)前索引位置……
static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS;
}

// tab指向table，標(biāo)準(zhǔn)的Doug Lea寫法
for (Node<K,V>[] tab = table;;) {
    Node<K,V> f; 
    int n, i, fh;
    // 如果當(dāng)前的數(shù)組為空或者他的數(shù)組長(zhǎng)度為0
    // 則進(jìn)行初始化
    if (tab == null || (n = tab.length) == 0){
        tab = initTable();
    }
}


// sizeCtl：是數(shù)組在初始化和擴(kuò)容操作時(shí)的一個(gè)控制變量
// -1：代表當(dāng)前數(shù)組正在初始化
// 小于-1：低16位代表當(dāng)前數(shù)組正在擴(kuò)容的線程個(gè)數(shù)（如果1個(gè)線程擴(kuò)容，值為-2，如果2個(gè)線程擴(kuò)容，值為-3）
// 0：代表數(shù)組還沒初始化
// 大于0：代表當(dāng)前數(shù)組的擴(kuò)容閾值，或者是當(dāng)前數(shù)組的初始化大小
private final Node<K,V>[] initTable() {
    // 經(jīng)典引用
    Node<K,V>[] tab; 
    int sc;
    // 當(dāng)前的初始化沒有完成時(shí),會(huì)一直進(jìn)行該while循環(huán)
    while ((tab = table) == null || tab.length == 0) {
        // 如果小于0,代表當(dāng)前數(shù)組正在擴(kuò)容或者初始化
        // 當(dāng)前線程等待一下
        if ((sc = sizeCtl) < 0)
            Thread.yield(); 
        // 嘗試將SIZECTL從SC更改為-1
        // CAS修改，線程安全，保證只有一個(gè)線程執(zhí)行數(shù)組初始化
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                // 更改成功,再次判斷一下(參考DCL)
                // 防止下面sizeCtl = sc剛賦值完,正好有線程走到這一步,不做限制的話就會(huì)重新初始化了
                if ((tab = table) == null || tab.length == 0) {
                    // 判斷當(dāng)前的sc是否大于0(sc=SIZECTL)
                    // 大于0：n = sc
                    // 小于等于0：n = DEFAULT_CAPACITY
                    // 一般我們只要不傳入入?yún)?這里基本走DEFAULT_CAPACITY的擴(kuò)容
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    // 擴(kuò)容即可
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    // table、tab賦值
                    table = tab = nt;
                    // 這里有點(diǎn)意思
                    // 將sc賦值成(n - 1/4n) = 0.75N
                    // 這里0.75是不是很熟悉，負(fù)載因子
                    sc = n - (n >>> 2);
                }
            } finally {
                // 將上面的擴(kuò)容閾值賦予sizeCtl
                sizeCtl = sc;
            }
            // 結(jié)束循環(huán)
            break;
        }
    }
    return tab;
}

// 如果當(dāng)前數(shù)組該下標(biāo)沒有數(shù)據(jù),直接插入即可
if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
    // CAS將當(dāng)前的hash、key、value組裝成一個(gè)Node,插入當(dāng)前數(shù)組i位置
    // 插入成功結(jié)束即可
    if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))){
        break;
    }      
}

// 基于我們上面說的(n - 1) & hash算出下標(biāo)
// 返回當(dāng)前數(shù)組下該下標(biāo)的數(shù)據(jù)
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
    return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}

static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v) {
    return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}

static class Node<K,V> implements Map.Entry<K,V> {
    // 當(dāng)前的hash值
    final int hash;
    // key
    final K key;
    // value
    volatile V val;
    // 下一個(gè)節(jié)點(diǎn)(用來連鏈表的)
    volatile Node<K,V> next;
}

// 判斷當(dāng)前位置數(shù)據(jù)是否正在擴(kuò)容……
if ((fh = f.hash) == MOVED)
    // 如果在擴(kuò)容,則當(dāng)前線程幫助其擴(kuò)容
    tab = helpTransfer(tab, f);

else {
    V oldVal = null;
    // 鎖當(dāng)前的數(shù)組下標(biāo)i的數(shù)組塊
    synchronized (f) {
        // 看一下當(dāng)前數(shù)組的i位置是不是等于f
        // 相當(dāng)于再次校驗(yàn)一次(DCL)
        if (tabAt(tab, i) == f) {
            // static final int MOVED     = -1; // 代表當(dāng)前hash位置的數(shù)據(jù)正在擴(kuò)容！
		   // static final int TREEBIN   = -2; // 代表當(dāng)前hash位置下掛載的是一個(gè)紅黑樹
		   // static final int RESERVED  = -3; // 預(yù)留當(dāng)前索引位置……
            // fh = f.hash
            // 判斷下當(dāng)前的fh是否大于0,也就是不是上面三種情況
            if (fh >= 0) {
                // 記錄當(dāng)前鏈表下面掛了幾個(gè)
                binCount = 1;
                // 獲取當(dāng)前的數(shù)組節(jié)點(diǎn),沒循環(huán)一次binCount加一
                for (Node<K,V> e = f;; ++binCount) {
                    K ek;
                    // 如果當(dāng)前數(shù)組下標(biāo)的hash和我們?nèi)雲(yún)⒌膆ash一樣,代表重復(fù)數(shù)據(jù)
                    if (e.hash == hash &&
                        // 如果當(dāng)前的key也等于原始的key
                        // 或者是根據(jù)equals判斷出來的相等(因?yàn)橛幸恍┛赡苤貙懥薳quals方法)
                        ((ek = e.key) == key ||
                         (ek != null && key.equals(ek)))) {
                        // 將當(dāng)前老的數(shù)據(jù)賦值給oldVal
                        oldVal = e.val;
                        // 這里的onlyIfAbsent我們之前也聊過
                        // 如果傳遞為false，代表key一致時(shí)，直接覆蓋數(shù)據(jù)
   					  // 如果傳遞為true，代表key一致時(shí)，什么都不做，key不存在，正常添加（Redis，setnx）
                        if (!onlyIfAbsent)
                            // 覆蓋數(shù)據(jù)
                            e.val = value;
                        break;
                    }
                    // 這里就不是相同的數(shù)據(jù)了,需要掛鏈表下面了
                    // 先獲取數(shù)組最上面的數(shù)據(jù)
                    Node<K,V> pred = e;
                    // 判斷下當(dāng)前的下一個(gè)數(shù)據(jù)是不是空指針
                    // 不是空指針的話,繼續(xù)指向下一個(gè)指針
                    if ((e = e.next) == null) {
                        // 直到最后的時(shí)候,創(chuàng)建一個(gè)節(jié)點(diǎn)掛上去
                        pred.next = new Node<K,V>(hash, key,value, null);
                        break;
                    }
                }
            }
}

 // 如果上面不成立的話,也就是當(dāng)前的數(shù)組下面是一個(gè)紅黑樹
 // 需要將當(dāng)前的數(shù)據(jù)放到紅黑樹里面
else if (f instanceof TreeBin) {
    Node<K,V> p;
    binCount = 2;
    // 將當(dāng)前數(shù)據(jù)放入到紅黑樹中
    if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) {
        // 記錄一下老數(shù)據(jù)
        oldVal = p.val;
        // 這里的onlyIfAbsent我們之前也聊過
        // 如果傳遞為false，代表key一致時(shí)，直接覆蓋數(shù)據(jù)
        // 如果傳遞為true，代表key一致時(shí)，什么都不做，key不存在，正常添加（Redis，setnx）
        if (!onlyIfAbsent)
            // 覆蓋數(shù)據(jù)
            p.val = value;
    }
}

// 如果當(dāng)前的鏈表上的數(shù)據(jù)不等于0
if (binCount != 0) {
    // 當(dāng)前列表下的數(shù)據(jù)長(zhǎng)度大于8
    // 這里需要注意,大于8的話并不是立即轉(zhuǎn)成紅黑樹,還需要判斷當(dāng)前數(shù)組的長(zhǎng)度
    if (binCount >= TREEIFY_THRESHOLD)
        treeifyBin(tab, i);
    if (oldVal != null)
        return oldVal;
    break;
}
static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;

private final void treeifyBin(Node<K,V>[] tab, int index) {
    Node<K,V> b; int n, sc;
    // 如果當(dāng)前的數(shù)組不為空
    if (tab != null) {
        // 如果當(dāng)前的數(shù)組長(zhǎng)度小于64,則沒必要轉(zhuǎn)成紅黑樹
        // 直接擴(kuò)容即可
        if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
            tryPresize(n << 1);
        // 后面的是轉(zhuǎn)成紅黑樹的代碼
        // 我們下一章在分析
        else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
            synchronized (b) {
                if (tabAt(tab, index) == b) {
                    TreeNode<K,V> hd = null, tl = null;
                    for (Node<K,V> e = b; e != null; e = e.next) {
                        TreeNode<K,V> p = new TreeNode<K,V>(e.hash, e.key, e.val, null, null);
                        if ((p.prev = tl) == null){
                            hd = p;
                        }
                        else{
                            tl.next = p;
                        }
                        tl = p;
                    }
                    setTabAt(tab, index, new TreeBin<K,V>(hd));
                }
            }
        }
    }
}