和HashMap类似，ConcurrentHashMap使用了一个table来存储Node，ConcurrentHashMap同样使用记录的key的hashCode来寻找记录的存储index，而处理哈希冲突的方式与HashMap也是类似的，冲突的记录将被存储在同一个位置上，形成一条链表，当链表的长度大于8的时候会将链表转化为一棵红黑树，从而将查找的复杂度从O(N)降到了O(lgN)。下文中将详细分析ConcurrentHashMap的实现，以及ConcurrentHashMap是如何保证在并发环境下的线程安全的。

1、重要的属性

sizeCtl，是使用的最多的一个属性，

  • 负数代表正在进行初始化或扩容操作，
  • -1代表正在初始化，
  • -N表示有N-1个线程在进行扩容操作

  • 正数或0代表hash表还没被初始化，表示初始化或下次扩容的大小，起到阈值的概念 ```java

    1.   /**
    • 盛装Node元素的数组 它的大小是2的整数次幂

    • Size is always a power of two. Accessed directly by iterators. */ transient volatile Node[] table;

      /**

    • Table initialization and resizing control. When negative, the
    • table is being initialized or resized: -1 for initialization,
    • else -(1 + the number of active resizing threads). Otherwise,
    • when table is null, holds the initial table size to use upon
    • creation, or 0 for default. After initialization, holds the

    • next element count value upon which to resize the table. hash表初始化或扩容时的一个控制位标识量。 负数代表正在进行初始化或扩容操作 -1代表正在初始化 -N 表示有N-1个线程正在进行扩容操作 正数或0代表hash表还没有被初始化，这个数值表示初始化或下一次进行扩容的大小

      / private transient volatile int sizeCtl; // 以下两个是用来控制扩容的时候 单线程进入的变量 /*

    • The number of bits used for generation stamp in sizeCtl.
    • Must be at least 6 for 32bit arrays. / private static int RESIZE_STAMP_BITS = 16; /*
    • The bit shift for recording size stamp in sizeCtl. */ private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
  1. /*
  2.  * Encodings for Node hash fields. See above for explanation.
  3.  */
  4. static final int MOVED     = -1; // hash值是-1，表示这是一个forwardNode节点
  5. static final int TREEBIN   = -2; // hash值是-2  表示这时一个TreeBin节点
  1. <a name="sk99ku"></a>
  2. # 2、重要的内部类
  3. <a name="vni5xu"></a>
  4. ## 2.1、node
  5. node是最核心的内部类，包装了key-value键值对，所有插入的值都存在了这里，但是value和next用了volatile修饰，保证线程可见，不允许调用setValue方法，提供了find方法
  6. ```java
  7.  static class Node<K,V> implements Map.Entry<K,V> {
  8.         final int hash;
  9.         final K key;
  10.         volatile V val;//带有同步锁的value
  11.         volatile Node<K,V> next;//带有同步锁的next指针
  13.         Node(int hash, K key, V val, Node<K,V> next) {
  14.             this.hash = hash;
  15.             this.key = key;
  16.             this.val = val;
  17.             this.next = next;
  18.         }
  20.         public final K getKey()       { return key; }
  21.         public final V getValue()     { return val; }
  22.         public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
  23.         public final String toString(){ return key + "=" + val; }
  24.         //不允许直接改变value的值
  25.         public final V setValue(V value) {
  26.             throw new UnsupportedOperationException();
  27.         }
  29.         public final boolean equals(Object o) {
  30.             Object k, v, u; Map.Entry<?,?> e;
  31.             return ((o instanceof Map.Entry) &&
  32.                     (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
  33.                     (v = e.getValue()) != null &&
  34.                     (k == key || k.equals(key)) &&
  35.                     (v == (u = val) || v.equals(u)));
  36.         }
  38.         /**
  39.          * Virtualized support for map.get(); overridden in subclasses.
  40.          */
  41.         Node<K,V> find(int h, Object k) {
  42.             Node<K,V> e = this;
  43.             if (k != null) {
  44.                 do {
  45.                     K ek;
  46.                     if (e.hash == h &&
  47.                         ((ek = e.key) == k || (ek != null && k.equals(ek))))
  48.                         return e;
  49.                 } while ((e = e.next) != null);
  50.             }
  51.             return null;
  52.         }
  53.     }

2.2、TreeNode

树节点类，当链表长度过长的时候，会转换成TreeNode，于HashMap不同的是，它并不是直接转换为红黑树，而是把这些节点包装成TreeNode放在TreeBin对象中，由TreeBin完成对红黑树的包装，TreeNode带有next指针，方便基于TreeBin的访问。

  1. /* ---------------- TreeNodes -------------- */
  3.     /**
  4.      * Nodes for use in TreeBins
  5.      */
  6.     static final class TreeNode<K,V> extends Node<K,V> {
  7.         TreeNode<K,V> parent;  // red-black tree links
  8.         TreeNode<K,V> left;
  9.         TreeNode<K,V> right;
  10.         TreeNode<K,V> prev;    // needed to unlink next upon deletion
  11.         boolean red;
  13.         TreeNode(int hash, K key, V val, Node<K,V> next,
  14.                  TreeNode<K,V> parent) {
  15.             super(hash, key, val, next);
  16.             this.parent = parent;
  17.         }
  19.         Node<K,V> find(int h, Object k) {
  20.             return findTreeNode(h, k, null);
  21.         }
  23.         /**
  24.          * Returns the TreeNode (or null if not found) for the given key
  25.          * starting at given root.
  26.          */
  27.         final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
  28.             if (k != null) {
  29.                 TreeNode<K,V> p = this;
  30.                 do  {
  31.                     int ph, dir; K pk; 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.     }

2.3、TreeBin

这个类包装了TreeNode节点来进行操作，还带有读写锁，构造方法中使用了TREEBIN常量作为hash值，标识节点类型

2.4、ForwardingNode

一个用于连接两个table的节点类，包含一个nextTable指针，指向下一张表，而这个节点的key value next指针全为null，hash值为-1，这里的find方法是从nextTable里进行查找，而不是以自身为头结点进行查找。

  1. /**
  2.      * A node inserted at head of bins during transfer operations.
  3.      */
  4.     static final class ForwardingNode<K,V> extends Node<K,V> {
  5.         final Node<K,V>[] nextTable;
  6.         ForwardingNode(Node<K,V>[] tab) {
  7.             super(MOVED, null, null, null);
  8.             this.nextTable = tab;
  9.         }
  11.         Node<K,V> find(int h, Object k) {
  12.             // loop to avoid arbitrarily deep recursion on forwarding nodes
  13.             outer: for (Node<K,V>[] tab = nextTable;;) {
  14.                 Node<K,V> e; int n;
  15.                 if (k == null || tab == null || (n = tab.length) == 0 ||
  16.                     (e = tabAt(tab, (n - 1) & h)) == null)
  17.                     return null;
  18.                 for (;;) {
  19.                     int eh; K ek;
  20.                     if ((eh = e.hash) == h &&
  21.                         ((ek = e.key) == k || (ek != null && k.equals(ek))))
  22.                         return e;
  23.                     if (eh < 0) {
  24.                         if (e instanceof ForwardingNode) {
  25.                             tab = ((ForwardingNode<K,V>)e).nextTable;
  26.                             continue outer;
  27.                         }
  28.                         else
  29.                             return e.find(h, k);
  30.                     }
  31.                     if ((e = e.next) == null)
  32.                         return null;
  33.                 }
  34.             }
  35.         }
  36.     }

3、Unsafe于CAS

内部随处可见U 也就是Unsafe，是一个本地类，实现了一系列的原子方法，利用CAS算法实现无锁化的修改操作，大大降低锁的性能消耗，CAS就是不断去比较当前值是否是你指定的值，如果是就接受并修改成功，如果不是修改失败，返回false

3.1、unsafe静态块

  1.  private static final sun.misc.Unsafe U;
  2.     private static final long SIZECTL;
  3.     private static final long TRANSFERINDEX;
  4.     private static final long BASECOUNT;
  5.     private static final long CELLSBUSY;
  6.     private static final long CELLVALUE;
  7.     private static final long ABASE;
  8.     private static final int ASHIFT;
  10.     static {
  11.         try {
  12.             U = sun.misc.Unsafe.getUnsafe();
  13.             Class<?> k = ConcurrentHashMap.class;
  14.             SIZECTL = U.objectFieldOffset
  15.                 (k.getDeclaredField("sizeCtl"));
  16.             TRANSFERINDEX = U.objectFieldOffset
  17.                 (k.getDeclaredField("transferIndex"));
  18.             BASECOUNT = U.objectFieldOffset
  19.                 (k.getDeclaredField("baseCount"));
  20.             CELLSBUSY = U.objectFieldOffset
  21.                 (k.getDeclaredField("cellsBusy"));
  22.             Class<?> ck = CounterCell.class;
  23.             CELLVALUE = U.objectFieldOffset
  24.                 (ck.getDeclaredField("value"));
  25.             Class<?> ak = Node[].class;
  26.             ABASE = U.arrayBaseOffset(ak);
  27.             int scale = U.arrayIndexScale(ak);
  28.             if ((scale & (scale - 1)) != 0)
  29.                 throw new Error("data type scale not a power of two");
  30.             ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
  31.         } catch (Exception e) {
  32.             throw new Error(e);
  33.         }
  34.     }

3.2、三个核心方法

定义了三个原子操作，用于对指定位置节点进行操作

  1.  @SuppressWarnings("unchecked")
  2.     //获得在i位置上的Node节点
  3.     static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
  4.         return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
  5.     }
  6.     //利用CAS算法设置i位置上的Node节点。之所以能实现并发是因为他指定了原来这个节点的值是多少
  7.     //在CAS算法中，会比较内存中的值与你指定的这个值是否相等，如果相等才接受你的修改，否则拒绝你的修改
  8.     //因此当前线程中的值并不是最新的值，这种修改可能会覆盖掉其他线程的修改结果  有点类似于SVN
  9.     static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
  10.                                         Node<K,V> c, Node<K,V> v) {
  11.         return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
  12.     }
  13.     //利用volatile方法设置节点位置的值
  14.     static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
  15.         U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
  16.     }

4、初始化方法initTable

对应ConcurrentHashMap来说，调用构造方法只是设置了一些参数，真正初始化是在插入元素的时候发生的，比如put，computeIfAbsent，compute，merge等方法的时候，通过table == null判断，使用sizeCtl属性判断，如果值小于0，表示正在初始化，交出CPU，只能由一个线程进行初始化，如果获得了初始化权限，通过CAS将sizeCtl置为-1获得，防止其他线程进入

  1.     /**
  2.      * Initializes table, using the size recorded in sizeCtl.
  3.      */
  4.     private final Node<K,V>[] initTable() {
  5.         Node<K,V>[] tab; int sc;
  6.         while ((tab = table) == null || tab.length == 0) {
  7.                 //sizeCtl表示有其他线程正在进行初始化操作，把线程挂起。对于table的初始化工作，只能有一个线程在进行。
  8.             if ((sc = sizeCtl) < 0)
  9.                 Thread.yield(); // lost initialization race; just spin
  10.             else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {//利用CAS方法把sizectl的值置为-1 表示本线程正在进行初始化
  11.                 try {
  12.                     if ((tab = table) == null || tab.length == 0) {
  13.                         int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
  14.                         @SuppressWarnings("unchecked")
  15.                         Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
  16.                         table = tab = nt;
  17.                         sc = n - (n >>> 2);//相当于0.75*n 设置一个扩容的阈值
  18.                     }
  19.                 } finally {
  20.                     sizeCtl = sc;
  21.                 }
  22.                 break;
  23.             }
  24.         }
  25.         return tab;
  26.     }

5、扩容方法transfer

容量不足的时候，需要对table进行扩容，整个扩容分为两部分

  • 构建nextTable，容量为原来的两倍，单线程进行操作，通过RESIZE_STAMP_SHIFT变量来保证
  • 将原来table中的元素复制到nextTable中，允许多线程操作单线程大体思想就是遍历、复制的过程，首先根据运算得到要遍历的次数i,然后利用tabAt方法获得i位置的元素：
  • 如果这个位置为空，就在原table中的i位置放入forwardNode节点，这里是支持并发扩容的关键
  • 如果这个位置是Node节点（fn>=0），如果是链表的头结点，就构造一个反序链表，把他们分别放在nextTable的i和i+n的位置
  • 如果是TreeBin节点，也做一个反序处理并判断是否需要untreeify，并把处理结果分别放在nextTable的i和i+1的位置上

  • 遍历过所有的节点以后就可以完成复制工作，这时让nextTable作为新的table，并更新sizeCtl的值为原来的0.75倍

    1. /**
    2.    * 一个过渡的table表  只有在扩容的时候才会使用
    3.    */
    4.   private transient volatile Node<K,V>[] nextTable;
    6. /**
    7.    * Moves and/or copies the nodes in each bin to new table. See
    8.    * above for explanation.
    9.    */
    10.   private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    11.       int n = tab.length, stride;
    12.       if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
    13.           stride = MIN_TRANSFER_STRIDE; // subdivide range
    14.       if (nextTab == null) {            // initiating
    15.           try {
    16.               @SuppressWarnings("unchecked")
    17.               //构造一个nextTable对象 它的容量是原来的两倍
    18.               Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
    19.               nextTab = nt;
    20.           } catch (Throwable ex) {      // try to cope with OOME
    21.               sizeCtl = Integer.MAX_VALUE;
    22.               return;
    23.           }
    24.           nextTable = nextTab;
    25.           transferIndex = n;
    26.       }
    27.       int nextn = nextTab.length;
    28.       //构造一个连节点指针 用于标志位
    29.       ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
    30.       //并发扩容的关键属性 如果等于true 说明这个节点已经处理过
    31.       boolean advance = true;
    32.       boolean finishing = false; 
    33.       // to ensure sweep before committing nextTab
    34.       for (int i = 0, bound = 0;;) {
    35.           Node<K,V> f; int fh;
    36.           //这个while循环体的作用就是在控制i--  通过i--可以依次遍历原hash表中的节点
    37.           while (advance) {
    38.               int nextIndex, nextBound;
    39.               if (--i >= bound || finishing)
    40.                   advance = false;
    41.               else if ((nextIndex = transferIndex) <= 0) {
    42.                   i = -1;
    43.                   advance = false;
    44.               }
    45.               else if (U.compareAndSwapInt
    46.                        (this, TRANSFERINDEX, nextIndex,
    47.                         nextBound = (nextIndex > stride ?
    48.                                      nextIndex - stride : 0))) {
    49.                   bound = nextBound;
    50.                   i = nextIndex - 1;
    51.                   advance = false;
    52.               }
    53.           }
    54.           if (i < 0 || i >= n || i + n >= nextn) {
    55.               int sc;
    56.               if (finishing) {
    57.                   //如果所有的节点都已经完成复制工作  就把nextTable赋值给table 清空临时对象nextTable
    58.                   nextTable = null;
    59.                   table = nextTab;
    60.                   //扩容阈值设置为原来容量的1.5倍  依然相当于现在容量的0.75倍
    61.                   sizeCtl = (n << 1) - (n >>> 1);
    62.                   return;
    63.               }
    64.               //利用CAS方法更新这个扩容阈值，在这里面sizectl值减一，说明新加入一个线程参与到扩容操作
    65.               if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
    66.                   if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
    67.                       return;
    68.                   finishing = advance = true;
    69.                   i = n; // recheck before commit
    70.               }
    71.           }
    72.           //如果遍历到的节点为空 则放入ForwardingNode指针
    73.           else if ((f = tabAt(tab, i)) == null)
    74.               advance = casTabAt(tab, i, null, fwd);
    75.           //如果遍历到ForwardingNode节点  说明这个点已经被处理过了 直接跳过  这里是控制并发扩容的核心
    76.           else if ((fh = f.hash) == MOVED)
    77.               advance = true; // already processed
    78.           else {
    79.                   //节点上锁
    80.               synchronized (f) {
    81.                   if (tabAt(tab, i) == f) {
    82.                       Node<K,V> ln, hn;
    83.                       //如果fh>=0 证明这是一个Node节点
    84.                       if (fh >= 0) {
    85.                           int runBit = fh & n;
    86.                           //以下的部分在完成的工作是构造两个链表  一个是原链表  另一个是原链表的反序排列
    87.                           Node<K,V> lastRun = f;
    88.                           for (Node<K,V> p = f.next; p != null; p = p.next) {
    89.                               int b = p.hash & n;
    90.                               if (b != runBit) {
    91.                                   runBit = b;
    92.                                   lastRun = p;
    93.                               }
    94.                           }
    95.                           if (runBit == 0) {
    96.                               ln = lastRun;
    97.                               hn = null;
    98.                           }
    99.                           else {
    100.                               hn = lastRun;
    101.                               ln = null;
    102.                           }
    103.                           for (Node<K,V> p = f; p != lastRun; p = p.next) {
    104.                               int ph = p.hash; K pk = p.key; V pv = p.val;
    105.                               if ((ph & n) == 0)
    106.                                   ln = new Node<K,V>(ph, pk, pv, ln);
    107.                               else
    108.                                   hn = new Node<K,V>(ph, pk, pv, hn);
    109.                           }
    110.                           //在nextTable的i位置上插入一个链表
    111.                           setTabAt(nextTab, i, ln);
    112.                           //在nextTable的i+n的位置上插入另一个链表
    113.                           setTabAt(nextTab, i + n, hn);
    114.                           //在table的i位置上插入forwardNode节点  表示已经处理过该节点
    115.                           setTabAt(tab, i, fwd);
    116.                           //设置advance为true 返回到上面的while循环中 就可以执行i--操作
    117.                           advance = true;
    118.                       }
    119.                       //对TreeBin对象进行处理  与上面的过程类似
    120.                       else if (f instanceof TreeBin) {
    121.                           TreeBin<K,V> t = (TreeBin<K,V>)f;
    122.                           TreeNode<K,V> lo = null, loTail = null;
    123.                           TreeNode<K,V> hi = null, hiTail = null;
    124.                           int lc = 0, hc = 0;
    125.                           //构造正序和反序两个链表
    126.                           for (Node<K,V> e = t.first; e != null; e = e.next) {
    127.                               int h = e.hash;
    128.                               TreeNode<K,V> p = new TreeNode<K,V>
    129.                                   (h, e.key, e.val, null, null);
    130.                               if ((h & n) == 0) {
    131.                                   if ((p.prev = loTail) == null)
    132.                                       lo = p;
    133.                                   else
    134.                                       loTail.next = p;
    135.                                   loTail = p;
    136.                                   ++lc;
    137.                               }
    138.                               else {
    139.                                   if ((p.prev = hiTail) == null)
    140.                                       hi = p;
    141.                                   else
    142.                                       hiTail.next = p;
    143.                                   hiTail = p;
    144.                                   ++hc;
    145.                               }
    146.                           }
    147.                           //如果扩容后已经不再需要tree的结构 反向转换为链表结构
    148.                           ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
    149.                               (hc != 0) ? new TreeBin<K,V>(lo) : t;
    150.                           hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
    151.                               (lc != 0) ? new TreeBin<K,V>(hi) : t;
    152.                            //在nextTable的i位置上插入一个链表    
    153.                           setTabAt(nextTab, i, ln);
    154.                           //在nextTable的i+n的位置上插入另一个链表
    155.                           setTabAt(nextTab, i + n, hn);
    156.                            //在table的i位置上插入forwardNode节点  表示已经处理过该节点
    157.                           setTabAt(tab, i, fwd);
    158.                           //设置advance为true 返回到上面的while循环中 就可以执行i--操作
    159.                           advance = true;
    160.                       }
    161.                   }
    162.               }
    163.           }
    164.       }
    165.   }

6、put 方法

根据hash值计算新值的位置i，如果i位置为空，就直接放进去，否则进行判断，是树节点就按照树的方式插入新值，如果是链表就插入到链表的尾部

  1. 如果有线程在进行扩容操作，当前线程也要进入扩容操作
  2. 如果检测到要插入的节点非空且不是forward节点，就加锁进行添加操作。

如果这个位置存在结点，说明发生了hash碰撞，首先判断这个节点的类型。如果是链表节点（fh>0）,则得到的结点就是hash值相同的节点组成的链表的头节点。需要依次向后遍历确定这个新加入的值所在位置。如果遇到hash值与key值都与新加入节点是一致的情况，则只需要更新value值即可。否则依次向后遍历，直到链表尾插入这个结点。 如果加入这个节点以后链表长度大于8，就把这个链表转换成红黑树。如果这个节点的类型已经是树节点的话，直接调用树节点的插入方法进行插入新的值。

  1. public V put(K key, V value) {
  2.         return putVal(key, value, false);
  3.     }
  5.     /** Implementation for put and putIfAbsent */
  6.     final V putVal(K key, V value, boolean onlyIfAbsent) {
  7.             //不允许 key或value为null
  8.         if (key == null || value == null) throw new NullPointerException();
  9.         //计算hash值
  10.         int hash = spread(key.hashCode());
  11.         int binCount = 0;
  12.         //死循环 何时插入成功 何时跳出
  13.         for (Node<K,V>[] tab = table;;) {
  14.             Node<K,V> f; int n, i, fh;
  15.             //如果table为空的话，初始化table
  16.             if (tab == null || (n = tab.length) == 0)
  17.                 tab = initTable();
  18.             //根据hash值计算出在table里面的位置 
  19.             else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
  20.                 //如果这个位置没有值 ，直接放进去，不需要加锁
  21.                 if (casTabAt(tab, i, null,
  22.                              new Node<K,V>(hash, key, value, null)))
  23.                     break;                   // no lock when adding to empty bin
  24.             }
  25.             //当遇到表连接点时，需要进行整合表的操作
  26.             else if ((fh = f.hash) == MOVED)
  27.                 tab = helpTransfer(tab, f);
  28.             else {
  29.                 V oldVal = null;
  30.                 //结点上锁  这里的结点可以理解为hash值相同组成的链表的头结点
  31.                 synchronized (f) {
  32.                     if (tabAt(tab, i) == f) {
  33.                         //fh〉0 说明这个节点是一个链表的节点 不是树的节点
  34.                         if (fh >= 0) {
  35.                             binCount = 1;
  36.                             //在这里遍历链表所有的结点
  37.                             for (Node<K,V> e = f;; ++binCount) {
  38.                                 K ek;
  39.                                 //如果hash值和key值相同  则修改对应结点的value值
  40.                                 if (e.hash == hash &&
  41.                                     ((ek = e.key) == key ||
  42.                                      (ek != null && key.equals(ek)))) {
  43.                                     oldVal = e.val;
  44.                                     if (!onlyIfAbsent)
  45.                                         e.val = value;
  46.                                     break;
  47.                                 }
  48.                                 Node<K,V> pred = e;
  49.                                 //如果遍历到了最后一个结点，那么就证明新的节点需要插入 就把它插入在链表尾部
  50.                                 if ((e = e.next) == null) {
  51.                                     pred.next = new Node<K,V>(hash, key,
  52.                                                               value, null);
  53.                                     break;
  54.                                 }
  55.                             }
  56.                         }
  57.                         //如果这个节点是树节点，就按照树的方式插入值
  58.                         else if (f instanceof TreeBin) {
  59.                             Node<K,V> p;
  60.                             binCount = 2;
  61.                             if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
  62.                                                            value)) != null) {
  63.                                 oldVal = p.val;
  64.                                 if (!onlyIfAbsent)
  65.                                     p.val = value;
  66.                             }
  67.                         }
  68.                     }
  69.                 }
  70.                 if (binCount != 0) {
  71.                     //如果链表长度已经达到临界值8 就需要把链表转换为树结构
  72.                     if (binCount >= TREEIFY_THRESHOLD)
  73.                         treeifyBin(tab, i);
  74.                     if (oldVal != null)
  75.                         return oldVal;
  76.                     break;
  77.                 }
  78.             }
  79.         }
  80.         //将当前ConcurrentHashMap的元素数量+1
  81.         addCount(1L, binCount);
  82.         return null;
  83.     }

6.1、helpTransfer方法

这是一个协助扩容的方法，被调用的时候一定有nextTable，首先拿到nextTable，调用transfer方法

  1.  /**
  2.      * Helps transfer if a resize is in progress.
  3.      */
  4.     final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
  5.         Node<K,V>[] nextTab; int sc;
  6.         if (tab != null && (f instanceof ForwardingNode) &&
  7.             (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
  8.             int rs = resizeStamp(tab.length);//计算一个操作校验码
  9.             while (nextTab == nextTable && table == tab &&
  10.                    (sc = sizeCtl) < 0) {
  11.                 if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
  12.                     sc == rs + MAX_RESIZERS || transferIndex <= 0)
  13.                     break;
  14.                 if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
  15.                     transfer(tab, nextTab);
  16.                     break;
  17.                 }
  18.             }
  19.             return nextTab;
  20.         }
  21.         return table;
  22.     }

6.2、treeifyBin方法

这个方法是将过长的链表转换为TreeBin对象，不是直接转换，先进行容量判断，没达到就进行扩容操作，满足条件后才将链表转换为TreeBin

  1. private final void treeifyBin(Node<K,V>[] tab, int index) {
  2.         Node<K,V> b; int n, sc;
  3.         if (tab != null) {
  4.             if ((n = tab.length) < MIN_TREEIFY_CAPACITY)//如果table.length<64 就扩大一倍 返回
  5.                 tryPresize(n << 1);
  6.             else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
  7.                 synchronized (b) {
  8.                     if (tabAt(tab, index) == b) {
  9.                         TreeNode<K,V> hd = null, tl = null;
  10.                         //构造了一个TreeBin对象 把所有Node节点包装成TreeNode放进去
  11.                         for (Node<K,V> e = b; e != null; e = e.next) {
  12.                             TreeNode<K,V> p =
  13.                                 new TreeNode<K,V>(e.hash, e.key, e.val,
  14.                                                   null, null);//这里只是利用了TreeNode封装 而没有利用TreeNode的next域和parent域
  15.                             if ((p.prev = tl) == null)
  16.                                 hd = p;
  17.                             else
  18.                                 tl.next = p;
  19.                             tl = p;
  20.                         }
  21.                         //在原来index的位置 用TreeBin替换掉原来的Node对象
  22.                         setTabAt(tab, index, new TreeBin<K,V>(hd));
  23.                     }
  24.                 }
  25.             }
  26.         }
  27.     }

7、get方法

get方法比较简单，给定一个key确定value的时候，必须满足hash和key都相同，查找可能是链表或者树上。

  1. public V get(Object key) {
  2.         Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
  3.         //计算hash值
  4.         int h = spread(key.hashCode());
  5.         //根据hash值确定节点位置
  6.         if ((tab = table) != null && (n = tab.length) > 0 &&
  7.             (e = tabAt(tab, (n - 1) & h)) != null) {
  8.             //如果搜索到的节点key与传入的key相同且不为null,直接返回这个节点    
  9.             if ((eh = e.hash) == h) {
  10.                 if ((ek = e.key) == key || (ek != null && key.equals(ek)))
  11.                     return e.val;
  12.             }
  13.             //如果eh<0 说明这个节点在树上 直接寻找
  14.             else if (eh < 0)
  15.                 return (p = e.find(h, key)) != null ? p.val : null;
  16.              //否则遍历链表 找到对应的值并返回
  17.             while ((e = e.next) != null) {
  18.                 if (e.hash == h &&
  19.                     ((ek = e.key) == key || (ek != null && key.equals(ek))))
  20.                     return e.val;
  21.             }
  22.         }
  23.         return null;
  24.     }

8、size相关方法

size值不一定准确，但也经过了计算

8.1、辅助定义

为了统计元素个数，定义了一些变量和一个内部类

  1. /**
  2.      * A padded cell for distributing counts.  Adapted from LongAdder
  3.      * and Striped64.  See their internal docs for explanation.
  4.      */
  5.     @sun.misc.Contended static final class CounterCell {
  6.         volatile long value;
  7.         CounterCell(long x) { value = x; }
  8.     }
  10.   /******************************************/  
  12.     /**
  13.      * 实际上保存的是hashmap中的元素个数  利用CAS锁进行更新
  14.      但它并不用返回当前hashmap的元素个数 
  16.      */
  17.     private transient volatile long baseCount;
  18.     /**
  19.      * Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
  20.      */
  21.     private transient volatile int cellsBusy;
  23.     /**
  24.      * Table of counter cells. When non-null, size is a power of 2.
  25.      */
  26.     private transient volatile CounterCell[] counterCells;

8.2、mappingCount与size方法

从代码来看，mappingCount方法比size方法更准确，都用到了sumCount方法进行统计，由于没有进行加锁，可能会因为并发问题出现一些误差，因为size方法返回的是int类型，所以如果数量超过int最大值的情况下，还是使用mappingCount方法。

  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.     }
  7.      /**
  8.      * Returns the number of mappings. This method should be used
  9.      * instead of {@link #size} because a ConcurrentHashMap may
  10.      * contain more mappings than can be represented as an int. The
  11.      * value returned is an estimate; the actual count may differ if
  12.      * there are concurrent insertions or removals.
  13.      *
  14.      * @return the number of mappings
  15.      * @since 1.8
  16.      */
  17.     public long mappingCount() {
  18.         long n = sumCount();
  19.         return (n < 0L) ? 0L : n; // ignore transient negative values
  20.     }
  22.      final long sumCount() {
  23.         CounterCell[] as = counterCells; CounterCell a;
  24.         long sum = baseCount;
  25.         if (as != null) {
  26.             for (int i = 0; i < as.length; ++i) {
  27.                 if ((a = as[i]) != null)
  28.                     sum += a.value;//所有counter的值求和
  29.             }
  30.         }
  31.         return sum;
  32.     }

8.3、addCount方法

put方法最后调用了这个方法，将当前元素个数+1，一共做了两件事，更新baseCount的值，检查是否需要扩容。

  1. private final void addCount(long x, int check) {
  2.         CounterCell[] as; long b, s;
  3.         //利用CAS方法更新baseCount的值 
  4.         if ((as = counterCells) != null ||
  5.             !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
  6.             CounterCell a; long v; int m;
  7.             boolean uncontended = true;
  8.             if (as == null || (m = as.length - 1) < 0 ||
  9.                 (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
  10.                 !(uncontended =
  11.                   U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
  12.                 fullAddCount(x, uncontended);
  13.                 return;
  14.             }
  15.             if (check <= 1)
  16.                 return;
  17.             s = sumCount();
  18.         }
  19.         //如果check值大于等于0 则需要检验是否需要进行扩容操作
  20.         if (check >= 0) {
  21.             Node<K,V>[] tab, nt; int n, sc;
  22.             while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
  23.                    (n = tab.length) < MAXIMUM_CAPACITY) {
  24.                 int rs = resizeStamp(n);
  25.                 //
  26.                 if (sc < 0) {
  27.                     if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
  28.                         sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
  29.                         transferIndex <= 0)
  30.                         break;
  31.                      //如果已经有其他线程在执行扩容操作
  32.                     if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
  33.                         transfer(tab, nt);
  34.                 }
  35.                 //当前线程是唯一的或是第一个发起扩容的线程  此时nextTable=null
  36.                 else if (U.compareAndSwapInt(this, SIZECTL, sc,
  37.                                              (rs << RESIZE_STAMP_SHIFT) + 2))
  38.                     transfer(tab, null);
  39.                 s = sumCount();
  40.             }
  41.         }
  42.     }

参考资料
https://juejin.im/entry/59fc786d518825297f3fa968
https://blog.csdn.net/u010723709/article/details/48007881