ConcurrentHashMap

ConcurrentHashMap是在JDK1.5时，J.U.C引入的一个同步集合工具类，顾名思义，这是一个线程安全的HashMap。不同版本的ConcurrentHashMap，内部实现机制千差万别，本节所有的讨论基于JDK1.8。

image.png


ConcurrentMap接口提供的功能：

方法签名 功能
getOrDefault(Object key, V defaultValue) 返回指定key对应的值；如果Map不存在该key，则返回defaultValue
forEach(BiConsumer action) 遍历Map的所有Entry，并对其进行指定的aciton操作
putIfAbsent(K key, V value) 如果Map不存在指定的key，则插入；否则，直接返回该key对应的值
remove(Object key, Object value) 删除与完全匹配的Entry，并返回true；否则，返回false
replace(K key, V oldValue, V newValue) 如果存在key，且值和oldValue一致，则更新为newValue，并返回true；否则，返回false
replace(K key, V value) 如果存在key，则更新为value，返回旧value；否则，返回null
replaceAll(BiFunction function) 遍历Map的所有Entry，并对其进行指定的funtion操作
computeIfAbsent(K key, Function mappingFunction) 如果Map不存在指定的key，则通过mappingFunction计算value并插入
computeIfPresent(K key, BiFunction remappingFunction) 如果Map存在指定的key，则通过mappingFunction计算value并替换旧值
compute(K key, BiFunction remappingFunction) 根据指定的key，查找value；然后根据得到的value和remappingFunction重新计算新值，并替换旧值
merge(K key, V value, BiFunction remappingFunction) 如果key不存在，则插入value；否则，根据key对应的值和remappingFunction计算新值，并替换旧值

ConcurrentHashMap基本结构

我们先来看下ConcurrentHashMap对象的内部结构究竟什么样的：
J.U.C——ConcurrentHashMap - 图2

基本结构

ConcurrentHashMap内部维护了一个Node类型的数组，也就是table：
transient volatile Node<K, V>[] table;
数组的每一个位置table[i]代表了一个桶，当插入键值对时，会根据键的hash值映射到不同的桶位置，table一共可以包含4种不同类型的桶：Node、TreeBin、ForwardingNode、ReservationNode。上图中，不同的桶用不同颜色表示。可以看到，有的桶链接着链表，有的桶链接着树，这也是JDK1.8中ConcurrentHashMap的特殊之处，后面会详细讲到。
需要注意的是：TreeBin所链接的是一颗红黑树，红黑树的结点用TreeNode表示，所以ConcurrentHashMap中实际上一共有五种不同类型的Node结点。
之所以用TreeBin而不是直接用TreeNode，是因为红黑树的操作比较复杂，包括构建、左旋、右旋、删除，平衡等操作，用一个代理结点TreeBin来包含这些复杂操作，其实是一种“职责分离”的思想。另外TreeBin中也包含了一些加/解锁的操作。

在JDK1.8之前，ConcurrentHashMap采用了分段锁的设计思路，以减少热点域的冲突。JDK1.8时不再延续，转而直接对每个桶加锁，并用“红黑树”链接冲突结点。关于红黑树和一般HashMap的实现思路，读者可以参考《Algorithms 4th》，或我之前写的博文：红黑树 和 哈希表 ，本文不会对红黑树的相关操作具体分析。

结点定义

上一节提到，ConcurrentHashMap一共包含5种结点，我们来看下各个结点的定义和作用。
1、Node结点
Node结点的定义非常简单，也是其它四种类型结点的父类。

默认链接到table[i] ——桶上的结点就是Node结点。当出现hash冲突时，Node结点会首先以链表的形式链接到table上，当结点数量超过一定数目时，链表会转化为红黑树。因为链表查找的平均时间复杂度为O(n) ，而红黑树是一种平衡二叉树，其平均时间复杂度为O(logn) 。

  1. /**
  2.  * 普通的Entry结点, 以链表形式保存时才会使用, 存储实际的数据.
  3.  */
  4. static class Node<K, V> implements Map.Entry<K, V> {
  5.     final int hash;
  6.     final K key;
  7.     volatile V val;
  8.     volatile Node<K, V> next;   // 链表指针
  9.     Node(int hash, K key, V val, Node<K, V> next) {
  10.         this.hash = hash;
  11.         this.key = key;
  12.         this.val = val;
  13.         this.next = next;
  14.     }
  15.     public final K getKey() {
  16.         return key;
  17.     }
  18.     public final V getValue() {
  19.         return val;
  20.     }
  21.     public final int hashCode() {
  22.         return key.hashCode() ^ val.hashCode();
  23.     }
  24.     public final String toString() {
  25.         return key + "=" + val;
  26.     }
  27.     public final V setValue(V value) {
  28.         throw new UnsupportedOperationException();
  29.     }
  30.     public final boolean equals(Object o) {
  31.         Object k, v, u;
  32.         Map.Entry<?, ?> e;
  33.         return ((o instanceof Map.Entry) &&
  34.             (k = (e = (Map.Entry<?, ?>) o).getKey()) != null &&
  35.             (v = e.getValue()) != null &&
  36.             (k == key || k.equals(key)) &&
  37.             (v == (u = val) || v.equals(u)));
  38.     }
  39.     /**
  40.      * 链表查找.
  41.      */
  42.     Node<K, V> find(int h, Object k) {
  43.         Node<K, V> e = this;
  44.         if (k != null) {
  45.             do {
  46.                 K ek;
  47.                 if (e.hash == h &&
  48.                     ((ek = e.key) == k || (ek != null && k.equals(ek))))
  49.                     return e;
  50.             } while ((e = e.next) != null);
  51.         }
  52.         return null;
  53.     }
  54. }

2、TreeNode结点
TreeNode就是红黑树的结点，TreeNode不会直接链接到table[i]——桶上面，而是由TreeBin链接，TreeBin会指向红黑树的根结点。

  1. /**
  2.  * 红黑树结点, 存储实际的数据.
  3.  */
  4. static final class TreeNode<K, V> extends Node<K, V> {
  5.     boolean red;
  6.     TreeNode<K, V> parent;
  7.     TreeNode<K, V> left;
  8.     TreeNode<K, V> right;
  9.     /**
  10.      * prev指针是为了方便删除.
  11.      * 删除链表的非头结点时，需要知道它的前驱结点才能删除，所以直接提供一个prev指针
  12.      */
  13.     TreeNode<K, V> prev;
  14.     TreeNode(int hash, K key, V val, Node<K, V> next,
  15.              TreeNode<K, V> parent) {
  16.         super(hash, key, val, next);
  17.         this.parent = parent;
  18.     }
  19.     Node<K, V> find(int h, Object k) {
  20.         return findTreeNode(h, k, null);
  21.     }
  22.     /**
  23.      * 以当前结点（this）为根结点，开始遍历查找指定key.
  24.      */
  25.     final TreeNode<K, V> findTreeNode(int h, Object k, Class<?> kc) {
  26.         if (k != null) {
  27.             TreeNode<K, V> p = this;
  28.             do {
  29.                 int ph, dir;
  30.                 K pk;
  31.                 TreeNode<K, V> q;
  32.                 TreeNode<K, V> pl = p.left, pr = p.right;
  33.                 if ((ph = p.hash) > h)
  34.                     p = pl;
  35.                 else if (ph < h)
  36.                     p = pr;
  37.                 else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
  38.                     return p;
  39.                 else if (pl == null)
  40.                     p = pr;
  41.                 else if (pr == null)
  42.                     p = pl;
  43.                 else if ((kc != null ||
  44.                     (kc = comparableClassFor(k)) != null) &&
  45.                     (dir = compareComparables(kc, k, pk)) != 0)
  46.                     p = (dir < 0) ? pl : pr;
  47.                 else if ((q = pr.findTreeNode(h, k, kc)) != null)
  48.                     return q;
  49.                 else
  50.                     p = pl;
  51.             } while (p != null);
  52.         }
  53.         return null;
  54.     }
  55. }

3、TreeBin结点
TreeBin相当于TreeNode的代理结点。TreeBin会直接链接到table[i]——桶上面，该结点提供了一系列红黑树相关的操作，以及加锁、解锁操作。

  1. /**
  2.  * TreeNode的代理结点（相当于封装了TreeNode的容器，提供针对红黑树的转换操作和锁控制）
  3.  * hash值固定为-3
  4.  */
  5. static final class TreeBin<K, V> extends Node<K, V> {
  6.     TreeNode<K, V> root;                // 红黑树结构的根结点
  7.     volatile TreeNode<K, V> first;      // 链表结构的头结点
  8.     volatile Thread waiter;             // 最近的一个设置WAITER标识位的线程
  9.     volatile int lockState;             // 整体的锁状态标识位
  10.     static final int WRITER = 1;        // 二进制001，红黑树的写锁状态
  11.     static final int WAITER = 2;        // 二进制010，红黑树的等待获取写锁状态
  12.     static final int READER = 4;        // 二进制100，红黑树的读锁状态，读可以并发，每多一个读线程，lockState都加上一个READER值
  13.     /**
  14.      * 在hashCode相等并且不是Comparable类型时，用此方法判断大小.
  15.      */
  16.     static int tieBreakOrder(Object a, Object b) {
  17.         int d;
  18.         if (a == null || b == null ||
  19.             (d = a.getClass().getName().
  20.                 compareTo(b.getClass().getName())) == 0)
  21.             d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
  22.                 -1 : 1);
  23.         return d;
  24.     }
  25.     /**
  26.      * 将以b为头结点的链表转换为红黑树.
  27.      */
  28.     TreeBin(TreeNode<K, V> b) {
  29.         super(TREEBIN, null, null, null);
  30.         this.first = b;
  31.         TreeNode<K, V> r = null;
  32.         for (TreeNode<K, V> x = b, next; x != null; x = next) {
  33.             next = (TreeNode<K, V>) x.next;
  34.             x.left = x.right = null;
  35.             if (r == null) {
  36.                 x.parent = null;
  37.                 x.red = false;
  38.                 r = x;
  39.             } else {
  40.                 K k = x.key;
  41.                 int h = x.hash;
  42.                 Class<?> kc = null;
  43.                 for (TreeNode<K, V> p = r; ; ) {
  44.                     int dir, ph;
  45.                     K pk = p.key;
  46.                     if ((ph = p.hash) > h)
  47.                         dir = -1;
  48.                     else if (ph < h)
  49.                         dir = 1;
  50.                     else if ((kc == null &&
  51.                         (kc = comparableClassFor(k)) == null) ||
  52.                         (dir = compareComparables(kc, k, pk)) == 0)
  53.                         dir = tieBreakOrder(k, pk);
  54.                     TreeNode<K, V> xp = p;
  55.                     if ((p = (dir <= 0) ? p.left : p.right) == null) {
  56.                         x.parent = xp;
  57.                         if (dir <= 0)
  58.                             xp.left = x;
  59.                         else
  60.                             xp.right = x;
  61.                         r = balanceInsertion(r, x);
  62.                         break;
  63.                     }
  64.                 }
  65.             }
  66.         }
  67.         this.root = r;
  68.         assert checkInvariants(root);
  69.     }
  70.     /**
  71.      * 对红黑树的根结点加写锁.
  72.      */
  73.     private final void lockRoot() {
  74.         if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
  75.             contendedLock();
  76.     }
  77.     /**
  78.      * 释放写锁.
  79.      */
  80.     private final void unlockRoot() {
  81.         lockState = 0;
  82.     }
  83.     /**
  84.      * Possibly blocks awaiting root lock.
  85.      */
  86.     private final void contendedLock() {
  87.         boolean waiting = false;
  88.         for (int s; ; ) {
  89.             if (((s = lockState) & ~WAITER) == 0) {
  90.                 if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
  91.                     if (waiting)
  92.                         waiter = null;
  93.                     return;
  94.                 }
  95.             } else if ((s & WAITER) == 0) {
  96.                 if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
  97.                     waiting = true;
  98.                     waiter = Thread.currentThread();
  99.                 }
  100.             } else if (waiting)
  101.                 LockSupport.park(this);
  102.         }
  103.     }
  104.     /**
  105.      * 从根结点开始遍历查找，找到“相等”的结点就返回它，没找到就返回null
  106.      * 当存在写锁时，以链表方式进行查找
  107.      */
  108.     final Node<K, V> find(int h, Object k) {
  109.         if (k != null) {
  110.             for (Node<K, V> e = first; e != null; ) {
  111.                 int s;
  112.                 K ek;
  113.                 /**
  114.                  * 两种特殊情况下以链表的方式进行查找:
  115.                  * 1. 有线程正持有写锁，这样做能够不阻塞读线程
  116.                  * 2. 有线程等待获取写锁，不再继续加读锁，相当于“写优先”模式
  117.                  */
  118.                 if (((s = lockState) & (WAITER | WRITER)) != 0) {
  119.                     if (e.hash == h &&
  120.                         ((ek = e.key) == k || (ek != null && k.equals(ek))))
  121.                         return e;
  122.                     e = e.next;
  123.                 } else if (U.compareAndSwapInt(this, LOCKSTATE, s,
  124.                     s + READER)) {
  125.                     TreeNode<K, V> r, p;
  126.                     try {
  127.                         p = ((r = root) == null ? null :
  128.                             r.findTreeNode(h, k, null));
  129.                     } finally {
  130.                         Thread w;
  131.                         if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
  132.                             (READER | WAITER) && (w = waiter) != null)
  133.                             LockSupport.unpark(w);
  134.                     }
  135.                     return p;
  136.                 }
  137.             }
  138.         }
  139.         return null;
  140.     }
  141.     /**
  142.      * 查找指定key对应的结点,如果未找到，则插入.
  143.      *
  144.      * @return 插入成功返回null, 否则返回找到的结点
  145.      */
  146.     final TreeNode<K, V> putTreeVal(int h, K k, V v) {
  147.         Class<?> kc = null;
  148.         boolean searched = false;
  149.         for (TreeNode<K, V> p = root; ; ) {
  150.             int dir, ph;
  151.             K pk;
  152.             if (p == null) {
  153.                 first = root = new TreeNode<K, V>(h, k, v, null, null);
  154.                 break;
  155.             } else if ((ph = p.hash) > h)
  156.                 dir = -1;
  157.             else if (ph < h)
  158.                 dir = 1;
  159.             else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
  160.                 return p;
  161.             else if ((kc == null &&
  162.                 (kc = comparableClassFor(k)) == null) ||
  163.                 (dir = compareComparables(kc, k, pk)) == 0) {
  164.                 if (!searched) {
  165.                     TreeNode<K, V> q, ch;
  166.                     searched = true;
  167.                     if (((ch = p.left) != null &&
  168.                         (q = ch.findTreeNode(h, k, kc)) != null) ||
  169.                         ((ch = p.right) != null &&
  170.                             (q = ch.findTreeNode(h, k, kc)) != null))
  171.                         return q;
  172.                 }
  173.                 dir = tieBreakOrder(k, pk);
  174.             }
  175.             TreeNode<K, V> xp = p;
  176.             if ((p = (dir <= 0) ? p.left : p.right) == null) {
  177.                 TreeNode<K, V> x, f = first;
  178.                 first = x = new TreeNode<K, V>(h, k, v, f, xp);
  179.                 if (f != null)
  180.                     f.prev = x;
  181.                 if (dir <= 0)
  182.                     xp.left = x;
  183.                 else
  184.                     xp.right = x;
  185.                 if (!xp.red)
  186.                     x.red = true;
  187.                 else {
  188.                     lockRoot();
  189.                     try {
  190.                         root = balanceInsertion(root, x);
  191.                     } finally {
  192.                         unlockRoot();
  193.                     }
  194.                 }
  195.                 break;
  196.             }
  197.         }
  198.         assert checkInvariants(root);
  199.         return null;
  200.     }
  201.     /**
  202.      * 删除红黑树的结点：
  203.      * 1. 红黑树规模太小时，返回true，然后进行 树 -> 链表 的转化;
  204.      * 2. 红黑树规模足够时，不用变换成链表，但删除结点时需要加写锁.
  205.      */
  206.     final boolean removeTreeNode(TreeNode<K, V> p) {
  207.         TreeNode<K, V> next = (TreeNode<K, V>) p.next;
  208.         TreeNode<K, V> pred = p.prev;  // unlink traversal pointers
  209.         TreeNode<K, V> r, rl;
  210.         if (pred == null)
  211.             first = next;
  212.         else
  213.             pred.next = next;
  214.         if (next != null)
  215.             next.prev = pred;
  216.         if (first == null) {
  217.             root = null;
  218.             return true;
  219.         }
  220.         if ((r = root) == null || r.right == null || // too small
  221.             (rl = r.left) == null || rl.left == null)
  222.             return true;
  223.         lockRoot();
  224.         try {
  225.             TreeNode<K, V> replacement;
  226.             TreeNode<K, V> pl = p.left;
  227.             TreeNode<K, V> pr = p.right;
  228.             if (pl != null && pr != null) {
  229.                 TreeNode<K, V> s = pr, sl;
  230.                 while ((sl = s.left) != null) // find successor
  231.                     s = sl;
  232.                 boolean c = s.red;
  233.                 s.red = p.red;
  234.                 p.red = c; // swap colors
  235.                 TreeNode<K, V> sr = s.right;
  236.                 TreeNode<K, V> pp = p.parent;
  237.                 if (s == pr) { // p was s's direct parent
  238.                     p.parent = s;
  239.                     s.right = p;
  240.                 } else {
  241.                     TreeNode<K, V> sp = s.parent;
  242.                     if ((p.parent = sp) != null) {
  243.                         if (s == sp.left)
  244.                             sp.left = p;
  245.                         else
  246.                             sp.right = p;
  247.                     }
  248.                     if ((s.right = pr) != null)
  249.                         pr.parent = s;
  250.                 }
  251.                 p.left = null;
  252.                 if ((p.right = sr) != null)
  253.                     sr.parent = p;
  254.                 if ((s.left = pl) != null)
  255.                     pl.parent = s;
  256.                 if ((s.parent = pp) == null)
  257.                     r = s;
  258.                 else if (p == pp.left)
  259.                     pp.left = s;
  260.                 else
  261.                     pp.right = s;
  262.                 if (sr != null)
  263.                     replacement = sr;
  264.                 else
  265.                     replacement = p;
  266.             } else if (pl != null)
  267.                 replacement = pl;
  268.             else if (pr != null)
  269.                 replacement = pr;
  270.             else
  271.                 replacement = p;
  272.             if (replacement != p) {
  273.                 TreeNode<K, V> pp = replacement.parent = p.parent;
  274.                 if (pp == null)
  275.                     r = replacement;
  276.                 else if (p == pp.left)
  277.                     pp.left = replacement;
  278.                 else
  279.                     pp.right = replacement;
  280.                 p.left = p.right = p.parent = null;
  281.             }
  282.             root = (p.red) ? r : balanceDeletion(r, replacement);
  283.             if (p == replacement) {  // detach pointers
  284.                 TreeNode<K, V> pp;
  285.                 if ((pp = p.parent) != null) {
  286.                     if (p == pp.left)
  287.                         pp.left = null;
  288.                     else if (p == pp.right)
  289.                         pp.right = null;
  290.                     p.parent = null;
  291.                 }
  292.             }
  293.         } finally {
  294.             unlockRoot();
  295.         }
  296.         assert checkInvariants(root);
  297.         return false;
  298.     }
  299.     // 以下是红黑树的经典操作方法，改编自《算法导论》
  300.     static <K, V> TreeNode<K, V> rotateLeft(TreeNode<K, V> root,
  301.                                             TreeNode<K, V> p) {
  302.         TreeNode<K, V> r, pp, rl;
  303.         if (p != null && (r = p.right) != null) {
  304.             if ((rl = p.right = r.left) != null)
  305.                 rl.parent = p;
  306.             if ((pp = r.parent = p.parent) == null)
  307.                 (root = r).red = false;
  308.             else if (pp.left == p)
  309.                 pp.left = r;
  310.             else
  311.                 pp.right = r;
  312.             r.left = p;
  313.             p.parent = r;
  314.         }
  315.         return root;
  316.     }
  317.     static <K, V> TreeNode<K, V> rotateRight(TreeNode<K, V> root,
  318.                                              TreeNode<K, V> p) {
  319.         TreeNode<K, V> l, pp, lr;
  320.         if (p != null && (l = p.left) != null) {
  321.             if ((lr = p.left = l.right) != null)
  322.                 lr.parent = p;
  323.             if ((pp = l.parent = p.parent) == null)
  324.                 (root = l).red = false;
  325.             else if (pp.right == p)
  326.                 pp.right = l;
  327.             else
  328.                 pp.left = l;
  329.             l.right = p;
  330.             p.parent = l;
  331.         }
  332.         return root;
  333.     }
  334.     static <K, V> TreeNode<K, V> balanceInsertion(TreeNode<K, V> root,
  335.                                                   TreeNode<K, V> x) {
  336.         x.red = true;
  337.         for (TreeNode<K, V> xp, xpp, xppl, xppr; ; ) {
  338.             if ((xp = x.parent) == null) {
  339.                 x.red = false;
  340.                 return x;
  341.             } else if (!xp.red || (xpp = xp.parent) == null)
  342.                 return root;
  343.             if (xp == (xppl = xpp.left)) {
  344.                 if ((xppr = xpp.right) != null && xppr.red) {
  345.                     xppr.red = false;
  346.                     xp.red = false;
  347.                     xpp.red = true;
  348.                     x = xpp;
  349.                 } else {
  350.                     if (x == xp.right) {
  351.                         root = rotateLeft(root, x = xp);
  352.                         xpp = (xp = x.parent) == null ? null : xp.parent;
  353.                     }
  354.                     if (xp != null) {
  355.                         xp.red = false;
  356.                         if (xpp != null) {
  357.                             xpp.red = true;
  358.                             root = rotateRight(root, xpp);
  359.                         }
  360.                     }
  361.                 }
  362.             } else {
  363.                 if (xppl != null && xppl.red) {
  364.                     xppl.red = false;
  365.                     xp.red = false;
  366.                     xpp.red = true;
  367.                     x = xpp;
  368.                 } else {
  369.                     if (x == xp.left) {
  370.                         root = rotateRight(root, x = xp);
  371.                         xpp = (xp = x.parent) == null ? null : xp.parent;
  372.                     }
  373.                     if (xp != null) {
  374.                         xp.red = false;
  375.                         if (xpp != null) {
  376.                             xpp.red = true;
  377.                             root = rotateLeft(root, xpp);
  378.                         }
  379.                     }
  380.                 }
  381.             }
  382.         }
  383.     }
  384.     static <K, V> TreeNode<K, V> balanceDeletion(TreeNode<K, V> root,
  385.                                                  TreeNode<K, V> x) {
  386.         for (TreeNode<K, V> xp, xpl, xpr; ; ) {
  387.             if (x == null || x == root)
  388.                 return root;
  389.             else if ((xp = x.parent) == null) {
  390.                 x.red = false;
  391.                 return x;
  392.             } else if (x.red) {
  393.                 x.red = false;
  394.                 return root;
  395.             } else if ((xpl = xp.left) == x) {
  396.                 if ((xpr = xp.right) != null && xpr.red) {
  397.                     xpr.red = false;
  398.                     xp.red = true;
  399.                     root = rotateLeft(root, xp);
  400.                     xpr = (xp = x.parent) == null ? null : xp.right;
  401.                 }
  402.                 if (xpr == null)
  403.                     x = xp;
  404.                 else {
  405.                     TreeNode<K, V> sl = xpr.left, sr = xpr.right;
  406.                     if ((sr == null || !sr.red) &&
  407.                         (sl == null || !sl.red)) {
  408.                         xpr.red = true;
  409.                         x = xp;
  410.                     } else {
  411.                         if (sr == null || !sr.red) {
  412.                             if (sl != null)
  413.                                 sl.red = false;
  414.                             xpr.red = true;
  415.                             root = rotateRight(root, xpr);
  416.                             xpr = (xp = x.parent) == null ?
  417.                                 null : xp.right;
  418.                         }
  419.                         if (xpr != null) {
  420.                             xpr.red = (xp == null) ? false : xp.red;
  421.                             if ((sr = xpr.right) != null)
  422.                                 sr.red = false;
  423.                         }
  424.                         if (xp != null) {
  425.                             xp.red = false;
  426.                             root = rotateLeft(root, xp);
  427.                         }
  428.                         x = root;
  429.                     }
  430.                 }
  431.             } else { // symmetric
  432.                 if (xpl != null && xpl.red) {
  433.                     xpl.red = false;
  434.                     xp.red = true;
  435.                     root = rotateRight(root, xp);
  436.                     xpl = (xp = x.parent) == null ? null : xp.left;
  437.                 }
  438.                 if (xpl == null)
  439.                     x = xp;
  440.                 else {
  441.                     TreeNode<K, V> sl = xpl.left, sr = xpl.right;
  442.                     if ((sl == null || !sl.red) &&
  443.                         (sr == null || !sr.red)) {
  444.                         xpl.red = true;
  445.                         x = xp;
  446.                     } else {
  447.                         if (sl == null || !sl.red) {
  448.                             if (sr != null)
  449.                                 sr.red = false;
  450.                             xpl.red = true;
  451.                             root = rotateLeft(root, xpl);
  452.                             xpl = (xp = x.parent) == null ?
  453.                                 null : xp.left;
  454.                         }
  455.                         if (xpl != null) {
  456.                             xpl.red = (xp == null) ? false : xp.red;
  457.                             if ((sl = xpl.left) != null)
  458.                                 sl.red = false;
  459.                         }
  460.                         if (xp != null) {
  461.                             xp.red = false;
  462.                             root = rotateRight(root, xp);
  463.                         }
  464.                         x = root;
  465.                     }
  466.                 }
  467.             }
  468.         }
  469.     }
  470.     /**
  471.      * 递归检查红黑树的正确性
  472.      */
  473.     static <K, V> boolean checkInvariants(TreeNode<K, V> t) {
  474.         TreeNode<K, V> tp = t.parent, tl = t.left, tr = t.right,
  475.             tb = t.prev, tn = (TreeNode<K, V>) t.next;
  476.         if (tb != null && tb.next != t)
  477.             return false;
  478.         if (tn != null && tn.prev != t)
  479.             return false;
  480.         if (tp != null && t != tp.left && t != tp.right)
  481.             return false;
  482.         if (tl != null && (tl.parent != t || tl.hash > t.hash))
  483.             return false;
  484.         if (tr != null && (tr.parent != t || tr.hash < t.hash))
  485.             return false;
  486.         if (t.red && tl != null && tl.red && tr != null && tr.red)
  487.             return false;
  488.         if (tl != null && !checkInvariants(tl))
  489.             return false;
  490.         if (tr != null && !checkInvariants(tr))
  491.             return false;
  492.         return true;
  493.     }
  494.     private static final sun.misc.Unsafe U;
  495.     private static final long LOCKSTATE;
  496.     static {
  497.         try {
  498.             U = sun.misc.Unsafe.getUnsafe();
  499.             Class<?> k = TreeBin.class;
  500.             LOCKSTATE = U.objectFieldOffset
  501.                 (k.getDeclaredField("lockState"));
  502.         } catch (Exception e) {
  503.             throw new Error(e);
  504.         }
  505.     }
  506. }

4、ForwardingNode结点
ForwardingNode结点仅仅在扩容时才会使用——关于扩容，会在下一篇文章专门论述

  1. /**
  2.  * ForwardingNode是一种临时结点，在扩容进行中才会出现，hash值固定为-1，且不存储实际数据。
  3.  * 如果旧table数组的一个hash桶中全部的结点都迁移到了新table中，则在这个桶中放置一个ForwardingNode。
  4.  * 读操作碰到ForwardingNode时，将操作转发到扩容后的新table数组上去执行；写操作碰见它时，则尝试帮助扩容。
  5.  */
  6. static final class ForwardingNode<K, V> extends Node<K, V> {
  7.     final Node<K, V>[] nextTable;
  8.     ForwardingNode(Node<K, V>[] tab) {
  9.         super(MOVED, null, null, null);
  10.         this.nextTable = tab;
  11.     }
  12.     // 在新的数组nextTable上进行查找
  13.     Node<K, V> find(int h, Object k) {
  14.         // loop to avoid arbitrarily deep recursion on forwarding nodes
  15.         outer:
  16.         for (Node<K, V>[] tab = nextTable; ; ) {
  17.             Node<K, V> e;
  18.             int n;
  19.             if (k == null || tab == null || (n = tab.length) == 0 ||
  20.                 (e = tabAt(tab, (n - 1) & h)) == null)
  21.                 return null;
  22.             for (; ; ) {
  23.                 int eh;
  24.                 K ek;
  25.                 if ((eh = e.hash) == h &&
  26.                     ((ek = e.key) == k || (ek != null && k.equals(ek))))
  27.                     return e;
  28.                 if (eh < 0) {
  29.                     if (e instanceof ForwardingNode) {
  30.                         tab = ((ForwardingNode<K, V>) e).nextTable;
  31.                         continue outer;
  32.                     } else
  33.                         return e.find(h, k);
  34.                 }
  35.                 if ((e = e.next) == null)
  36.                     return null;
  37.             }
  38.         }
  39.     }
  40. }

5、ReservationNode结点
保留结点，ConcurrentHashMap中的一些特殊方法会专门用到该类结点。

  1. /**
  2.  * 保留结点.
  3.  * hash值固定为-3， 不保存实际数据
  4.  * 只在computeIfAbsent和compute这两个函数式API中充当占位符加锁使用
  5.  */
  6. static final class ReservationNode<K, V> extends Node<K, V> {
  7.     ReservationNode() {
  8.         super(RESERVED, null, null, null);
  9.     }
  10.     Node<K, V> find(int h, Object k) {
  11.         return null;
  12.     }
  13. }

ConcurrentHashMap的构造

构造器定义

ConcurrentHashMap提供了五个构造器，这五个构造器内部最多也只是计算了下table的初始容量大小，并没有进行实际的创建table数组的工作：

ConcurrentHashMap，采用了一种“懒加载”的模式，只有到首次插入键值对的时候，才会真正的去初始化table数组。

空构造器

  1. public ConcurrentHashMap() {
  2. }

指定table初始容量的构造器

  1. /**
  2.  * 指定table初始容量的构造器.
  3.  * tableSizeFor会返回大于入参（initialCapacity + (initialCapacity >>> 1) + 1）的最小2次幂值
  4.  */
  5. public ConcurrentHashMap(int initialCapacity) {
  6.     if (initialCapacity < 0)
  7.         throw new IllegalArgumentException();
  8.     int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
  9.         tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
  10.     this.sizeCtl = cap;
  11. }

根据已有的Map构造

  1. /**
  2.  * 根据已有的Map构造ConcurrentHashMap.
  3.  */
  4. public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
  5.     this.sizeCtl = DEFAULT_CAPACITY;
  6.     putAll(m);
  7. }

指定table初始容量和负载因子的构造器

  1. /**
  2.  * 指定table初始容量和负载因子的构造器.
  3.  */
  4. public ConcurrentHashMap(int initialCapacity, float loadFactor) {
  5.     this(initialCapacity, loadFactor, 1);
  6. }

指定table初始容量、负载因子、并发级别的构造器

  1. /**
  2.  * 指定table初始容量、负载因子、并发级别的构造器.
  3.  * <p>
  4.  * 注意：concurrencyLevel只是为了兼容JDK1.8以前的版本，并不是实际的并发级别，loadFactor也不是实际的负载因子
  5.  * 这两个都失去了原有的意义，仅仅对初始容量有一定的控制作用
  6.  */
  7. public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
  8.     if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
  9.         throw new IllegalArgumentException();
  10.     if (initialCapacity < concurrencyLevel)
  11.         initialCapacity = concurrencyLevel;
  12.     long size = (long) (1.0 + (long) initialCapacity / loadFactor);
  13.     int cap = (size >= (long) MAXIMUM_CAPACITY) ?
  14.         MAXIMUM_CAPACITY : tableSizeFor((int) size);
  15.     this.sizeCtl = cap;
  16. }

常量/字段定义

我们再看下ConcurrentHashMap内部定义了哪些常量/字段，先大致熟悉下这些常量/字段，后面结合具体的方法分析就能相对容易地理解这些常量/字段的含义了。
常量 :

  1. /**
  2.  * 最大容量.
  3.  */
  4. private static final int MAXIMUM_CAPACITY = 1 << 30;
  5. /**
  6.  * 默认初始容量
  7.  */
  8. private static final int DEFAULT_CAPACITY = 16;
  9. /**
  10.  * The largest possible (non-power of two) array size.
  11.  * Needed by toArray and related methods.
  12.  */
  13. static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  14. /**
  15.  * 负载因子，为了兼容JDK1.8以前的版本而保留。
  16.  * JDK1.8中的ConcurrentHashMap的负载因子恒定为0.75
  17.  */
  18. private static final float LOAD_FACTOR = 0.75f;
  19. /**
  20.  * 链表转树的阈值，即链接结点数大于8时， 链表转换为树.
  21.  */
  22. static final int TREEIFY_THRESHOLD = 8;
  23. /**
  24.  * 树转链表的阈值，即树结点树小于6时，树转换为链表.
  25.  */
  26. static final int UNTREEIFY_THRESHOLD = 6;
  27. /**
  28.  * 在链表转变成树之前，还会有一次判断：
  29.  * 即只有键值对数量大于MIN_TREEIFY_CAPACITY，才会发生转换。
  30.  * 这是为了避免在Table建立初期，多个键值对恰好被放入了同一个链表中而导致不必要的转化。
  31.  */
  32. static final int MIN_TREEIFY_CAPACITY = 64;
  33. /**
  34.  * 在树转变成链表之前，还会有一次判断：
  35.  * 即只有键值对数量小于MIN_TRANSFER_STRIDE，才会发生转换.
  36.  */
  37. private static final int MIN_TRANSFER_STRIDE = 16;
  38. /**
  39.  * 用于在扩容时生成唯一的随机数.
  40.  */
  41. private static int RESIZE_STAMP_BITS = 16;
  42. /**
  43.  * 可同时进行扩容操作的最大线程数.
  44.  */
  45. private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
  46. /**
  47.  * The bit shift for recording size stamp in sizeCtl.
  48.  */
  49. private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
  50. static final int MOVED = -1;                // 标识ForwardingNode结点（在扩容时才会出现，不存储实际数据）
  51. static final int TREEBIN = -2;              // 标识红黑树的根结点
  52. static final int RESERVED = -3;             // 标识ReservationNode结点（）
  53. static final int HASH_BITS = 0x7fffffff;    // usable bits of normal node hash
  54. /**
  55.  * CPU核心数，扩容时使用
  56.  */
  57. static final int NCPU = Runtime.getRuntime().availableProcessors();

字段 :

  1. /**
  2.  * Node数组，标识整个Map，首次插入元素时创建，大小总是2的幂次.
  3.  */
  4. transient volatile Node<K, V>[] table;
  5. /**
  6.  * 扩容后的新Node数组，只有在扩容时才非空.
  7.  */
  8. private transient volatile Node<K, V>[] nextTable;
  9. /**
  10.  * 控制table的初始化和扩容.
  11.  * 0  : 初始默认值
  12.  * -1 : 有线程正在进行table的初始化
  13.  * >0 : table初始化时使用的容量，或初始化/扩容完成后的threshold
  14.  * -(1 + nThreads) : 记录正在执行扩容任务的线程数
  15.  */
  16. private transient volatile int sizeCtl;
  17. /**
  18.  * 扩容时需要用到的一个下标变量.
  19.  */
  20. private transient volatile int transferIndex;
  21. /**
  22.  * 计数基值,当没有线程竞争时，计数将加到该变量上。类似于LongAdder的base变量
  23.  */
  24. private transient volatile long baseCount;
  25. /**
  26.  * 计数数组，出现并发冲突时使用。类似于LongAdder的cells数组
  27.  */
  28. private transient volatile CounterCell[] counterCells;
  29. /**
  30.  * 自旋标识位，用于CounterCell[]扩容时使用。类似于LongAdder的cellsBusy变量
  31.  */
  32. private transient volatile int cellsBusy;
  33. // 视图相关字段
  34. private transient KeySetView<K, V> keySet;
  35. private transient ValuesView<K, V> values;
  36. private transient EntrySetView<K, V> entrySet;

ConcurrentHashMap的put操作

我们来看下ConcurrentHashMap如何插入一个元素：

  1. /**
  2.  * 插入键值对，<K,V>均不能为null.
  3.  */
  4. public V put(K key, V value) {
  5.     return putVal(key, value, false);
  6. }

put方法内部调用了putVal这个私有方法：

  1. /**
  2.  * 实际的插入操作
  3.  *
  4.  * @param onlyIfAbsent true:仅当key不存在时,才插入
  5.  */
  6. final V putVal(K key, V value, boolean onlyIfAbsent) {
  7.     if (key == null || value == null) throw new NullPointerException();
  8.     int hash = spread(key.hashCode());  // 再次计算hash值
  9.     /**
  10.      * 使用链表保存时，binCount记录table[i]这个桶中所保存的结点数；
  11.      * 使用红黑树保存时，binCount==2，保证put后更改计数值时能够进行扩容检查，同时不触发红黑树化操作
  12.      */
  13.     int binCount = 0;
  14.     for (Node<K, V>[] tab = table; ; ) {            // 自旋插入结点，直到成功
  15.         Node<K, V> f;
  16.         int n, i, fh;
  17.         if (tab == null || (n = tab.length) == 0)                   // CASE1: 首次初始化table —— 懒加载
  18.             tab = initTable();
  19.         else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {    // CASE2: table[i]对应的桶为null
  20.             // 注意下上面table[i]的索引i的计算方式：[ key的hash值 & (table.length-1) ]
  21.             // 这也是table容量必须为2的幂次的原因，读者可以自己看下当table.length为2的幂次时，(table.length-1)的二进制形式的特点 —— 全是1
  22.             // 配合这种索引计算方式可以实现key的均匀分布，减少hash冲突
  23.             if (casTabAt(tab, i, null, new Node<K, V>(hash, key, value, null))) // 插入一个链表结点
  24.                 break;
  25.         } else if ((fh = f.hash) == MOVED)                          // CASE3: 发现ForwardingNode结点，说明此时table正在扩容，则尝试协助数据迁移
  26.             tab = helpTransfer(tab, f);
  27.         else {                                                      // CASE4: 出现hash冲突,也就是table[i]桶中已经有了结点
  28.             V oldVal = null;
  29.             synchronized (f) {              // 锁住table[i]结点
  30.                 if (tabAt(tab, i) == f) {   // 再判断一下table[i]是不是第一个结点, 防止其它线程的写修改
  31.                     if (fh >= 0) {          // CASE4.1: table[i]是链表结点
  32.                         binCount = 1;
  33.                         for (Node<K, V> e = f; ; ++binCount) {
  34.                             K ek;
  35.                             // 找到“相等”的结点，判断是否需要更新value值
  36.                             if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) {
  37.                                 oldVal = e.val;
  38.                                 if (!onlyIfAbsent)
  39.                                     e.val = value;
  40.                                 break;
  41.                             }
  42.                             Node<K, V> pred = e;
  43.                             if ((e = e.next) == null) {     // “尾插法”插入新结点
  44.                                 pred.next = new Node<K, V>(hash, key,
  45.                                     value, null);
  46.                                 break;
  47.                             }
  48.                         }
  49.                     } else if (f instanceof TreeBin) {  // CASE4.2: table[i]是红黑树结点
  50.                         Node<K, V> p;
  51.                         binCount = 2;
  52.                         if ((p = ((TreeBin<K, V>) f).putTreeVal(hash, key, value)) != null) {
  53.                             oldVal = p.val;
  54.                             if (!onlyIfAbsent)
  55.                                 p.val = value;
  56.                         }
  57.                     }
  58.                 }
  59.             }
  60.             if (binCount != 0) {
  61.                 if (binCount >= TREEIFY_THRESHOLD)
  62.                     treeifyBin(tab, i);     // 链表 -> 红黑树 转换
  63.                 if (oldVal != null)         // 表明本次put操作只是替换了旧值，不用更改计数值
  64.                     return oldVal;
  65.                 break;
  66.             }
  67.         }
  68.     }
  69.     addCount(1L, binCount);             // 计数值加1
  70.     return null;
  71. }

putVal的逻辑还是很清晰的，首先根据key计算hash值，然后通过hash值与table容量进行运算，计算得到key所映射的索引——也就是对应到table中桶的位置。
这里需要注意的是计算索引的方式：i = (n - 1) & hash
n - 1 == table.length - 1，table.length 的大小必须为2的幂次的原因就在这里。
读者可以自己计算下，当table.length为2的幂次时，(table.length-1)的二进制形式的特点是除最高位外全部是1，配合这种索引计算方式可以实现key在table中的均匀分布，减少hash冲突——出现hash冲突时，结点就需要以链表或红黑树的形式链接到table[i]，这样无论是插入还是查找都需要额外的时间。

putVal方法一共处理四种情况：

1、首次初始化table —— 懒加载

之前讲构造器的时候说了，ConcurrentHashMap在构造的时候并不会初始化table数组，首次初始化就在这里通过initTable方法完成：

  1. /**
  2.  * 初始化table, 使用sizeCtl作为初始化容量.
  3.  */
  4. private final Node<K, V>[] initTable() {
  5.     Node<K, V>[] tab;
  6.     int sc;
  7.     while ((tab = table) == null || tab.length == 0) {  //自旋直到初始化成功
  8.         if ((sc = sizeCtl) < 0)         // sizeCtl<0 说明table已经正在初始化/扩容
  9.             Thread.yield();
  10.         else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {  // 将sizeCtl更新成-1,表示正在初始化中
  11.             try {
  12.                 if ((tab = table) == null || tab.length == 0) {
  13.                     int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
  14.                     Node<K, V>[] nt = (Node<K, V>[]) new Node<?, ?>[n];
  15.                     table = tab = nt;
  16.                     sc = n - (n >>> 2);     // n - (n >>> 2) = n - n/4 = 0.75n, 前面说了loadFactor已在JDK1.8废弃
  17.                 }
  18.             } finally {
  19.                 sizeCtl = sc;               // 设置threshold = 0.75 * table.length
  20.             }
  21.             break;
  22.         }
  23.     }
  24.     return tab;
  25. }

initTable方法就是将sizeCtl字段的值（ConcurrentHashMap对象在构造时设置）作为table的大小。
需要注意的是这里的n - (n >>> 2)，其实就是0.75 * n，sizeCtl 的值最终需要变更为0.75 * n，相当于设置了threshold。

2、table[i]对应的桶为空

最简单的情况，直接CAS操作占用桶table[i]即可。

3、发现ForwardingNode结点，说明此时table正在扩容，则尝试协助进行数据迁移

ForwardingNode结点是ConcurrentHashMap中的五类结点之一，相当于一个占位结点，表示当前table正在进行扩容，当前线程可以尝试协助数据迁移。

扩容和数据迁移是ConcurrentHashMap中最复杂的部分，我们会在下一章专门讨论。

4、出现hash冲突,也就是table[i]桶中已经有了结点

当两个不同key映射到同一个table[i]桶中时，就会出现这种情况：

  • 当table[i]的结点类型为Node——链表结点时，就会将新结点以“尾插法”的形式插入链表的尾部。
  • 当table[i]的结点类型为TreeBin——红黑树代理结点时，就会将新结点通过红黑树的插入方式插入。

putVal方法的最后，涉及将链表转换为红黑树 —— treeifyBin ，但实际情况并非立即就会转换，当table的容量小于64时，出于性能考虑，只是对table数组扩容1倍——tryPresize：

tryPresize方法涉及扩容和数据迁移，我们会在下一章专门讨论。

  1. /**
  2.  * 尝试进行 链表 -> 红黑树 的转换.
  3.  */
  4. private final void treeifyBin(Node<K, V>[] tab, int index) {
  5.     Node<K, V> b;
  6.     int n, sc;
  7.     if (tab != null) {
  8.         // CASE 1: table的容量 < MIN_TREEIFY_CAPACITY(64)时，直接进行table扩容，不进行红黑树转换
  9.         if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
  10.             tryPresize(n << 1);
  11.             // CASE 2: table的容量 ≥ MIN_TREEIFY_CAPACITY(64)时，进行链表 -> 红黑树的转换
  12.         else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
  13.             synchronized (b) {
  14.                 if (tabAt(tab, index) == b) {
  15.                     TreeNode<K, V> hd = null, tl = null;
  16.                     // 遍历链表，建立红黑树
  17.                     for (Node<K, V> e = b; e != null; e = e.next) {
  18.                         TreeNode<K, V> p = new TreeNode<K, V>(e.hash, e.key, e.val, null, null);
  19.                         if ((p.prev = tl) == null)
  20.                             hd = p;
  21.                         else
  22.                             tl.next = p;
  23.                         tl = p;
  24.                     }
  25.                     // 以TreeBin类型包装，并链接到table[index]中
  26.                     setTabAt(tab, index, new TreeBin<K, V>(hd));
  27.                 }
  28.             }
  29.         }
  30.     }
  31. }

ConcurrentHashMap的get操作

我们来看下ConcurrentHashMap如何根据key来查找一个元素：

  1. /**
  2.  * 根据key查找对应的value值
  3.  *
  4.  * @return 查找不到则返回null
  5.  * @throws NullPointerException if the specified key is null
  6.  */
  7. public V get(Object key) {
  8.     Node<K, V>[] tab;
  9.     Node<K, V> e, p;
  10.     int n, eh;
  11.     K ek;
  12.     int h = spread(key.hashCode());     // 重新计算key的hash值
  13.     if ((tab = table) != null && (n = tab.length) > 0 &&
  14.             (e = tabAt(tab, (n - 1) & h)) != null) {
  15.         if ((eh = e.hash) == h) {       // table[i]就是待查找的项，直接返回
  16.             if ((ek = e.key) == key || (ek != null && key.equals(ek)))
  17.                 return e.val;
  18.         } else if (eh < 0)              // hash值<0, 说明遇到特殊结点(非链表结点), 调用find方法查找
  19.             return (p = e.find(h, key)) != null ? p.val : null;
  20.         while ((e = e.next) != null) {  // 按链表方式查找
  21.             if (e.hash == h &&
  22.                     ((ek = e.key) == key || (ek != null && key.equals(ek))))
  23.                 return e.val;
  24.         }
  25.     }
  26.     return null;
  27. }

get方法的逻辑很简单，首先根据key的hash值计算映射到table的哪个桶——table[i]。

  1. 如果table[i]的key和待查找key相同，那直接返回；
  2. 如果table[i]对应的结点是特殊结点（hash值小于0），则通过**find**方法查找；
  3. 如果table[i]对应的结点是普通链表结点，则按链表方式查找。

关键是第二种情况，不同结点的find查找方式有所不同，我们来具体看下：

Node结点的查找

当槽table[i]被普通Node结点占用，说明是链表链接的形式，直接从链表头开始查找：

  1. /**
  2.  * 链表查找.
  3.  */
  4. Node<K, V> find(int h, Object k) {
  5.     Node<K, V> e = this;
  6.     if (k != null) {
  7.         do {
  8.             K ek;
  9.             if (e.hash == h && ((ek = e.key) == k || (ek != null && k.equals(ek))))
  10.                 return e;
  11.         } while ((e = e.next) != null);
  12.     }
  13.     return null;
  14. }

TreeBin结点的查找

TreeBin的查找比较特殊，我们知道当槽table[i]被TreeBin结点占用时，说明链接的是一棵红黑树。由于红黑树的插入、删除会涉及整个结构的调整，所以通常存在读写并发操作的时候，是需要加锁的。

ConcurrentHashMap采用了一种类似读写锁的方式：当线程持有写锁（修改红黑树）时，如果读线程需要查找，不会像传统的读写锁那样阻塞等待，而是转而以链表的形式进行查找（TreeBin本身时Node类型的子类，所有拥有Node的所有字段）

  1. /**
  2.  * 从根结点开始遍历查找，找到“相等”的结点就返回它，没找到就返回null
  3.  * 当存在写锁时，以链表方式进行查找
  4.  */
  5. final Node<K, V> find(int h, Object k) {
  6.     if (k != null) {
  7.         for (Node<K, V> e = first; e != null; ) {
  8.             int s;
  9.             K ek;
  10.             /**
  11.              * 两种特殊情况下以链表的方式进行查找:
  12.              * 1. 有线程正持有写锁，这样做能够不阻塞读线程
  13.              * 2. 有线程等待获取写锁，不再继续加读锁，相当于“写优先”模式
  14.              */
  15.             if (((s = lockState) & (WAITER | WRITER)) != 0) {
  16.                 if (e.hash == h &&
  17.                     ((ek = e.key) == k || (ek != null && k.equals(ek))))
  18.                     return e;
  19.                 e = e.next;     // 链表形式
  20.             }
  21.             // 读线程数量加1，读状态进行累加
  22.             else if (U.compareAndSwapInt(this, LOCKSTATE, s, s + READER)) {
  23.                 TreeNode<K, V> r, p;
  24.                 try {
  25.                     p = ((r = root) == null ? null :
  26.                         r.findTreeNode(h, k, null));
  27.                 } finally {
  28.                     Thread w;
  29.                     // 如果当前线程是最后一个读线程，且有写线程因为读锁而阻塞，则写线程，告诉它可以尝试获取写锁了
  30.                     if (U.getAndAddInt(this, LOCKSTATE, -READER) == (READER | WAITER) && (w = waiter) != null)
  31.                         LockSupport.unpark(w);
  32.                 }
  33.                 return p;
  34.             }
  35.         }
  36.     }
  37.     return null;
  38. }

ForwardingNode结点的查找

ForwardingNode是一种临时结点，在扩容进行中才会出现，所以查找也在扩容的table上进行：

  1. /**
  2.  * 在新的扩容table——nextTable上进行查找
  3.  */
  4. Node<K, V> find(int h, Object k) {
  5.     // loop to avoid arbitrarily deep recursion on forwarding nodes
  6.     outer:
  7.     for (Node<K, V>[] tab = nextTable; ; ) {
  8.         Node<K, V> e;
  9.         int n;
  10.         if (k == null || tab == null || (n = tab.length) == 0 ||
  11.             (e = tabAt(tab, (n - 1) & h)) == null)
  12.             return null;
  13.         for (; ; ) {
  14.             int eh;
  15.             K ek;
  16.             if ((eh = e.hash) == h &&
  17.                 ((ek = e.key) == k || (ek != null && k.equals(ek))))
  18.                 return e;
  19.             if (eh < 0) {
  20.                 if (e instanceof ForwardingNode) {
  21.                     tab = ((ForwardingNode<K, V>) e).nextTable;
  22.                     continue outer;
  23.                 } else
  24.                     return e.find(h, k);
  25.             }
  26.             if ((e = e.next) == null)
  27.                 return null;
  28.         }
  29.     }
  30. }

ReservationNode结点的查找

ReservationNode是保留结点，不保存实际数据，所以直接返回null：

  1. Node<K, V> find(int h, Object k) {
  2.     return null;
  3. }

ConcurrentHashMap的计数

计数原理

我们来看下ConcurrentHashMap是如何计算键值对的数目的：

  1. public int size() {
  2.     long n = sumCount();
  3.     return ((n < 0L) ? 0 :
  4.             (n > (long) Integer.MAX_VALUE) ? Integer.MAX_VALUE :
  5.                     (int) n);
  6. }

size方法内部实际调用了sumCount方法：

  1. final long sumCount() {
  2.     CounterCell[] as = counterCells;
  3.     CounterCell a;
  4.     long sum = baseCount;
  5.     if (as != null) {
  6.         for (int i = 0; i < as.length; ++i) {
  7.             if ((a = as[i]) != null)
  8.                 sum += a.value;
  9.         }
  10.     }
  11.     return sum;
  12. }

可以看到，最终键值对的数目其实是通过下面这个公式计算的：

sum=baseCount+∑i=0nCounterCell[i]
如果读者看过我之前的博文——LongAdder，这时应该已经猜到ConcurrentHashMap的计数思路了。
没错，ConcurrentHashMap的计数其实延用了LongAdder分段计数的思路，只不过ConcurrentHashMap并没有在内部直接使用LongAdder，而是差不多copy了一份和LongAdder类似的代码：

  1. /**
  2.  * 计数基值,当没有线程竞争时，计数将加到该变量上。类似于LongAdder的base变量
  3.  */
  4. private transient volatile long baseCount;
  5. /**
  6.  * 计数数组，出现并发冲突时使用。类似于LongAdder的cells数组
  7.  */
  8. private transient volatile CounterCell[] counterCells;
  9. /**
  10.  * 自旋标识位，用于CounterCell[]扩容时使用。类似于LongAdder的cellsBusy变量
  11.  */
  12. private transient volatile int cellsBusy;

我们来看下CounterCell这个槽对象——出现并发冲突时，每个线程会根据自己的hash值找到对应的槽位置：

  1. /**
  2.  * 计数槽.
  3.  * 类似于LongAdder中的Cell内部类
  4.  */
  5. static final class CounterCell {
  6.     volatile long value;
  7.     CounterCell(long x) {
  8.         value = x;
  9.     }
  10. }

addCount的实现

回顾之前的putval方法的最后，当插入一对键值对后，通过addCount方法将计数值为加1：

  1. /**
  2.  * 实际的插入操作
  3.  *
  4.  * @param onlyIfAbsent true:仅当key不存在时,才插入
  5.  */
  6. final V putVal(K key, V value, boolean onlyIfAbsent) {
  7.     // …
  8.     addCount(1L, binCount);             // 计数值加1
  9.     return null;
  10. }

我们来看下addCount的具体实现（后半部分涉及扩容，暂且不看）：
首先，如果counterCells为null，说明之前一直没有出现过冲突，直接将值累加到baseCount上；
否则，尝试更新counterCells[i]中的值，更新成功就退出。失败说明槽中也出现了并发冲突，可能涉及槽数组——counterCells的扩容，所以调用fullAddCount方法。

fullAddCount的逻辑和LongAdder中的longAccumulate几乎完全一样，这里不再赘述，读者可以参考：Java多线程进阶（十七）—— J.U.C之atomic框架：LongAdder

  1. /**
  2.  * 更改计数值
  3.  */
  4. private final void addCount(long x, int check) {
  5.     CounterCell[] as;
  6.     long b, s;
  7.     if ((as = counterCells) != null ||
  8.             !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) { // 首先尝试更新baseCount
  10.         // 更新失败,说明出现并发冲突,则将计数值累加到Cell槽
  11.         CounterCell a;
  12.         long v;
  13.         int m;
  14.         boolean uncontended = true;
  15.         if (as == null || (m = as.length - 1) < 0 ||
  16.                 (a = as[ThreadLocalRandom.getProbe() & m]) == null ||   // 根据线程hash值计算槽索引
  17.                 !(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
  18.             fullAddCount(x, uncontended);       // 槽更新也失败, 则会执行fullAddCount
  19.             return;
  20.         }
  21.         if (check <= 1)
  22.             return;
  23.         s = sumCount();
  24.     }