1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V val;
        volatile Node<K,V> next;

        Node(int hash, K key, V val, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.val = val;
            this.next = next;
        }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

    Node<K,V> find(int h, Object k) {
              Node<K,V> e = this;
              if (k != null) {
                  do {
                      K ek;
                      if (e.hash == h &&
                          ((ek = e.key) == k || (ek != null && k.equals(ek))))
                          return e;
                  } while ((e = e.next) != null);
              }
              return null;
          }
      }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

    static final class TreeNode<K,V> extends Node<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion  需要在删除后取消链接。
        boolean red;

        TreeNode(int hash, K key, V val, Node<K,V> next,
                 TreeNode<K,V> parent) {
            super(hash, key, val, next);
            this.parent = parent;
        }

 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

        final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
              if (k != null) {
                  TreeNode<K,V> p = this;
                  do  {
                      int ph, dir; K pk; TreeNode<K,V> q;
                      TreeNode<K,V> pl = p.left, pr = p.right;
                      if ((ph = p.hash) > h)
                          p = pl;
                      else if (ph < h)
                          p = pr;
                      else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
                          return p;
                      else if (pl == null)
                          p = pr;
                      else if (pr == null)
                          p = pl;
                      else if ((kc != null ||(kc = comparableClassFor(k)) != null) && //判断是否实现Comparable接口
                               (dir = compareComparables(kc, k, pk)) != 0)
                          p = (dir < 0) ? pl : pr;
                      else if ((q = pr.findTreeNode(h, k, kc)) != null)
                          return q;
                      else
                          p = pl; //赋值左节点查找
                  } while (p != null);
              }
              return null;
          }
      } 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

  static final class TreeBin<K,V> extends Node<K,V> {
      TreeNode<K,V> root;
      volatile TreeNode<K,V> first;
      volatile Thread waiter;  
      //Unsafe更新节点
      volatile int lockState;   //锁的状态
      // values for lockState  锁状态值
      static final int WRITER = 1; // set while holding write lock    在保持写锁的同时设置
      static final int WAITER = 2; // set when waiting for write lock  在等待写锁时设置。
      static final int READER = 4; // increment value for setting read lock  设置读锁的增量值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

  static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                              TreeNode<K,V> p) {
            TreeNode<K,V> r, pp, rl;
            if (p != null && (r = p.right) != null) { //p的右节点，肯定不能为空，为空旋转啥；把p的右节点保存r临时值
                if ((rl = p.right = r.left) != null) // r的左节点赋值给p的右节点 现在p的右节点根r断开关系
                    rl.parent = p;                   // r的左节点前提不能为空，p赋值给r的左节点父节点，现在r的左节点断开关系
                if ((pp = r.parent = p.parent) == null) //p的父节点赋值给[r的父节点] 现在p的父节点根p断开关系
                    (root = r).red = false;             //p是根节点，r为根节点，以及设置为黑节点，红黑树的特性
                else if (pp.left == p)                // r的父节点的左节点等于p
                    pp.left = r;                      //  是：r赋值给[p的父节点的左节] 
                else                                  //  否：r赋值给[p的父节点的右节] 
                    pp.right = r;
                r.left = p;                           // p节点赋值[r的左节点]
                p.parent = r;                         // r赋值给[p节点的父节点]
            }
            return root;
        }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

        static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                               TreeNode<K,V> p) {
            TreeNode<K,V> l, pp, lr;
            if (p != null && (l = p.left) != null) {    //p的左节点，肯定不能为空，为空旋转啥；把p的左节点保存l临时值
                if ((lr = p.left = l.right) != null)    //l的右节点赋值给p的左节点,现在p的左节点根l断开关系
                    lr.parent = p;                      // l的右节不为空前提，把p赋值给l的右节点的父节点，现在l根l的右节点断开关系
                if ((pp = l.parent = p.parent) == null) //p的父节点赋值给l的父节点,现在p的父节点根p断开关系
                    (root = l).red = false;             //p为根节点，l为根节点，l设置为黑节点
                else if (pp.right == p)                 // l的父节点的右节点等于p
                    pp.right = l;                       // 是 l赋值给【l的父节点右节点】
                else                                    // 否 l赋值给【l的父节点左节点】 
                    pp.left = l;
                l.right = p;                            //p赋值给l的右节点
                p.parent = l;                           //l节点赋值给p的父节点
            }
            return root;
        }

 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

      static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                  TreeNode<K,V> x) {
          x.red = true;
          for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
              if ((xp = x.parent) == null) {          //x的父节点为空，添加第一个元素。
                  x.red = false;
                  return x;
              }
              else if (!xp.red || (xpp = xp.parent) == null)    //x的父节点为黑，没有破坏红黑树特性。或者x的祖父节点为空
                  return root;
              if (xp == (xppl = xpp.left)) {                   //x的父节点是祖父的左节点
                  if ((xppr = xpp.right) != null && xppr.red) { //          场景1:x的父节点为红色，且x的叔叔节点为红色；
                      xppr.red = false;                         //               x的叔叔节点设置黑色
                      xp.red = false;                           //               x的父节点设置黑色
                      xpp.red = true;                           //               x的祖父节点设置红色
                      x = xpp;                                  //               把祖父设置当前节点
                  }
                  else {
                      if (x == xp.right) {                                //场景2：x的父节点为红色，x的叔叔节点为黑色，且x节点是父节点右孩子；
                          root = rotateLeft(root, x = xp);                //      把父节点设置当前节点，x进行左旋转
                          xpp = (xp = x.parent) == null ? null : xp.parent;//     重新设置父节点，重新设置祖父节点
                      }
                      if (xp != null) {                                    //场景3：x的父节点为红色，x的叔叔节点为黑色，且x节点是父节点左孩子
                          xp.red = false;                                  //      父节点设置黑色
                          if (xpp != null) {                               //      祖父节点不为空情况：
                              xpp.red = true;                              //            祖父节点设置红色
                              root = rotateRight(root, xpp);               //            祖父节点进行右旋转
                          }
                      }
                  }
              }
              else {                       //树对称，操作也是对称的！
                  if (xppl != null && xppl.red) {
                      xppl.red = false;
                      xp.red = false;
                      xpp.red = true;
                      x = xpp;
                  }
                  else {
                      if (x == xp.left) {                               //判断x节点是父节点左孩子；
                          root = rotateRight(root, x = xp);             //进行右旋转
                          xpp = (xp = x.parent) == null ? null : xp.parent;
                      }
                      if (xp != null) {
                          xp.red = false;
                          if (xpp != null) {
                              xpp.red = true;
                              root = rotateLeft(root, xpp);             //进行左旋转
                          }
                      }
                  }
              }
          }
      }

 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

  static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
                                                   TreeNode<K,V> x) {
            for (TreeNode<K,V> xp, xpl, xpr;;)  {
                if (x == null || x == root)          
                    return root;
                else if ((xp = x.parent) == null) {
                    x.red = false;
                    return x;
                }
                else if (x.red) {                               //x节点为红色，没有破坏红黑树特性
                    x.red = false;
                    return root;
                }
                else if ((xpl = xp.left) == x) {                  //x是父节点左孩子
                    if ((xpr = xp.right) != null && xpr.red) {            //场景1:x的兄弟节点为红色，
                        xpr.red = false;                                  //     x的兄弟节点设置黑色
                        xp.red = true;                                    //     x的父节点设置红色  
                        root = rotateLeft(root, xp);                      //     x的父节点进行左旋转
                        xpr = (xp = x.parent) == null ? null : xp.right;  //     重新设置父节点和兄弟节点
                    }
                    if (xpr == null)                                      //x的兄弟节点为空，把父节点设置当前节点
                        x = xp;
                    else {
                        TreeNode<K,V> sl = xpr.left, sr = xpr.right;
                        if ((sr == null || !sr.red) &&
                            (sl == null || !sl.red)) {                   //场景2: x的兄弟节点为黑，且x的兄弟节点的两个孩子都是黑色
                            xpr.red = true;                              //      x的兄弟节点设置为红色
                            x = xp;                                      //      把父节点设置为当前节点
                        }
                        else {
                            if (sr == null || !sr.red) {                //场景3: x的兄弟节点为黑，且x的兄弟节点的右孩子都是黑色，左孩子都是红色
                                if (sl != null)                         //      x的兄弟节点的左孩子不为空，设置为黑色
                                    sl.red = false;
                                xpr.red = true;                         //      x的兄弟节点设置为红色
                                root = rotateRight(root, xpr);          //      x的兄弟节点进行右旋转
                                xpr = (xp = x.parent) == null ?         //      重新设置父节点和兄弟节点
                                    null : xp.right;
                            }
                            if (xpr != null) {                          //场景3: x的兄弟节点为黑，且x的兄弟节点的右孩子都是红色，左孩子任意颜色
                                xpr.red = (xp == null) ? false : xp.red;//      将x父节点颜色 赋值给 x的兄弟节点。         
                                if ((sr = xpr.right) != null)           //      x的兄弟节点的右孩子不为空，设置为黑色
                                    sr.red = false;
                            }
                            if (xp != null) {        
                                xp.red = false;                        //       x的父节点设置为黑色
                                root = rotateLeft(root, xp);           //       x的父节点进行左旋转
                            }
                            x = root;                                 //        把根节点设置为当前节点
                        }
                    }
                }
                else { // symmetric  对称
                    if (xpl != null && xpl.red) {
                        xpl.red = false;
                        xp.red = true;
                        root = rotateRight(root, xp);                //x的父节点进行左旋转
                        xpl = (xp = x.parent) == null ? null : xp.left;
                    }
                    if (xpl == null)
                        x = xp;
                    else {
                        TreeNode<K,V> sl = xpl.left, sr = xpl.right;
                        if ((sl == null || !sl.red) &&
                            (sr == null || !sr.red)) {
                            xpl.red = true;
                            x = xp;
                        }
                        else {
                            if (sl == null || !sl.red) {       //判断x的兄弟节点的左孩子都是黑色
                                if (sr != null)
                                    sr.red = false;
                                xpl.red = true;
                                root = rotateLeft(root, xpl);   //左旋转
                                xpl = (xp = x.parent) == null ?
                                    null : xp.left;
                            }
                            if (xpl != null) {
                                xpl.red = (xp == null) ? false : xp.red;
                                if ((sl = xpl.left) != null)
                                    sl.red = false;
                            }
                            if (xp != null) {
                                xp.red = false;
                                root = rotateRight(root, xp);    //右旋转
                            }
                            x = root;
                        }
                    }
                }
            }
        }

 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

        TreeBin(TreeNode<K,V> b) {
            super(TREEBIN, null, null, null);
            this.first = b;
            TreeNode<K,V> r = null;
            for (TreeNode<K,V> x = b, next; x != null; x = next) {
                next = (TreeNode<K,V>)x.next;
                x.left = x.right = null;
                if (r == null) {  //赋值根节点
                    x.parent = null;
                    x.red = false;
                    r = x;
                }
                else {
                    K k = x.key;
                    int h = x.hash;
                    Class<?> kc = null;
                    for (TreeNode<K,V> p = r;;) { //二分查找，查找到插入位置
                        int dir, ph;
                        K pk = p.key;
                        if ((ph = p.hash) > h)
                            dir = -1;
                        else if (ph < h)
                            dir = 1;
                        else if ((kc == null &&
                                  (kc = comparableClassFor(k)) == null) ||
                                 (dir = compareComparables(kc, k, pk)) == 0) //是否实现Comparable
                            dir = tieBreakOrder(k, pk);
                            TreeNode<K,V> xp = p;
                        if ((p = (dir <= 0) ? p.left : p.right) == null) {
                            x.parent = xp;
                            if (dir <= 0)
                                xp.left = x;
                            else
                                xp.right = x;
                            r = balanceInsertion(r, x); //红黑树插入
                            break;
                        }
                    }
                }
            }
            this.root = r;
            assert checkInvariants(root);
        }

 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

        final TreeNode<K,V> putTreeVal(int h, K k, V v) {
            Class<?> kc = null;
            boolean searched = false;
            for (TreeNode<K,V> p = root;;) {
                int dir, ph; K pk;
                if (p == null) {
                    first = root = new TreeNode<K,V>(h, k, v, null, null);
                    break;
                }
                else if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
                    return p;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0) {
                    if (!searched) {
                        TreeNode<K,V> q, ch;
                        searched = true;
                        if (((ch = p.left) != null &&
                             (q = ch.findTreeNode(h, k, kc)) != null) ||
                            ((ch = p.right) != null &&
                             (q = ch.findTreeNode(h, k, kc)) != null))
                            return q;
                    }
                    //根Class名称比较，在System.identityHashCode比较，总之比较出大小
                    dir = tieBreakOrder(k, pk);
                }

                TreeNode<K,V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    TreeNode<K,V> x, f = first;
                    first = x = new TreeNode<K,V>(h, k, v, f, xp);
                    if (f != null)
                        f.prev = x;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    if (!xp.red)
                        x.red = true;
                    else {
                        lockRoot();//弄一个锁，为查询了
                        try {
                            root = balanceInsertion(root, x);
                        } finally {
                            unlockRoot();
                        }
                    }
                    break;
                }
            }
            ...
            return null;
        }
        

 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

        final Node<K,V> find(int h, Object k) {
            if (k != null) {
                for (Node<K,V> e = first; e != null; ) {
                    int s; K ek;
                    if (((s = lockState) & (WAITER|WRITER)) != 0) {  
                        if (e.hash == h &&
                            ((ek = e.key) == k || (ek != null && k.equals(ek))))
                            return e;
                        e = e.next;
                    }
                    else if (U.compareAndSwapInt(this, LOCKSTATE, s,
                                                 s + READER)) {
                        TreeNode<K,V> r, p;
                        try {
                            p = ((r = root) == null ? null :
                                 r.findTreeNode(h, k, null));
                        } finally {
                            Thread w;
                            if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
                                (READER|WAITER) && (w = waiter) != null)
                                LockSupport.unpark(w);
                        }
                        return p;
                    }
                }
            }
            return null;
        }

 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

           final boolean removeTreeNode(TreeNode<K,V> p) {
                  TreeNode<K,V> next = (TreeNode<K,V>)p.next;
                  TreeNode<K,V> pred = p.prev;  // unlink traversal pointers
                  TreeNode<K,V> r, rl;
                  if (pred == null)
                      first = next;
                  else
                      pred.next = next;
                  if (next != null)
                      next.prev = pred;
                  if (first == null) {
                      root = null;
                      return true;
                  }
                  if ((r = root) == null || r.right == null || // too small
                      (rl = r.left) == null || rl.left == null)
                      return true;
                  lockRoot();
                  try {
                      TreeNode<K,V> replacement;
                      TreeNode<K,V> pl = p.left;
                      TreeNode<K,V> pr = p.right;
                      if (pl != null && pr != null) {
                          TreeNode<K,V> s = pr, sl;
                          while ((sl = s.left) != null) // find successor
                              s = sl;
                          boolean c = s.red; s.red = p.red; p.red = c; // swap colors
                          TreeNode<K,V> sr = s.right;
                          TreeNode<K,V> pp = p.parent;
                          if (s == pr) { // p was s's direct parent
                              p.parent = s;
                              s.right = p;
                          }
                          else {
                              TreeNode<K,V> sp = s.parent;
                              if ((p.parent = sp) != null) {
                                  if (s == sp.left)
                                      sp.left = p;
                                  else
                                      sp.right = p;
                              }
                              if ((s.right = pr) != null)
                                  pr.parent = s;
                          }
                          p.left = null;
                          if ((p.right = sr) != null)
                              sr.parent = p;
                          if ((s.left = pl) != null)
                              pl.parent = s;
                          if ((s.parent = pp) == null)
                              r = s;
                          else if (p == pp.left)
                              pp.left = s;
                          else
                              pp.right = s;
                          if (sr != null)
                              replacement = sr;
                          else
                              replacement = p;
                      }
                      else if (pl != null)
                          replacement = pl;
                      else if (pr != null)
                          replacement = pr;
                      else
                          replacement = p;
                      if (replacement != p) {
                          TreeNode<K,V> pp = replacement.parent = p.parent;
                          if (pp == null)
                              r = replacement;
                          else if (p == pp.left)
                              pp.left = replacement;
                          else
                              pp.right = replacement;
                          p.left = p.right = p.parent = null;
                      }
      
                      root = (p.red) ? r : balanceDeletion(r, replacement);
      
                      if (p == replacement) {  // detach pointers
                          TreeNode<K,V> pp;
                          if ((pp = p.parent) != null) {
                              if (p == pp.left)
                                  pp.left = null;
                              else if (p == pp.right)
                                  pp.right = null;
                              p.parent = null;
                          }
                      }
                  } finally {
                      unlockRoot();
                  }
                  assert checkInvariants(root);
                  return false;
              }
        }

1
2
3
4
5
6
7

  static final class ForwardingNode<K,V> extends Node<K,V> {
          final Node<K,V>[] nextTable;
          ForwardingNode(Node<K,V>[] tab) {
              super(MOVED, null, null, null);
              this.nextTable = tab;
          }
}

 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

    Node<K,V> find(int h, Object k) {
             // loop to avoid arbitrarily deep recursion on forwarding nodes
             outer: for (Node<K,V>[] tab = nextTable;;) {
                 Node<K,V> e; int n;
                 if (k == null || tab == null || (n = tab.length) == 0 ||
                     (e = tabAt(tab, (n - 1) & h)) == null)
                     return null;
                 for (;;) {
                     int eh; K ek;
                     if ((eh = e.hash) == h &&
                         ((ek = e.key) == k || (ek != null && k.equals(ek))))
                         return e;
                     if (eh < 0) {
                         if (e instanceof ForwardingNode) {
                             tab = ((ForwardingNode<K,V>)e).nextTable;
                             continue outer;
                         }
                         else
                             return e.find(h, k);
                     }
                     if ((e = e.next) == null)
                         return null;
                 }
             }
         } 

  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

       

    /**
     * 最大可能的表容量。
     */
    private static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 默认的初始表容量。必须是2(i)的幂
     */
    private static final int DEFAULT_CAPACITY = 16;

    /**
     * 最大可能的(非幂两)数组大小。需要的阵列和相关的方法。
     */
    static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * 负载因子。在构造函数中重写此值只会影响初始表的容量。实际浮点值通常不被使用 - 
     * 使用诸如{@code n - （n >>> 2 }之类的表达式可以更简单地实现关联的调整大小阈值。
     */
    private static final float LOAD_FACTOR = 0.75f;

    /**
     * 节点数量大于8，转化为红黑树结构
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * 节点数量小于6，转化为链表结构
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

    /**
     * Minimum number of rebinnings per transfer step. Ranges are
     * subdivided to allow multiple resizer threads.  This value
     * serves as a lower bound to avoid resizers encountering
     * excessive memory contention.  The value should be at least
     * DEFAULT_CAPACITY.
     */
    private static final int MIN_TRANSFER_STRIDE = 16;

    /**
     * sizeCtl中用于生成stamp的位数。  32位数组必须至少为6
     */
    private static int RESIZE_STAMP_BITS = 16;

    /**
     * 可以帮助调整大小的最大线程数。必须适合32 - RESIZE_STAMP_BITS位。
     */
    private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;

    /**
     * sizeCtl中记录尺寸的位变换。
     */
    private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;

    /*
     * Encodings for Node hash fields. See above for explanation.
     * 为节点哈希字段编码
     */
    static final int MOVED     = -1; // hash for forwarding nodes  hash值是-1，表示这是一个forwardNode节点
    static final int TREEBIN   = -2; // hash for roots of trees    hash值是-2 表示这时一个TreeBin节点
    static final int RESERVED  = -3; // hash for transient reservations hash值是-3  ReservationNode节点
    static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash 

    /** Number of CPUS, to place bounds on some sizings */
    static final int NCPU = Runtime.getRuntime().availableProcessors();

    /**

     * 数组
     */
    transient volatile Node<K,V>[] table;

    /**
     * rehash扩容时用到的新键值对数组
     */
    private transient volatile Node<K,V>[] nextTable;

    /**
     * 记录当前键值对总数，通过CAS更新，对所有线程可见
     */
    private transient volatile long baseCount;

    /**
     * 当`sizeCtl` < 0时，表示多个线程在等待扩容；
     * 当`sizeCtl` = 0时，默认值；
     * 当`sizeCtl` > 0时，表示扩容的阈值；初始化数组以前代表创建数组大小。
     */
    private transient volatile int sizeCtl;

    /**
     * 下表索引(+ 1)在调整大小时进行拆分。
     */
    private transient volatile int transferIndex;

    /**
     * 自旋锁
     */
    private transient volatile int cellsBusy;

    /**
     * counter cell表，长度总为2的幂次；
     */
    private transient volatile CounterCell[] counterCells;
}    

 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

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

    final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException(); 
        //XOR计算
        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)                 //初始化数组大小
                tab = initTable();
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {  //【(n - 1) & hash】获取数组下标，获取元素为空，CAS更新数组值
                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)                         // 正在扩容中，以前旧数组中，获取元素为空，保存ForwardingNode对象，hash==MOVED
                tab = helpTransfer(tab, f);                          // 获取新数组。协助迁移数组数据
            else {
                V oldVal = null;
                synchronized (f) {                                   //同步锁，锁定数组下标对象值
                    if (tabAt(tab, i) == f) {                        //二次判断
                        if (fh >= 0) {                               //hash大于零是普通节点           
                            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, null);
                                    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) {
                    if (binCount >= TREEIFY_THRESHOLD)  //普通节点数大于TREEIFY_THRESHOLD(8)转化为黑红树
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount); //添加数量
        return null;
    }

1
2
3

    static final int spread(int h) {
        return (h ^ (h >>> 16)) & HASH_BITS; //HASH_BITS = 0x7fffffff;Integer.MAX_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

   /**
    * Initializes table, using the size recorded in sizeCtl.
    */
   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(); 
           else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {  // CAS 修改sizeCtl为-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); // sc=(3/4)*n 扩容阈值
                   }
               } finally {
                   sizeCtl = sc;
               }
               break;
           }
       }
       return tab;
   }

 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

   /**
     * Helps transfer if a resize is in progress.
     * 如果调整了大小，可以帮助转移。
     */
    final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
        Node<K,V>[] nextTab; int sc;
        if (tab != null && (f instanceof ForwardingNode) &&
            (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
            int rs = resizeStamp(tab.length);                             
            while (nextTab == nextTable && table == tab &&
                   (sc = sizeCtl) < 0) {                  //sizeCtl 小于零时候，在扩容数组
                   //判断是否协助扩容时迁移旧数组数据。RESIZE_STAMP_SHIFT=16
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                    sc == rs + MAX_RESIZERS || transferIndex <= 0)
                    break;
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                    transfer(tab, nextTab);
                    break;
                }
            }
            return nextTab;
        }
        return table;
    }
   /**
     * 返回用于调整大小为n的table的标记位。向左移动RESIZE_STAMP_SHIFT时必须为负值。
     */
    static final int resizeStamp(int n) {
        //RESIZE_STAMP_BITS=16
        return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
    }    

 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

    private final void treeifyBin(Node<K,V>[] tab, int index) {
        Node<K,V> b; int n, sc;
        if (tab != null) {
            if ((n = tab.length) < MIN_TREEIFY_CAPACITY) //数组大小与MIN_TREEIFY_CAPACITY(64)，尝试扩容
                tryPresize(n << 1);
            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));
                    }
                }
            }
        }
    }

 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

    private final void tryPresize(int size) {
        int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
            tableSizeFor(size + (size >>> 1) + 1);
        int sc;
        while ((sc = sizeCtl) >= 0) {
            Node<K,V>[] tab = table; int n;
            if (tab == null || (n = tab.length) == 0) {
                n = (sc > c) ? sc : c;
                if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                    try {
                        if (table == tab) {
                            @SuppressWarnings("unchecked")
                            Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                            table = nt;
                            sc = n - (n >>> 2);
                        }
                    } finally {
                        sizeCtl = sc;
                    }
                }
            }
            else if (c <= sc || n >= MAXIMUM_CAPACITY)
                break;
            else if (tab == table) {
                int rs = resizeStamp(n);
                if (sc < 0) {
                    Node<K,V>[] nt;
                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                        transferIndex <= 0)
                        break;
                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                        transfer(tab, nt);
                }
                else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                             (rs << RESIZE_STAMP_SHIFT) + 2))
                    transfer(tab, null);
            }
        }
    }

 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[] as; long b, s;
        if ((as = counterCells) != null ||
            !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
            CounterCell a; long v; int m;
            boolean uncontended = true;
            if (as == null || (m = as.length - 1) < 0 ||
                (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
                !(uncontended =
                  U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
                fullAddCount(x, uncontended);
                return;
            }
            if (check <= 1)
                return;
            s = sumCount();
        }
        if (check >= 0) {
            Node<K,V>[] tab, nt; int n, sc;
            while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
                   (n = tab.length) < MAXIMUM_CAPACITY) {
                int rs = resizeStamp(n);
                if (sc < 0) {
                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                        transferIndex <= 0)
                        break;
                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                        transfer(tab, nt);
                }
                else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                             (rs << RESIZE_STAMP_SHIFT) + 2)) 
                    transfer(tab, null);//进行扩容操作
                s = sumCount();
            }
        }
    }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

   /* ---------------- Counter support -------------- */

   /**
    * A padded cell for distributing counts.  Adapted from LongAdder
    * and Striped64.  See their internal docs for explanation.
    */
   @sun.misc.Contended static final class CounterCell {
       volatile long value;
       CounterCell(long x) { value = x; }
   }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

   final long sumCount() {
       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;
   }

  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

    private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
        int n = tab.length, stride;
        // stride(步长)作用用于多线程并发处理迁移数据。分段处理机制，每个线程可以去负责每段数据处理。用于CPU数量大于1情况；
        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]; //2倍扩容
                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);//用于旧数组迁移到新数组，把旧数组中数据修改成ForwardingNode对象；
        boolean advance = true;
        boolean finishing = false; // to ensure sweep before committing nextTab
        for (int i = 0, bound = 0;;) {  
            Node<K,V> f; int fh;
            while (advance) {
                int nextIndex, nextBound;
                if (--i >= bound || finishing)       //递减分段下标索引
                    advance = false;
                else if ((nextIndex = transferIndex) <= 0) {  //transferIndex小于零，说明已迁移完毕！
                    i = -1;
                    advance = false;
                }
                else if (U.compareAndSwapInt
                         (this, TRANSFERINDEX, nextIndex,
                          nextBound = (nextIndex > stride ?
                                       nextIndex - stride : 0))) { //CAS处理transferIndex属性，告诉其他线程已处理下标索引。
                    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);//1.5倍扩容
                    return;
                }
                if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                    if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)  //sc - 2?? 因为扩容时，CAS修改sizectl属性为(resizeStamp(n) << RESIZE_STAMP_SHIFT)+2，所以这里判断是不是最后一个线程处理。
                        return;
                    finishing = advance = true;
                    i = n; // recheck before commit
                }
            }
            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;
                        if (fh >= 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) :  //红黑树节点数量小于等于UNTREEIFY_THRESHOLD(6)改成普通节点
                                (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;
                        }
                    }
                }
            }
        }
    }