ConcurrentHashMap源码解析

发表于 | 分类于 | 评论数： | 阅读次数：
本文字数： 25k | 阅读时长 ≈ 23 分钟

如果想更详细了解ConcurrentHashMap 内部工作原来可以去看下我以前写过一篇HashMap源码解析了解下hash 算法原理、数组扩容、红黑树转换等等。

initTable

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        if ((sc = sizeCtl) < 0) //这时已经有其他线程获取到执行权，沉睡一会
            Thread.yield(); // lost initialization race; just spin
        else if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {
            try {
                if ((tab = table) == null || tab.length == 0) {
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; //初始化数组
                    table = tab = nt;
                    sc = n - (n >>> 2);
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

这个是初始化map数组，核心是sizeCtl 这个变量：一个使用volatile修饰共享变量，作用通过交换比较竞争获取初始化或者扩容数组执行权。当线程发现sizeCtl小于0的时候，线程就会让出执行权，当线程成功竞争设置-1 就相当于获取到执行权，所以就可以去初始化数组了。当为正数时，保存下一个要调整Map大小的元素计数值

说明下Unsafe 交换比较方法

1
2
3
4
5
6
7
8
9
/**
 * 通过对象属性的值，修改前、更新后一致，才是更新成功
 * @param o 需要被修改的属性的对象
 * @param l 对象Field的指针地址，可以理解成属性值引用
 * @param i 修改前的值
 * @param i1 修改后的值
 * @return
 */
public final native boolean compareAndSwapInt(java.lang.Object o, long l, int i, int i1)；

put方法解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
    public V put(K key, V value) {
    return putVal(key, value, false);
}


final V putVal(K key, V value, boolean onlyIfAbsent) {
   //ConcurrentHashMap 不允许key value为空，因为在并发情况下不能通过获取get(key) 判断key存不存在
    if (key == null || value == null) throw new NullPointerException(); 
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh; K fk; V fv;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { //通过计算hash得到数组下标，为空通过交换比较设置进去，这时不需要加锁的
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
                break;                   // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED)  //这种情况说明数组正在扩容，需要对链表和黑红树进行迁移
            tab = helpTransfer(tab, f);
        else if (onlyIfAbsent // check first node without acquiring lock
                 && fh == hash
                 && ((fk = f.key) == key || (fk != null && key.equals(fk)))
                 && (fv = f.val) != null)
            return fv;
        else {
            V oldVal = null;
            synchronized (f) {
                if (tabAt(tab, i) == f) { //头节点没有改变，说明获取锁过程，没有线程扩容
                    if (fh >= 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)))) {
                                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);
                                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;
                        }
                    }
                    else if (f instanceof ReservationNode)
                        throw new IllegalStateException("Recursive update");
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

简单说下put 业务逻辑：

  1. 先判断table数组是否为空，不加锁，调用initTable 进行初始化

  2. 计算key 哈希值，通过hash计算出数组中下标，如果下标刚好为空，通过交换比较设置进去。多个线程设置通过数组下标时，当设置失败时会不满足下标为空情况，进入获取头节点锁

  3. 此时节点有值，并且hash 值等于-1，则说明数组正在扩容，调用helpTransfer 方法多线程进行copy数组

  4. 只锁住链表或红黑树根节点，先判断根节点是否等于获取锁的对象，因为有可能获取到锁对象已经因为数组扩容进行偏移了 ，如果已经进行偏移还在根节点进行插入会导致hash计算错误，导致get 获取不到值。这个是安全检查很重要的。

  5. 为什么要判断fh >= 0 主要是因为ConcurrentHashMap Node hash 有特殊意义

    • int MOVED = -1; 正在进行数组扩容，准备迁移
    • int TREEBIN = -2 红黑树根节点
    • int RESERVED = -3; 临时保留节点

  6. 大于0就知道这是一个链表，从头开始遍历到最后插入，Java8 链表改成尾插入有一个好处就是遍历完链表后就知道链表长度了，binCount就是链表长度。每次遍历节点都会比较key相等，覆盖旧值，否则在链表最后插入。

  7. 红黑树逻辑插入和链表差不多，通过putTreeVal 遍历并且插入节点，只要找到相同key节点才会返回节点对象，如果是在红黑树下新增只会返回null。

  8. binCount是链表长度，如果长度大于链表长度阈值（默认8）转换成红黑树。因为上面遍历时遇到相同key值，都会将节点赋值给oldVal，如果不为空则是覆盖，不需要执行累加，直接返回就可以了。

  9. addCount只要就是对map size进行累加，因为在并发情况下不能直接加锁住size方法进行加一，这违反设定的粗细粒锁的设定。实际情况比较复制，数组扩容的逻辑也是在这个方法中实现的，下面具体分析下。

size() 方法

在分析map size之前，看讲下size方法如何获取长度，有利于addCount 讲解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int size() {
    long n = sumCount();
    return ((n < 0L) ? 0 :
            (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
            (int)n);
}
final long sumCount() {
    CounterCell[] cs = counterCells;
    long sum = baseCount;
    if (cs != null) {
        for (CounterCell c : cs)
            if (c != null)
                sum += c.value;
    }
    return sum;
}

size长度主要是通过baseCount + CounterCell数组累加起来的。baseCount 只要当一个线程在使用map时，才会使用baseCount来记录size大小，当出现多个线程线程同时对map操作时，就会放弃使用baseCount，而将每个线程操作数量 放入CounterCell数组中。可以理解CounterCell只是一个计算盒子，通过一些算法将不同线程操作数量放入到指定index位置，可以隔离线程对同个数竞争修改，有点类似hash 计算下标放入数组方式，这样可以减少冲突次数。

addCount分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
private final void addCount(long x, int check) {
    CounterCell[] cs; long b, s;
    if ((cs = counterCells) != null ||
        !U.compareAndSetLong(this, BASECOUNT, b = baseCount, s = b + x)) {
        CounterCell c; long v; int m;
        boolean uncontended = true;
        // 此时cs 没有初始化，或者 cs刚刚初始化，长度还是0，通过线程随机数获取下标刚好为空
        if (cs == null || (m = cs.length - 1) < 0 ||
            (c = cs[ThreadLocalRandom.getProbe() & m]) == null ||
            !(uncontended =
              U.compareAndSetLong(c, CELLVALUE, v = c.value, v + x))) {
            fullAddCount(x, uncontended);  //将累加值添加到数组中
            return;
        }
        if (check <= 1)
            return;
        s = sumCount();
    }
    if (check >= 0) { //于于0不会判断数组扩容情况
        Node<K,V>[] tab, nt; int n, sc;
        // 只有满足size长度等于或大于sizeCtl 扩容阈值长度，才会进行下面逻辑
        while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
               (n = tab.length) < MAXIMUM_CAPACITY) {
            int rs = resizeStamp(n) << RESIZE_STAMP_SHIFT;
            if (sc < 0) { //当前tab数组来扩容，通过竞争去抢夺扩容权
                if (sc == rs + MAX_RESIZERS || sc == rs + 1 ||
                    (nt = nextTable) == null || transferIndex <= 0)
                    break;
                if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1))
                    transfer(tab, nt);
            }
            else if (U.compareAndSetInt(this, SIZECTL, sc, rs + 2))
                transfer(tab, null);
            s = sumCount();
        }
    }
}

先从if判断开始，如果countCells 这个数组不空，第二个条件不用判断，进入countCells设置累加。第一个条件不成立就会执行 baseCount累加，累加成功条件不成立，不进入if逻辑。
countCells 初始化、x值添加到数组上，或者多线程对同一个数组下标累加的控制都需要fullAddCount去实现的。
上面说过sizeCtl 为正整数就是数组容量扩容阈值，while 下先判断map size 是否达到或者超过阈值，符合条件就会
进入循环了进行数组扩容。当sizeCtl > 0 时则是多个线程在对数组扩容，这时需要竞争获取执行权。
具体分析下扩容条件如何成立的，首先直到

resizeStamp(n) << RESIZE_STAMP_SHIFT;

这个方法是将数组n，低位补零左移16为，相当于讲数组长度保存到高16位中。每一个线程参与并发就会在sizeCtl 上+1 ，低16位这样就是用来保存参与数组扩容数量。

  • sc > 0

    • 这时还没有线程对tab数组进行扩容

  • sz < 0

    • 已经有线程在扩容，将sizeCtl+1并调用transfer()让当前线程参与扩容。

下面分析下while 里面的判断

  • sc == rs + MAX_RESIZERS 当前线程数已经达到最大上限了，再有新的线程进来扩容就没有意义了
  • sc == rs + 1 只要rs + 1成功会在调用transfer，但是现在rs值已经被其他线程修改了，累加已经失败了，没有必要在执行一次交换比较了。
  • (nt = nextTable) == null 此时扩容已经完成了，新的线程不必进入扩容方法了
  • transferIndex <= 0 transferIndex tab数组没有分配的迁移的数量，此时为0表示扩容线程已经达到最大数量了，不必再使用新的线程进入了

细讲下fullAddCount 方法
ThreadLocalRandom.getProbe()可以简单理解成每一个线程hash值，但是这个值不是固定的，在找不到数组slot是，可以重新计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
private final void fullAddCount(long x, boolean wasUncontended) {
     int h;
     if ((h = ThreadLocalRandom.getProbe()) == 0) {  //初始化
         ThreadLocalRandom.localInit();      // force initialization
         h = ThreadLocalRandom.getProbe();
         wasUncontended = true;
     }
     boolean collide = false;                
     for (;;) {
         CounterCell[] cs; CounterCell c; int n; long v;
         if ((cs = counterCells) != null && (n = cs.length) > 0) { 
             if ((c = cs[(n - 1) & h]) == null) {
                 if (cellsBusy == 0) {            // Try to attach new Cell
                     CounterCell r = new CounterCell(x); // Optimistic create
                     if (cellsBusy == 0 &&
                         U.compareAndSetInt(this, CELLSBUSY, 0, 1)) {  //竞争成功了可以对数组修改
                         boolean created = false;
                         try {               // Recheck under lock
                             CounterCell[] rs; int m, j;
                             if ((rs = counterCells) != null &&
                                 (m = rs.length) > 0 &&
                                 rs[j = (m - 1) & h] == null) {
                                 rs[j] = r;
                                 created = true;
                             }
                         } finally {
                             cellsBusy = 0;
                         }
                         if (created)
                             break;
                         continue;           // Slot is now non-empty
                     }
                 }
                 collide = false;
             }
             else if (!wasUncontended)       // 这时CAS已经失败了，继续自旋等待扩容
                 wasUncontended = true;      // Continue after rehash
             else if (U.compareAndSetLong(c, CELLVALUE, v = c.value, v + x))  //累加成功，退出自旋
                 break;
             //当数组长度超过CPU个数了，这时就不应该扩容了，而是继续自旋直到累加成功
             else if (counterCells != cs || n >= NCPU) 
                 collide = false;            // At max size or stale
             else if (!collide) //如果竞争继续失败了，不扩容的话会继续自旋
                 collide = true;
             else if (cellsBusy == 0 &&
                     //走到这里说明第一次竞争失败了，有冲突直接对数据扩容
                      U.compareAndSetInt(this, CELLSBUSY, 0, 1)) {
                 try {
                     if (counterCells == cs) // Expand table unless stale
                         counterCells = Arrays.copyOf(cs, n << 1);
                 } finally {
                     cellsBusy = 0;
                 }
                 collide = false;
                 continue;                   // Retry with expanded table
             }
            //重新生成probe ，因为此时是CAS插入失败。 更换其他的插槽试试
             h = ThreadLocalRandom.advanceProbe(h); 
         }
         else if (cellsBusy == 0 && counterCells == cs &&
                  U.compareAndSetInt(this, CELLSBUSY, 0, 1)) {//初始化数组
             boolean init = false;
             try {                           // Initialize table
                 if (counterCells == cs) {
                     CounterCell[] rs = new CounterCell[2];
                     rs[h & 1] = new CounterCell(x);
                     counterCells = rs;
                     init = true;
                 }
             } finally {
                 cellsBusy = 0;
             }
             if (init)
                 break;
         }
          // 这时候counterCells 数组没有初始化，有没有多个线程竞争，可以使用baseCount 进行累加
         else if (U.compareAndSetLong(this, BASECOUNT, v = baseCount, v + x))
             break;                          // Fall back on using base
     }
 }

cellsBusy 这个属性跟我们之前讲过sizeCtl 功能很相识的，都是来控制数组修改权限的。当cellsBusy =0时，counterCells数组可以被插入、扩容的 ，线程只要将cellsBusy设置成1就可以获取修改权限，改完后将cellsBusy变成0就可以了。
看过LongAdder源码的同学是不是觉得很熟悉啊，不能说很相识，只是说是一模一样，就连变量名都是复制过来的。其实这个我愿意讲这个细节的原因，涉及了LongAdder设计思想，value值分离成一个数组，当多线程访问时，通过hash算法映射到其中的一个数字进行计数
图来自 https://cloud.tencent.com/developer/article/1497528

transfer

接着看下map在多线程下如何进行扩容的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    int n = tab.length, stride;
    //这里是计算一个线程最大要迁移数组个数，相当于将数组分拆成这么多部分，每个线程最大可以处理
    if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
        stride = MIN_TRANSFER_STRIDE; // subdivide range
    if (nextTab == null) {            // initiating
        try {
            @SuppressWarnings("unchecked")
            Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
            nextTab = nt;
        } catch (Throwable ex) {      // try to cope with OOME
            sizeCtl = Integer.MAX_VALUE;
            return;
        }
        nextTable = nextTab;
        transferIndex = n;
    }
    int nextn = nextTab.length;
    ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
    boolean advance = true; //数组下标移动标记
    boolean finishing = false; //一个线程负责数组上元素是否已经全部迁徙完成
    //i 表示上一次分配剩余数量  bound数组现在剩下数量
    for (int i = 0, bound = 0;;) {
        Node<K,V> f; int fh;
        while (advance) {
            int nextIndex, nextBound;
           //这里只是为了i-1，或者就是所有数组元素已经全部迁移完成了
            if (--i >= bound || finishing) 
                advance = false;
            else if ((nextIndex = transferIndex) <= 0) {//数组已经全部被标注完了
                i = -1;
                advance = false;
            }
             //这里给进来线程分配迁移数量，分配成功就会跳出wile循环到下面去执行copy
            else if (U.compareAndSetInt
                     (this, TRANSFERINDEX, nextIndex,
                      nextBound = (nextIndex > stride ?
                                   nextIndex - stride : 0))) { 
                bound = nextBound;
                i = nextIndex - 1;
                advance = false;
            }
        }
        // 这三个条件任意一个成立都说明旧数据已经完全迁徙完成 了
        if (i < 0 || i >= n || i + n >= nextn) {
            int sc;
            if (finishing) {
                nextTable = null;
                table = nextTab;
                sizeCtl = (n << 1) - (n >>> 1);
                return;
            }
            if (U.compareAndSetInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
               //在addCount 时 sc +2  就会进入扩容，现在再减回去 如果不相等则表示现在还要线程在处理数据扩容，否则将finish改成true表示扩容已经结束 
                if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT) 
                    return;
                finishing = advance = true;
                i = n; // recheck before commit
            }
        }
       //下面进入数组元素迁移，每处理完一个将advance 改成true 重新进入while 
        else if ((f = tabAt(tab, i)) == null)
            advance = casTabAt(tab, i, null, fwd);
        //表明这个节点已经有其他线程在处理了
        else if ((fh = f.hash) == MOVED)
            advance = true; // already processed
        else {  //要迁移这个元素，直接锁住
            synchronized (f) {
                if (tabAt(tab, i) == f) { //双重检查
                    Node<K,V> ln, hn; //将链表分拆成两个 ln表示低位  hn高位
                    if (fh >= 0) { //上面说过，只要hash大于0就是链表
                        int runBit = fh & n;
                        Node<K,V> lastRun = f;
                        for (Node<K,V> p = f.next; p != null; p = p.next) { //这里先找出最后一个元素
                            int b = p.hash & n; 
                            if (b != runBit) {
                                runBit = b;
                                lastRun = p;
                            }
                        }
                        if (runBit == 0) {
                            ln = lastRun;
                            hn = null;
                        }
                        else {
                            hn = lastRun;
                            ln = null;
                        }
                        //将链表拆成两个，分别连起来了
                        for (Node<K,V> p = f; p != lastRun; p = p.next) { 
                            int ph = p.hash; K pk = p.key; V pv = p.val;
                            if ((ph & n) == 0)
                                ln = new Node<K,V>(ph, pk, pv, ln);
                            else
                                hn = new Node<K,V>(ph, pk, pv, hn);
                        }
                        setTabAt(nextTab, i, ln);
                        setTabAt(nextTab, i + n, hn);
                        // 标记旧数组，此下标不可以使用了
                        setTabAt(tab, i, fwd);
                        advance = true;
                    }
                    else if (f instanceof TreeBin) { //红黑树原来和上面差不多了
                        TreeBin<K,V> t = (TreeBin<K,V>)f;
                        TreeNode<K,V> lo = null, loTail = null;
                        TreeNode<K,V> hi = null, hiTail = null;
                        int lc = 0, hc = 0;
                        //遍历红黑树仍然使用链表下标去做，找到最后一个
                        for (Node<K,V> e = t.first; e != null; e = e.next) {
                            int h = e.hash;
                            TreeNode<K,V> p = new TreeNode<K,V>
                                (h, e.key, e.val, null, null);
                            if ((h & n) == 0) {
                                if ((p.prev = loTail) == null)
                                    lo = p;
                                else
                                    loTail.next = p;
                                loTail = p;
                                ++lc;
                            }
                            else {
                                if ((p.prev = hiTail) == null)
                                    hi = p;
                                else
                                    hiTail.next = p;
                                hiTail = p;
                                ++hc;
                            }
                        }
                       //新产生红黑树链表不满足阈值，转换成链表
                        ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
                            (hc != 0) ? new TreeBin<K,V>(lo) : t;
                        hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                            (lc != 0) ? new TreeBin<K,V>(hi) : t;
                        setTabAt(nextTab, i, ln);
                        setTabAt(nextTab, i + n, hn);
                        setTabAt(tab, i, fwd);
                        advance = true;
                    }
                    else if (f instanceof ReservationNode)
                        throw new IllegalStateException("Recursive update");
                }
            }
        }
    }
}

ForwardingNode 这个是一个特殊节点，在数组迁移过程中，已经被迁移过去节点会被标注成这个对象。防止在迁移数组过程中插入到旧数组中。内部封装一个find方法，可以去新数组中查找key value，下面get方法会用到的。
如何支持并发情况下，分配各个线程任务的。每一个线程进入都会在双层循环的while中分配到任务。刚进来时前面两个if、else if不会满足条件，但是会讲transferIndex重新赋值给nextIndex，此时nextIndex还是数组长度来的，当开始竞争修改transferIndex 时，设置成功的线程，分配到了数组下标 tab.leng -1 到 tab.length -1 - stride 这个范围的下标，从数组最后往前进行元素分配，并且将迁移完成index设置bound，i为数组copy的下标，当下标已经迁移到下个线程开始位置时，就会跳出while循环了，否则每次进入while就为了让下标 -1。竞争失败的线程会重新进入whle循环，继续去从transferIndex获取分配数量。当transferIndex不为空时，表示数组仍然有任务分配，继续去竞争获取。

if (i < 0 || i >= n || i + n >= nextn) { 当i < 0 成立时表示当前线程已经做完copy任务了， i >= n || i + n >= nextn都是跟下面i = n 相关，对当前数组进行边界检查。我们上面说过sizeCtl低16位表达当前线程扩容数量，让一个线程完成任务后，在sizeCtl -1 。sizeCtl -2 不相等主要和扩容时sizeCtl +2 调用transfer 向对应，不相等说明此时仍然有其他线程正在copy中，扩容没有完成的，已经完成线程自动退出扩容方法。让最后一个线程将完成收尾工作，将nextTab 变成tab。

get方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    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) { //数组元素就是当前key
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        else if (eh < 0) //这里是红黑树或者ForwardingNode  ，使用内部封装方法去查询
            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;
}

get方法没有使用锁，支持最大并发读取，而且不会出现安全问题。当eh < 0 ，这时是红黑树的话，调用红黑树遍历方法去操作节点。如果此时ForwardingNode，虽然这个节点的数据已经被迁移到新数组去了，但是内部封装find方法，去新的数组中查找。无论是哪种节点都可以找到对应key value。

删除方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
public V remove(Object key) {
    return replaceNode(key, null, null);
}

final V replaceNode(Object key, V value, Object cv) {
    int hash = spread(key.hashCode()); //计算hash值
    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)  //找不到对应key 节点，退出循环
            break;
        else if ((fh = f.hash) == MOVED)  //参考上面put 此时数组在扩容，线程帮忙进入扩容
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            boolean validated = false;
            synchronized (f) {  //锁住数组下标节点
                if (tabAt(tab, i) == f) {
                    if (fh >= 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;
                                    else
                                        //前面节点为空，头节点就是要被删除的
                                        setTabAt(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));
                            }
                        }
                    }
                    else if (f instanceof ReservationNode)
                        throw new IllegalStateException("Recursive update");
                }
            }
            if (validated) {
                if (oldVal != null) {  //旧值不存在，才会真正去删除节点数据
                    if (value == null)
                        addCount(-1L, -1);  //size -1
                    return oldVal;
                }
                break;
            }
        }
    }
    return null;
}

资料引用

https://xilidou.com/2018/11/27/LongAdder/

https://cloud.tencent.com/developer/article/1497528

https://blog.csdn.net/zzu_seu/article/details/106698150