1、ConcurrentHashMap-底层数据结构

  1. 1、ConcurrentHashMap-底层数据结构：
  2.     1-1、jdk1.7: 采用Segment + HashEntry的方式进行实现，采取分段锁来保证安全性。
  3.         1-1-1、Segment 的结构和 HashMap 类似，是一个数组和链表结构，继承了ReentrantLock类，是 ReentrantLock 重入锁，每个Segment 对应一把锁。
  4.         1-1-2、Segment的优点：如果多个线程访问不同的Segment，实际是没有冲突的 ，这与jdk8是类似的(jdk8是把锁加在每个链表/红黑树的头结点对象上，jdk7是把锁加在每个Segment对象上)
  5.         1-1-3、缺点：Segment 数组默认大小为16，这个容量初始化之后就不能改变了，并且不是懒惰初始化的。
  6.         1-1-4、HashEntry 则用于存储键值对数据。一个 ConcurrentHashMap 里包含一个 Segment 数组，一个 Segment 里包含一个 HashEntry 数组。
  7.         1-1-5、源码：
  8.             final Segment<K,V>[] segments; 
  9.             static final class HashEntry<K,V> {  
  10.                 final K key;  
  11.                 final int hash;  
  12.                 volatile V value;  
  13.                 final HashEntry<K,V> next;  
  14.             }      
  16.     1-2、jdk1.8: 摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 Synchronized 和 CAS 来操作。
  17.         1-2-1、源码：
  18.             transient volatile Node<K,V>[] table;

1-1、ConcurrentHashMap-底层数据结构-jdk1.7-示意图


容器(Map)-ConcurrentHashMap-源码分析 - 图1

1-2、ConcurrentHashMap-底层数据结构-jdk1.8-示意图

image.png

1-3、ConcurrentHashMap-底层数据结构-jdk1.8-基本属性

  1. 1、ConcurrentHashMap-jdk1.8-基本属性：
  2.     //node数组最大容量：1 << 30 = 1*2^30=1073741824
  3.     private static final int MAXIMUM_CAPACITY = 1 << 30;
  5.     //默认初始值，必须是2的幂数
  6.     private static final int DEFAULT_CAPACITY = 16;
  8.     //数组可能最大值，需要与toArray（）相关方法关联
  9.     static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  11.     //并发级别，遗留下来的，为兼容以前的版本
  12.     private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
  14.     //负载因子
  15.     private static final float LOAD_FACTOR = 0.75f;
  17.     //链表转红黑树阀值,> 8 链表转换为红黑树
  18.     static final int TREEIFY_THRESHOLD = 8;
  20.     //树转链表阀值，小于等于6（tranfer时，lc、hc=0两个计数器分别++记录原bin、新binTreeNode数量，<=UNTREEIFY_THRESHOLD 则untreeify(lo)）
  21.     static final int UNTREEIFY_THRESHOLD = 6;
  23.     //转化为红黑树的表的最小容量
  24.     static final int MIN_TREEIFY_CAPACITY = 64;
  26.     //每次进行转移的最小值
  27.     private static final int MIN_TRANSFER_STRIDE = 16;
  29.     //生成sizeCtl所使用的bit位数
  30.     private static int RESIZE_STAMP_BITS = 16;
  32.     //2^15-1，help resize的最大线程数
  33.     private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
  35.     //32-16=16，sizeCtl中记录size大小的偏移量
  36.     private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
  38.     //forwarding nodes的hash值
  39.     static final int MOVED = -1;
  41.     //树根节点的hash值
  42.     static final int TREEBIN = -2;
  44.     //ReservationNode的hash值
  45.     static final int RESERVED = -3;
  47.     //可用处理器数量
  48.     static final int NCPU = Runtime.getRuntime().availableProcessors();
  50.     //存放node的数组
  51.     transient volatile Node<K,V>[] table;
  53.     /*控制标识符，用来控制table的初始化和扩容的操作，不同的值有不同的含义
  54.         *当为负数时：-1代表正在初始化，-N代表有N-1个线程正在 进行扩容
  55.         *当为0时：代表当时的table还没有被初始化
  56.         *当为正数时：表示初始化或者下一次进行扩容的大小
  57.         */
  58.     private transient volatile int sizeCtl;
  60.     // 下一个表，过渡表，用于在扩容时将table表中的结点转移到nextTable中。
  61.     private transient volatile Node<K,V>[] nextTable;
  63.     // 基本计数
  64.     private transient volatile long baseCount;
  66.     // 扩容下另一个表的索引
  67.     private transient volatile int transferIndex;
  69.     // 旋转锁
  70.     private transient volatile int cellsBusy;
  72.     // counterCell表
  73.     private transient volatile CounterCell[] counterCells;

1-4、ConcurrentHashMap-底层数据结构-jdk1.8-关键类

  1. 1、ConcurrentHashMap-jdk1.8-关键类：
  2.     1-1、Node,静态内部类，保存 key，value 及 key 的 hash 值的数据结构。
  3.         //它对value和next属性设置了volatile同步锁(与JDK7的Segment相同)，它不允许调用setValue方法直接改变Node的value域，它增加了find方法辅助map.get()方法。
  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;
  10.             Node(int hash, K key, V val, Node<K,V> next) {
  11.                 this.hash = hash;
  12.                 this.key = key;
  13.                 this.val = val;
  14.                 this.next = next;
  15.             }
  17.             public final K getKey()       { return key; }
  18.             public final V getValue()     { return val; }
  19.             public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
  20.             public final String toString(){ return key + "=" + val; }
  21.             public final V setValue(V value) {
  22.                 throw new UnsupportedOperationException();
  23.             }
  25.             public final boolean equals(Object o) {
  26.                 Object k, v, u; Map.Entry<?,?> e;
  27.                 return ((o instanceof Map.Entry) &&
  28.                         (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
  29.                         (v = e.getValue()) != null &&
  30.                         (k == key || k.equals(key)) &&
  31.                         (v == (u = val) || v.equals(u)));
  32.             }
  34.             /**
  35.              * Virtualized support for map.get(); overridden in subclasses.
  36.              */
  37.             Node<K,V> find(int h, Object k) {
  38.                 Node<K,V> e = this;
  39.                 if (k != null) {
  40.                     do {
  41.                         K ek;
  42.                         if (e.hash == h &&
  43.                             ((ek = e.key) == k || (ek != null && k.equals(ek))))
  44.                             return e;
  45.                     } while ((e = e.next) != null);
  46.                 }
  47.                 return null;
  48.             }
  49.         }
  51.     1-2、TreeNode,静态内部类，
  52.         /**
  53.             当链表长度过长的时候，会转换为TreeNode。它并不是直接转换为红黑树，而是把这些结点包装成TreeNode放在TreeBin对象中，由TreeBin完成对红黑树的包装。而且TreeNode在ConcurrentHashMap集成自Node类，而并非HashMap中的集成自LinkedHashMap.Entry<K,V>类。
  54.         */
  55.         static final class TreeNode<K,V> extends Node<K,V> {
  56.             TreeNode<K,V> parent;  // red-black tree links
  57.             TreeNode<K,V> left;
  58.             TreeNode<K,V> right;
  59.             TreeNode<K,V> prev;    // needed to unlink next upon deletion
  60.             boolean red;
  62.             //TreeNode带有next指针，这样做的目的是方便基于TreeBin的访问
  63.             TreeNode(int hash, K key, V val, Node<K,V> next,TreeNode<K,V> parent) {
  64.                 super(hash, key, val, next);
  65.                 this.parent = parent;
  66.             }
  68.             Node<K,V> find(int h, Object k) {
  69.                 return findTreeNode(h, k, null);
  70.             }
  72.             /**
  73.              * Returns the TreeNode (or null if not found) for the given key
  74.              * starting at given root.
  75.              */
  76.             final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
  77.                 if (k != null) {
  78.                     TreeNode<K,V> p = this;
  79.                     do  {
  80.                         int ph, dir; K pk; TreeNode<K,V> q;
  81.                         TreeNode<K,V> pl = p.left, pr = p.right;
  82.                         if ((ph = p.hash) > h)
  83.                             p = pl;
  84.                         else if (ph < h)
  85.                             p = pr;
  86.                         else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
  87.                             return p;
  88.                         else if (pl == null)
  89.                             p = pr;
  90.                         else if (pr == null)
  91.                             p = pl;
  92.                         else if ((kc != null ||
  93.                                   (kc = comparableClassFor(k)) != null) &&
  94.                                  (dir = compareComparables(kc, k, pk)) != 0)
  95.                             p = (dir < 0) ? pl : pr;
  96.                         else if ((q = pr.findTreeNode(h, k, kc)) != null)
  97.                             return q;
  98.                         else
  99.                             p = pl;
  100.                     } while (p != null);
  101.                 }
  102.                 return null;
  103.             }
  104.         }
  106.     1-3、TreeBin类,静态内部类，
  107.         /**
  108.             并不负责包装用户的key、value信息，而是包装的很多TreeNode节点。它代替了TreeNode的根节点.
  109.             在实际的ConcurrentHashMap“数组”中，存放的是TreeBin对象，而不是TreeNode对象.
  110.             这个类还带有了读写锁。
  111.         */
  112.         static final class TreeBin<K,V> extends Node<K,V> {
  113.             TreeNode<K,V> root;
  114.             volatile TreeNode<K,V> first;
  115.             volatile Thread waiter;
  116.             volatile int lockState;
  117.             // values for lockState
  118.             static final int WRITER = 1; // set while holding write lock
  119.             static final int WAITER = 2; // set when waiting for write lock
  120.             static final int READER = 4; // increment value for setting read lock
  122.             /**
  123.              * Tie-breaking utility for ordering insertions when equal
  124.              * hashCodes and non-comparable. We don't require a total
  125.              * order, just a consistent insertion rule to maintain
  126.              * equivalence across rebalancings. Tie-breaking further than
  127.              * necessary simplifies testing a bit.
  128.              */
  129.             static int tieBreakOrder(Object a, Object b) {
  130.                 int d;
  131.                 if (a == null || b == null ||
  132.                     (d = a.getClass().getName().
  133.                      compareTo(b.getClass().getName())) == 0)
  134.                     d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
  135.                          -1 : 1);
  136.                 return d;
  137.             }
  139.             /**
  140.              * Creates bin with initial set of nodes headed by b.
  141.              */
  142.             TreeBin(TreeNode<K,V> b) {
  143.                 //指定了它的hash值为TREEBIN常量
  144.                 super(TREEBIN, null, null, null);
  145.                 this.first = b;
  146.                 TreeNode<K,V> r = null;
  147.                 for (TreeNode<K,V> x = b, next; x != null; x = next) {
  148.                     next = (TreeNode<K,V>)x.next;
  149.                     x.left = x.right = null;
  150.                     if (r == null) {
  151.                         x.parent = null;
  152.                         x.red = false;
  153.                         r = x;
  154.                     }
  155.                     else {
  156.                         K k = x.key;
  157.                         int h = x.hash;
  158.                         Class<?> kc = null;
  159.                         for (TreeNode<K,V> p = r;;) {
  160.                             int dir, ph;
  161.                             K pk = p.key;
  162.                             if ((ph = p.hash) > h)
  163.                                 dir = -1;
  164.                             else if (ph < h)
  165.                                 dir = 1;
  166.                             else if ((kc == null &&
  167.                                       (kc = comparableClassFor(k)) == null) ||
  168.                                      (dir = compareComparables(kc, k, pk)) == 0)
  169.                                 dir = tieBreakOrder(k, pk);
  170.                                 TreeNode<K,V> xp = p;
  171.                             if ((p = (dir <= 0) ? p.left : p.right) == null) {
  172.                                 x.parent = xp;
  173.                                 if (dir <= 0)
  174.                                     xp.left = x;
  175.                                 else
  176.                                     xp.right = x;
  177.                                 r = balanceInsertion(r, x);
  178.                                 break;
  179.                             }
  180.                         }
  181.                     }
  182.                 }
  183.                 this.root = r;
  184.                 assert checkInvariants(root);
  185.             }
  186.             //........
  187.         }
  189.     1-4、ForwardingNode类，静态内部类，
  190.         /**
  191.             一个用于连接两个table的节点类。它包含一个nextTable指针，用于指向下一张表。而且这个节点的key value next指针全部为null，它的hash值为-1。
  192.             find的方法是从nextTable里进行查询节点，而不是以自身为头节点进行查找。
  193.         */
  194.         static final class ForwardingNode<K,V> extends Node<K,V> {
  195.             final Node<K,V>[] nextTable;
  196.             ForwardingNode(Node<K,V>[] tab) {
  197.                 super(MOVED, null, null, null);
  198.                 this.nextTable = tab;
  199.             }
  201.             Node<K,V> find(int h, Object k) {
  202.                 // loop to avoid arbitrarily deep recursion on forwarding nodes
  203.                 outer: for (Node<K,V>[] tab = nextTable;;) {
  204.                     Node<K,V> e; int n;
  205.                     if (k == null || tab == null || (n = tab.length) == 0 ||
  206.                         (e = tabAt(tab, (n - 1) & h)) == null)
  207.                         return null;
  208.                     for (;;) {
  209.                         int eh; K ek;
  210.                         if ((eh = e.hash) == h &&
  211.                             ((ek = e.key) == k || (ek != null && k.equals(ek))))
  212.                             return e;
  213.                         if (eh < 0) {
  214.                             if (e instanceof ForwardingNode) {
  215.                                 tab = ((ForwardingNode<K,V>)e).nextTable;
  216.                                 continue outer;
  217.                             }
  218.                             else
  219.                                 return e.find(h, k);
  220.                         }
  221.                         if ((e = e.next) == null)
  222.                             return null;
  223.                     }
  224.                 }
  225.             }
  226.         }
  228.     1-5、Traverser类
  229. 　　        Traverser类主要用于遍历操作，其子类有BaseIterator、KeySpliterator、ValueSpliterator、EntrySpliterator四个类，BaseIterator用于遍历操作。KeySplitertor、ValueSpliterator、EntrySpliterator则用于键、值、键值对的划分。
  231. 　　1-6、CollectionView类
  232.          CollectionView抽象类主要定义了视图操作，其子类KeySetView、ValueSetView、EntrySetView分别表示键视图、值视图、键值对视图。对视图均可以进行操作。
  234. 　　1-7、Segment类
  235. 　　       Segment类在JDK1.8中与之前的版本的JDK作用存在很大的差别，JDK1.8下，其在普通的ConcurrentHashMap操作中已经没有失效，其在序列化与反序列化的时候会发挥作用。
  237. 　　1-8、CounterCell
  238.     　　 CounterCell类主要用于对baseCount的计数。

2、ConcurrentHashMap-Unsafe|CAS

  1. 1、Unsafe|CAS：
  2.     1-1、ConcurrentHashMap类中，U.compareAndSwapXXX的方法，这个方法是利用一个CAS算法实现无锁化的修改值的操作，他可以大大降低锁代理的性能消耗。不断地去比较当前内存中的变量值与你指定的一个变量值是否相等，如果相等，则接受你指定的修改的值，否则拒绝你的操作。
  3.     1-2、ConcurrentHashMap类中，unsafe静态块，控制了一些属性的修改工作，比如最常用的SIZECTL 。
  4.     1-3、ConcurrentHashMap类中，添加了Unsafe实例，主要用于反射获取对象相应的字段。

3、ConcurrentHashMap-构造方法

  1. 1、ConcurrentHashMap-构造方法：
  3.     //无参构造函数用于创建一个带有默认初始容量 (16)、加载因子 (0.75) 和 concurrencyLevel (16) 的新的空映射。
  4.     /**
  5.         concurrencyLevel: 
  6.             1.表示并发级别，这个值用来确定Segment的个数，Segment的个数是大于等于concurrencyLevel的第一个2的n次方的数。
  7.             2.比如，如果concurrencyLevel为12，13，14，15，16这些数，则Segment的数目为16(2的4次方)。默认值为static final int DEFAULT_CONCURRENCY_LEVEL = 16;
  8.             3.也就是Segment的个数不能超过规定的最大Segment的个数，默认值为static final int MAX_SEGMENTS = 1 << 16;，如果超过这个值，设置为这个值。
  9.     */
  10.     public ConcurrentHashMap() {
  11.     }
  13.     //构造函数用于创建一个带有指定初始容量、默认加载因子 (0.75) 和 concurrencyLevel (16) 的新的空映射。
  14.     public ConcurrentHashMap(int initialCapacity) {
  15.         if (initialCapacity < 0) // 初始容量小于0，抛出异常
  16.             throw new IllegalArgumentException();
  17.         int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
  18.                    MAXIMUM_CAPACITY :
  19.                    tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));// 找到最接近该容量的2的幂次方数
  20.         // 初始化
  21.         this.sizeCtl = cap;
  22.     }
  24.     //该构造函数用于创建一个带有指定初始容量、加载因子和默认 concurrencyLevel (1) 的新的空映射。
  25.     public ConcurrentHashMap(int initialCapacity, float loadFactor) {
  26.         this(initialCapacity, loadFactor, 1);
  27.     }
  29.     //该构造函数用于创建一个带有指定初始容量、加载因子和并发级别的新的空映射。
  30.     public ConcurrentHashMap(int initialCapacity,
  31.                              float loadFactor, int concurrencyLevel) {
  32.         if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
  33.             throw new IllegalArgumentException();
  34.         if (initialCapacity < concurrencyLevel)   // Use at least as many bins
  35.             initialCapacity = concurrencyLevel;   // as estimated threads
  36.         long size = (long)(1.0 + (long)initialCapacity / loadFactor);
  37.         int cap = (size >= (long)MAXIMUM_CAPACITY) ?
  38.             MAXIMUM_CAPACITY : tableSizeFor((int)size);
  39.         this.sizeCtl = cap;
  40.     }
  42.     //该构造函数用于构造一个与给定映射具有相同映射关系的新映射。
  43.     public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
  44.         this.sizeCtl = DEFAULT_CAPACITY;
  45.         putAll(m);
  46.     }
  48. 2、构造函数-小结：
  49.     2-1、构造函数而言，会根据输入的initialCapacity的大小来确定一个最小的且大于等于initialCapacity大小的2的n次幂，如initialCapacity为15，则sizeCtl为16，若initialCapacity为16，则sizeCtl为16。若initialCapacity大小超过了允许的最大值，则sizeCtl为最大值。
  50.     2-2、值得注意的是，构造函数中的concurrencyLevel参数已经在JDK1.8中的意义发生了很大的变化，其并不代表所允许的并发数，其只是用来确定sizeCtl大小，在JDK1.8中的并发控制都是针对具体的桶而言，即有多少个桶就可以允许多少个并发数。

4、ConcurrentHashMap-添加元素

  1. 1、添加元素：.put()方法，采用 CAS + synchronized 实现并发插入或更新操作。
  3. 2、源代码：
  4.     //.put()方法，底层调用了.putVal()进行数据的插入
  5.     public V put(K key, V value) {
  6.         return putVal(key, value, false);
  7.     }
  9.     final V putVal(K key, V value, boolean onlyIfAbsent) {
  10.         //键或值为空，抛出异常
  11.         if (key == null || value == null) 
  12.             throw new NullPointerException();
  13.         // 键的hash值经过计算获得hash值
  14.         int hash = spread(key.hashCode());
  15.         int binCount = 0;
  16.         for (Node<K,V>[] tab = table;;) { // 无限循环,何时插入成功 何时跳出
  17.             Node<K,V> f; int n, i, fh;
  18.             // 表为空或者表的长度为0
  19.             if (tab == null || (n = tab.length) == 0)
  20.                 tab = initTable();// 初始化表
  21.             // 表不为空并且表的长度大于0，并且该桶不为空
  22.             else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
  23.                 // 比较并且交换值，如tab的第i项为空则用新生成的node替换
  24.                 if (casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null)))
  25.                     break;                   // no lock when adding to empty bin
  26.             }
  27.              // 该结点的hash值为MOVED, 为表连接点时，需要进行整合表的操作
  28.             else if ((fh = f.hash) == MOVED)
  29.                 tab = helpTransfer(tab, f); // 进行结点的转移（在扩容的过程中）
  30.             else {
  31.                 V oldVal = null;
  32.                 // 加锁同步
  33.                 synchronized (f) {
  34.                     // 找到table表下标为i的节点
  35.                     if (tabAt(tab, i) == f) {
  36.                         // 该table表中该结点的hash值大于0
  37.                         if (fh >= 0) {
  38.                             // binCount赋值为1
  39.                             binCount = 1;
  40.                             // 无限循环
  41.                             for (Node<K,V> e = f;; ++binCount) {
  42.                                 K ek;
  43.                                 // 结点的hash值相等并且key也相等
  44.                                 if (e.hash == hash &&
  45.                                     ((ek = e.key) == key ||
  46.                                      (ek != null && key.equals(ek)))) {
  47.                                     // 保存该结点的val值
  48.                                     oldVal = e.val;
  49.                                     // 进行判断
  50.                                     if (!onlyIfAbsent)
  51.                                          // 将指定的value保存至节点，即进行了节点值的更新
  52.                                         e.val = value;
  53.                                     break;
  54.                                 }
  55.                                 // 保存当前节点
  56.                                 Node<K,V> pred = e;
  57.                                 // 当前结点的下一个结点为空，即为最后一个结点
  58.                                 if ((e = e.next) == null) {
  59.                                     // 新生一个结点并且赋值给next域
  60.                                     pred.next = new Node<K,V>(hash, key, value, null);
  61.                                     break;
  62.                                 }
  63.                             }
  64.                         }
  65.                         // 节点为红黑树结点类型
  66.                         else if (f instanceof TreeBin) {
  67.                             Node<K,V> p;
  68.                              // binCount赋值为2
  69.                             binCount = 2;
  70.                             // 将hash、key、value放入红黑树
  71.                             if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) {
  72.                                 // 保存结点的val
  73.                                 oldVal = p.val;
  74.                                 if (!onlyIfAbsent)
  75.                                     // 赋值结点value值
  76.                                     p.val = value;
  77.                             }
  78.                         }
  79.                     }
  80.                 }
  81.                 // binCount不为0
  82.                 if (binCount != 0) {
  83.                     // 如果binCount大于等于转化为红黑树的阈值
  84.                     if (binCount >= TREEIFY_THRESHOLD)
  85.                         // 进行转化
  86.                         treeifyBin(tab, i);
  87.                     if (oldVal != null) // 旧值不为空
  88.                          // 返回旧值
  89.                         return oldVal;
  90.                     break;
  91.                 }
  92.             }
  93.         }
  94.         // 增加binCount的数量
  95.         addCount(1L, binCount);
  96.         return null;
  97.     }
  99.     2-1、.putVal()方法，执行流程：
  100.           2-1-1、判断存储的key、value是否为空，若为空，则抛出异常，否则，进入步骤2-1-2。
  101.           2-1-2、计算key的hash值，随后进入无限循环，该无限循环可以确保成功插入数据，若table表为空或者长度为0，则初始化table表，否则，进入步骤2-1-3。
  102.           2-1-3、根据key的hash值取出table表中的结点元素，若取出的结点为空(该桶为空)，则使用CAS将key、value、hash值生成的结点放入桶中。否则，进入步骤2-1-4。
  103.           2-1-4、若该结点的的hash值为MOVED，则对该桶中的结点进行转移，否则，进入步骤2-1-5。
  104.           2-1-5、对桶中的第一个结点(即table表中的结点)进行加锁，对该桶进行遍历，桶中的结点的hash值与key值与给定的hash值和key值相等，则根据标识选择是否进行更新操作(用给定的value值替换该结点的value值)，若遍历完桶仍没有找到hash值与key值和指定的hash值与key值相等的结点，则直接新生一个结点并赋值为之前最后一个结点的下一个结点。进入步骤2-1-6。
  105.           2-1-6、若binCount值达到红黑树转化的阈值，则将桶中的结构转化为红黑树存储，最后，增加binCount的值。
  107.    2-2、初始化表.initTable()方法源码分析：
  108.            //对于table的大小，会根据sizeCtl的值进行设置，如果没有设置szieCtl的值，那么默认生成的table大小为16，否则，会根据sizeCtl的大小设置table大小。
  109.            private final Node<K,V>[] initTable() {
  110.             Node<K,V>[] tab; int sc;
  111.             while ((tab = table) == null || tab.length == 0) { // 表为空或者表的长度为0
  112.                 // 如果这个值〈0，表示其他线程正在进行初始化，就放弃这个操作。进行线程让步等待
  113.                 if ((sc = sizeCtl) < 0)
  114.                     Thread.yield(); // lost initialization race; just spin
  115.                 else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { // 比较sizeCtl的值与sc是否相等，相等则用-1替换,防止其他线程进入。
  116.                     try {
  117.                         if ((tab = table) == null || tab.length == 0) { // table表为空或者大小为0
  118.                             // sc的值是否大于0，若是，则n为sc，否则，n为默认初始容量
  119.                             int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
  120.                             @SuppressWarnings("unchecked")
  121.                             // 新生结点数组
  122.                             Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
  123.                             // 赋值给table
  124.                             table = tab = nt;
  125.                             // sc为n * 3/4==>n-(n/2)/2=3/4*n=0.75*n
  126.                             sc = n - (n >>> 2);
  127.                         }
  128.                     } finally {
  129.                         // 设置sizeCtl的值,初始化数组后，将sizeCtl的值改为0.75*n。
  130.                         sizeCtl = sc;
  131.                     }
  132.                     break;
  133.                 }
  134.             }
  135.             // 返回table表
  136.             return tab;
  137.         }
  139.     2-3、.tabAt()方法源码分析：原子操作。
  140.         //原子操作，用于对指定位置的节点进行操作。
  141.         //获得在i位置上的Node节点，即返回table数组中下标为i的结点
  142.         static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
  143.             //getObjectVolatile的第二项参数为下标为i的偏移地址。
  144.             //U.getObjectVolatile()，直接获取指定内存的数据，保证了每次拿到数据都是最新的。
  145.             return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
  146.         }
  148.     2-4、.casTabAt()方法源码分析：原子操作。
  149.         /**
  150.             利用CAS算法设置i位置上的Node节点。之所以能实现并发是因为他指定了原来这个节点的值是多少
  151.             在CAS算法中，会比较内存中的值与你指定的这个值是否相等，如果相等才接受你的修改，否则拒绝你的修改
  152.             因此当前线程中的值并不是最新的值，这种修改可能会覆盖掉其他线程的修改结果.有点类似于SVN
  153.         */
  154.         //用于比较table数组下标为i的结点是否为c，若为c，则用v交换操作。否则，不进行交换操作。
  155.         static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v) {
  156.             return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
  157.         }
  159.     2-5、.setTabAt()方法源码分析：原子操作
  160.         //利用volatile方法设置节点位置的值
  161.         static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
  162.             U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
  163.         }
  165.     2-6、.helpTransfer()方法源码分析：
  166.         //用于在扩容时将table表中的结点转移到nextTable中。
  167.         //是一个协助扩容的方法。这个方法被调用的时候，当前ConcurrentHashMap一定已经有了nextTable对象，首先拿到这个nextTable对象，调用transfer方法。回看上面的transfer方法可以看到，当本线程进入扩容方法的时候会直接进入复制阶段。
  168.         final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
  169.             Node<K,V>[] nextTab; int sc;
  170.             if (tab != null && (f instanceof ForwardingNode) &&
  171.                 (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) { // table表不为空并且结点类型使ForwardingNode类型，并且结点的nextTable不为空
  172.                 int rs = resizeStamp(tab.length);
  173.                 while (nextTab == nextTable && table == tab &&
  174.                        (sc = sizeCtl) < 0) { // 条件判断
  175.                     if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
  176.                         sc == rs + MAX_RESIZERS || transferIndex <= 0) // 
  177.                         break;
  178.                     if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) { // 比较并交换
  179.                         // 将table的结点转移到nextTab中,具体见扩容源码章节
  180.                         transfer(tab, nextTab);
  181.                         break;
  182.                     }
  183.                 }
  184.                 return nextTab;
  185.             }
  186.             return table;
  187.         }
  189.     2-7、.putTreeVal()方法源码分析：
  190.         //该方法用于将指定的hash、key、value值添加到红黑树中，若已经添加了，则返回null，否则返回该结点。
  191.         final TreeNode<K,V> putTreeVal(int h, K k, V v) {
  192.             Class<?> kc = null;
  193.             boolean searched = false;
  194.             for (TreeNode<K,V> p = root;;) {
  195.                 int dir, ph; K pk;
  196.                 if (p == null) {
  197.                     first = root = new TreeNode<K,V>(h, k, v, null, null);
  198.                     break;
  199.                 }
  200.                 else if ((ph = p.hash) > h)
  201.                     dir = -1;
  202.                 else if (ph < h)
  203.                     dir = 1;
  204.                 else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
  205.                     return p;
  206.                 else if ((kc == null &&
  207.                           (kc = comparableClassFor(k)) == null) ||
  208.                          (dir = compareComparables(kc, k, pk)) == 0) {
  209.                     if (!searched) {
  210.                         TreeNode<K,V> q, ch;
  211.                         searched = true;
  212.                         if (((ch = p.left) != null &&
  213.                              (q = ch.findTreeNode(h, k, kc)) != null) ||
  214.                             ((ch = p.right) != null &&
  215.                              (q = ch.findTreeNode(h, k, kc)) != null))
  216.                             return q;
  217.                     }
  218.                     dir = tieBreakOrder(k, pk);
  219.                 }
  221.                 TreeNode<K,V> xp = p;
  222.                 if ((p = (dir <= 0) ? p.left : p.right) == null) {
  223.                     TreeNode<K,V> x, f = first;
  224.                     first = x = new TreeNode<K,V>(h, k, v, f, xp);
  225.                     if (f != null)
  226.                         f.prev = x;
  227.                     if (dir <= 0)
  228.                         xp.left = x;
  229.                     else
  230.                         xp.right = x;
  231.                     if (!xp.red)
  232.                         x.red = true;
  233.                     else {
  234.                         lockRoot();
  235.                         try {
  236.                             root = balanceInsertion(root, x);
  237.                         } finally {
  238.                             unlockRoot();
  239.                         }
  240.                     }
  241.                     break;
  242.                 }
  243.             }
  244.             assert checkInvariants(root);
  245.             return null;
  246.         }
  248.     2-8、.treeifyBin()方法源码分析：
  249.         //用于将桶中的数据结构转化为红黑树，其中，值得注意的是，当table的长度未达到阈值时，会进行一次扩容操作，该操作会使得触发treeifyBin操作的某个桶中的所有元素进行一次重新分配，这样可以避免某个桶中的结点数量太大。
  250.         private final void treeifyBin(Node<K,V>[] tab, int index) {
  251.             Node<K,V> b; int n, sc;
  252.             if (tab != null) { // 表不为空
  253.                 if ((n = tab.length) < MIN_TREEIFY_CAPACITY) // table表的长度小于最小的长度
  254.                     // 进行扩容，调整某个桶中结点数量过多的问题（由于某个桶中结点数量超出了阈值，则触发treeifyBin）
  255.                     tryPresize(n << 1);
  256.                 else if ((b = tabAt(tab, index)) != null && b.hash >= 0) { // 桶中存在结点并且结点的hash值大于等于0
  257.                     synchronized (b) { // 对桶中第一个结点进行加锁
  258.                         if (tabAt(tab, index) == b) { // 第一个结点没有变化
  259.                             TreeNode<K,V> hd = null, tl = null;
  260.                             for (Node<K,V> e = b; e != null; e = e.next) { // 遍历桶中所有结点
  261.                                 // 新生一个TreeNode结点
  262.                                 TreeNode<K,V> p =
  263.                                     new TreeNode<K,V>(e.hash, e.key, e.val,
  264.                                                       null, null);
  265.                                 if ((p.prev = tl) == null) // 该结点前驱为空
  266.                                     // 设置p为头结点
  267.                                     hd = p;
  268.                                 else
  269.                                     // 尾节点的next域赋值为p
  270.                                     tl.next = p;
  271.                                 // 尾节点赋值为p
  272.                                 tl = p;
  273.                             }
  274.                             // 设置table表中下标为index的值为hd
  275.                             setTabAt(tab, index, new TreeBin<K,V>(hd));
  276.                         }
  277.                     }
  278.                 }
  279.             }
  280.         }
  282.     2-9、.addCount()方法源码分析：
  283.         //该方法主要完成binCount的值加1的操作。
  284.          private final void addCount(long x, int check) {
  285.             CounterCell[] as; long b, s;
  286.             if ((as = counterCells) != null ||
  287.                 !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) { // counterCells不为空或者比较交换失败
  288.                 CounterCell a; long v; int m;
  289.                 // 无竞争标识
  290.                 boolean uncontended = true;
  291.                 if (as == null || (m = as.length - 1) < 0 ||
  292.                     (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
  293.                     !(uncontended =
  294.                       U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) { // 
  295.                     fullAddCount(x, uncontended);
  296.                     return;
  297.                 }
  298.                 if (check <= 1)
  299.                     return;
  300.                 s = sumCount();
  301.             }
  302.             //.......
  303.         }

5、ConcurrentHashMap-获取元素

  1. 1、获取元素：.get()方法
  3. 2、源代码：
  4.     //get函数根据key的hash值来计算在哪个桶中，再遍历桶，查找元素，若找到则返回该结点，否则，返回null。
  5.      public V get(Object key) {
  6.         Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
  7.         // 计算key的hash值
  8.         int h = spread(key.hashCode()); 
  9.         if ((tab = table) != null && (n = tab.length) > 0 &&
  10.             (e = tabAt(tab, (n - 1) & h)) != null) { // 表不为空并且表的长度大于0并且key所在的桶不为空
  11.             if ((eh = e.hash) == h) { // 表中的元素的hash值与key的hash值相等
  12.                 if ((ek = e.key) == key || (ek != null && key.equals(ek))) // 键相等
  13.                     // 返回值
  14.                     return e.val;
  15.             }
  16.             else if (eh < 0) // 结点hash值小于0
  17.                 // 在桶（链表/红黑树）中查找
  18.                 return (p = e.find(h, key)) != null ? p.val : null;
  19.             while ((e = e.next) != null) { // 对于结点hash值大于0的情况
  20.                 if (e.hash == h &&
  21.                     ((ek = e.key) == key || (ek != null && key.equals(ek))))
  22.                     return e.val;
  23.             }
  24.         }
  25.         return null;
  26.     }

6、ConcurrentHashMap-删除元素

  1. 1、删除元素：.remove()方法，内部调用了.replaceNode()方法
  3. 2、源代码：
  5.     public V remove(Object key) {
  6.         return replaceNode(key, null, null);
  7.     }
  9.     //对remove函数提供支持，remove函数底层是调用的replaceNode函数实现结点的删除。
  10.     final V replaceNode(Object key, V value, Object cv) {
  11.         // 计算key的hash值
  12.         int hash = spread(key.hashCode());
  13.         for (Node<K,V>[] tab = table;;) { // 无限循环
  14.             Node<K,V> f; int n, i, fh;
  15.             if (tab == null || (n = tab.length) == 0 ||
  16.                 (f = tabAt(tab, i = (n - 1) & hash)) == null) // table表为空或者表长度为0或者key所对应的桶为空
  17.                 // 跳出循环
  18.                 break;
  19.             else if ((fh = f.hash) == MOVED) // 桶中第一个结点的hash值为MOVED
  20.                 // 转移
  21.                 tab = helpTransfer(tab, f);
  22.             else {
  23.                 V oldVal = null;
  24.                 boolean validated = false;
  25.                 synchronized (f) { // 加锁同步
  26.                     if (tabAt(tab, i) == f) { // 桶中的第一个结点没有发生变化
  27.                         if (fh >= 0) { // 结点hash值大于0
  28.                             validated = true;
  29.                             for (Node<K,V> e = f, pred = null;;) { // 无限循环
  30.                                 K ek;
  31.                                 if (e.hash == hash &&
  32.                                     ((ek = e.key) == key ||
  33.                                      (ek != null && key.equals(ek)))) { // 结点的hash值与指定的hash值相等，并且key也相等
  34.                                     V ev = e.val;
  35.                                     if (cv == null || cv == ev ||
  36.                                         (ev != null && cv.equals(ev))) { // cv为空或者与结点value相等或者不为空并且相等
  37.                                         // 保存该结点的val值
  38.                                         oldVal = ev;
  39.                                         if (value != null) // value为null
  40.                                             // 设置结点value值
  41.                                             e.val = value;
  42.                                         else if (pred != null) // 前驱不为空
  43.                                             // 前驱的后继为e的后继，即删除了e结点
  44.                                             pred.next = e.next;
  45.                                         else
  46.                                             // 设置table表中下标为index的值为e.next
  47.                                             setTabAt(tab, i, e.next);
  48.                                     }
  49.                                     break;
  50.                                 }
  51.                                 pred = e;
  52.                                 if ((e = e.next) == null)
  53.                                     break;
  54.                             }
  55.                         }
  56.                         else if (f instanceof TreeBin) { // 为红黑树结点类型
  57.                             validated = true;
  58.                             // 类型转化
  59.                             TreeBin<K,V> t = (TreeBin<K,V>)f;
  60.                             TreeNode<K,V> r, p;
  61.                             if ((r = t.root) != null &&
  62.                                 (p = r.findTreeNode(hash, key, null)) != null) { // 根节点不为空并且存在与指定hash和key相等的结点
  63.                                 // 保存p结点的value
  64.                                 V pv = p.val;
  65.                                 if (cv == null || cv == pv ||
  66.                                     (pv != null && cv.equals(pv))) { // cv为空或者与结点value相等或者不为空并且相等
  67.                                     oldVal = pv;
  68.                                     if (value != null) 
  69.                                         p.val = value;
  70.                                     else if (t.removeTreeNode(p)) // 移除p结点
  71.                                         setTabAt(tab, i, untreeify(t.first));
  72.                                 }
  73.                             }
  74.                         }
  75.                     }
  76.                 }
  77.                 if (validated) {
  78.                     if (oldVal != null) {
  79.                         if (value == null)
  80.                             // baseCount值减一
  81.                             addCount(-1L, -1);
  82.                         return oldVal;
  83.                     }
  84.                     break;
  85.                 }
  86.             }
  87.         }
  88.         return null;
  89.     }

7、ConcurrentHashMap-扩容

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

7-1、ConcurrentHashMap-扩容-多线程-逻辑图


image.png

  1. https://www.cnblogs.com/williamjie/p/9099861.html
  2. https://www.cnblogs.com/banjinbaijiu/p/9147434.html