JDK1.7

整个ConcurrentHashMap由一个个Segment组成，Segment代表部分或者一段的意思，所以很多地方都会将其描述为分段锁。Segment通过继承ReentrantLock来进行加锁，所以每次需要加锁的操作锁住的是一个Segment，这样只要保证Segment是线程安全的，也就实现了全局的线程安全。
每个Segment就是一个哈希数组，对应每个槽位中是一个个的链表。
3.png
concurrencyLevel：并行级别、并发数、Segment数。默认是16，也就是说ConcurrentHashMap有16个Segment，所以理论上，最多可以同时支持16个线程并发写，只要它们的操作分布在不同的Segment上。这个值可以在初始化的时候设置为其他值，但是一旦初始化以后，它是不可以扩容的。

初始化

  1. public ConcurrentHashMap(int initialCapacity,
  2.                          float loadFactor, int concurrencyLevel) {
  3.     if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
  4.         throw new IllegalArgumentException();
  5.     if (concurrencyLevel > MAX_SEGMENTS)
  6.         concurrencyLevel = MAX_SEGMENTS;
  7.     // Find power-of-two sizes best matching arguments
  8.     int sshift = 0;
  9.     int ssize = 1;
  10.     // 计算并行级别，保持并行级别是2的n次方
  11.     while (ssize < concurrencyLevel) {
  12.         ++sshift;
  13.         ssize <<= 1;
  14.     }
  15.     // 使用默认值，currencyLevel为16，sshift为4
  16.     // 那么segmentShift=28，segmentMask=15
  17.     this.segmentShift = 32 - sshift;
  18.     this.segmentMask = ssize - 1;
  20.     if (initialCapacity > MAXIMUM_CAPACITY)
  21.         initialCapacity = MAXIMUM_CAPACITY;
  23.     // initialCapacity设置整个map的初始大小
  24.     // 这里根据initialCapacity计算Segment数组中每个位置可以分到的大小
  25.     // 如initialCapacity=64，那么每个Segment可以分到4个
  26.     int c = initialCapacity / ssize;
  27.     if (c * ssize < initialCapacity)
  28.         ++c;
  29.     // 默认MIN_SEGMENT_TABLE_CAPACITY 是 2，这个值也是有讲究的
  30.     // 因为这样的话，对于具体的槽上，
  31.     // 插入一个元素不至于扩容，插入第二个的时候才会扩容
  32.     int cap = MIN_SEGMENT_TABLE_CAPACITY; 
  33.     while (cap < c)
  34.         cap <<= 1;
  36.     // 创建segment数组，并创建数组的第一个元素segment[0]
  37.     Segment<K,V> s0 =
  38.         new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
  39.                          (HashEntry<K,V>[])new HashEntry[cap]);
  40.     Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
  41.     // 往数组写入segment[0]
  42.     UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
  43.     this.segments = ss;
  44. }

初始化完成，我们得到了一个Segment数组。
就当是new ConcurrentHashMap()无参构造函数进行初始化的，那么初始化完成以后：

  • Segment数组长度为16，不可以扩容；
  • Segment[i]的默认大小为2，负载因子是0.75，得出初始阈值为1.5，也就是以后插入第一个元素不会触发扩容。插入第二个会进行第一次扩容；
  • 这里初始化了 segment[0]，其他位置还是 null；
  • 当前移位数 segmentShift = 28，掩码 segmentMask = 15。

put过程

流程如下：
（1）计算key的hash值，再计算Segment数组下标，找到相应的Segment。
（2）如果该Segment未初始化，则采用循环CAS操作的方式进行初始化。
（3）执行插入操作：

  1. 通过tryLock获取该Segment的独占锁，失败则通过scanAndLockForPut获取锁。
  2. 计算数组下标，使用头插法插入节点，如果节点为空则执行初始化。
  3. 如果添加节点后该Segment超过阈值，那么对这个Segment进行扩容。

（4）Segment扩容：

  1. 创建新数组，扩容两倍。
  2. 进行数据迁移，将原数组i处的链表移到新数组i或者i+oldCap的位置。

  3. 将新数组赋值给原数组。

    1. public V put(K key, V value) {
    2. Segment<K, V> s;
    3. if (value == null) {
    4.   throw new NullPointerException();
    5. }
    6. // 1. 计算key的hash值
    7. int hash = hash(key);
    8. // 2. 根据hash值找到Segment数组中的位置j
    9. // hash是32位，无符号右移segmentShift(28)位，剩下高4位
    10. // 然后和segmentMask(15)做一次与操作，也就是说j是hash值的高位，也就是槽的数组下标
    11. int j = (hash >>> segmentShift) & segmentMask;
    12. // 初始化只初始化了segment[0]，其他位置还是null
    13. // ensureSegment(j)对segment[j]进行初始化
    14. if ((s = (Segment<K, V> UNSAFE.getObject(segments, (j << SSHIFT) + SBASE)) == null)
    15.   s = ensureSegment(j);
    16. // 3. 插入到槽s中
    17. return s.put(key, hash, value, false);
    18. }

    第一层皮很简单，根据hash值很快就能找到相应Segment，之后就是Segment内部的put操作了。
    Segment内部是由数组+链表组成的。

    1. final V put(K key, int hash, V value, boolean onlyIfAbsent) {
    2. // 先通过tryLock获取该segment的独占锁，node初始化为空
    3. // 如果失败则通过scanAndLockForPut获取锁，node在scanAndLockForPut中初始化
    4. HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value);
    5. V oldValue;
    6. try {
    7.   // segment内部的数组
    8.   HashEntry<K,V>[] tab = table;
    9.   // 计算放置的数组下标
    10.   int index = (tab.length - 1) & hash;
    11.   // 获取到该数组相应位置的链表头节点
    12.   HashEntry<K,V> first = entryAt(tab, index);
    14.   // 遍历链表
    15.   for (HashEntry<K,V> e = first;;) {
    16.       if (e != null) {
    17.           K k;
    18.           // 存在相同的key
    19.           if ((k = e.key) == key || (e.hash == hash && key.equals(k))) {
    20.               oldValue = e.value;
    21.               if (!onlyIfAbsent) {
    22.                   // 覆盖旧值
    23.                   e.value = value;
    24.                   ++modCount;
    25.               }
    26.               break;
    27.           }
    28.           // 迭代
    29.           e = e.next;
    30.       }
    31.       else {
    32.           // 如果node不为空，将其设置为链表头节点
    33.           if (node != null)
    34.               node.setNext(first);
    35.           // 如果node为空，初始化并将其设置为链表头节点
    36.           else
    37.               node = new HashEntry<K,V>(hash, key, value, first);
    39.           int c = count + 1;
    40.           // 如果超过了该segment的阈值，那么这个segment需要进行扩容
    41.           if (c > threshold && tab.length < MAXIMUM_CAPACITY)
    42.               rehash(node);
    43.           // 没有达到阈值，将node放到数组tab的index位置，
    44.           // 其实就是将新的节点设置成原链表的头节点
    45.           else
    46.               setEntryAt(tab, index, node);
    47.           ++modCount;
    48.           count = c;
    49.           oldValue = null;
    50.           break;
    51.       }
    52.   }
    53. } finally {
    54.   // 解锁
    55.   unlock();
    56. }
    57. return oldValue;
    58. }

    插槽操作通过独占锁的保护保证线程安全，先找到数组相应位置的链表头节点，为空则初始化并设置头节点，超过segment的阈值则需要扩容。
    其中的还有几步关键操作：
    （1）初始化槽
    ConcurrentHashMap初始化的时候会初始化第一个槽segment[0]，对于其他槽来说，在插入第一个值的时候进行初始化。这里需要考虑并发，对与每个线程先检查该槽是否被初始化，然后通过循环CAS操作直到成功为止。

    1. private Segment<K,V> ensureSegment(int k) {
    2. final Segment<K,V>[] ss = this.segments;
    3. long u = (k << SSHIFT) + SBASE; // raw offset
    4. Segment<K,V> seg;
    5. if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
    6.   // 这里使用当前segment[0]处的数组长度和负载因子来初始化segment[k]
    7.   // 使用当前是因为segment[0]可能已经扩容了
    8.   Segment<K,V> proto = ss[0];
    9.   int cap = proto.table.length;
    10.   float lf = proto.loadFactor;
    11.   int threshold = (int)(cap * lf);
    13.   // 初始化segment[k]内部的数组
    14.   HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
    16.   // 再次检查该槽是否被其他线程初始化
    17.   if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
    18.       == null) {
    20.       Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
    21.       // while+CAS设值成功后退出
    22.       while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
    23.              == null) {
    24.           if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
    25.               break;
    26.       }
    27.   }
    28. }
    29. return seg;
    30. }

    （2）获取写锁
    这个方法有两个出口，一个是tryLock成功，循环终止；另一个是通过MAX_SCAN_RETRIES控制自旋次数，失败则进入lock()方法，阻塞等待，直到成功拿到独占锁。

    1. private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
    2. // 获取数组相应位置的头节点
    3. HashEntry<K,V> first = entryForHash(this, hash);
    4. HashEntry<K,V> e = first;
    5. HashEntry<K,V> node = null;
    6. int retries = -1; // negative while locating node
    8. // 循环获取锁
    9. while (!tryLock()) {
    10.   HashEntry<K,V> f; // to recheck first below
    11.   if (retries < 0) {
    12.       if (e == null) {
    13.           // 链表为空或者tryLock失败
    14.           if (node == null) // 初始化node节点
    15.               node = new HashEntry<K,V>(hash, key, value, null);
    16.           retries = 0;
    17.       }
    18.       else if (key.equals(e.key))
    19.           retries = 0;
    20.       else
    21.           // 迭代
    22.           e = e.next;
    23.   }
    24.   // 如果重试次数如果超过MAX_SCAN_RETRIE（单核1多核64）
    25.   // 那么放弃抢锁，进入到阻塞队列等待锁
    26.   // lock()是阻塞方法，直到获取锁后返回
    27.   else if (++retries > MAX_SCAN_RETRIES) {
    28.       lock();
    29.       break;
    30.   }
    31.   // 如果有新的元素进入链表并成为新的头节点
    32.   // 那么重新获取头节点
    33.   else if ((retries & 1) == 0 &&
    34.            (f = entryForHash(this, hash)) != first) {
    35.       e = first = f; // re-traverse if entry changed
    36.       retries = -1;
    37.   }
    38. }
    39. return node;
    40. }

    （3）扩容
    segment数组不能扩容，扩容时segment数组某个位置内部的数组HashEntry[]进行扩容，扩容后容量加倍。这个方法不需要考虑并发，因为被调用的时候已经持有该segment的独占锁。

    1. // node是扩容时需要添加的新节点
    2. private void rehash(HashEntry<K,V> node) {
    3. HashEntry<K,V>[] oldTable = table;
    4. int oldCapacity = oldTable.length;
    5. // 扩容两倍
    6. int newCapacity = oldCapacity << 1;
    7. threshold = (int)(newCapacity * loadFactor);
    8. // 创建新数组
    9. HashEntry<K,V>[] newTable = (HashEntry<K,V>[]) new HashEntry[newCapacity];
    10. // 新的掩码，如从16扩容到32，那么sizeMask为31，对应二进制 ‘000...00011111’
    11. int sizeMask = newCapacity - 1;
    13. // 遍历数组
    14. // 将原数组i处的链表拆分到新数组位置i和i+oldCap两个位置
    15. for (int i = 0; i < oldCapacity ; i++) {
    16.   // e是链表的头节点
    17.   HashEntry<K,V> e = oldTable[i];
    18.   if (e != null) {
    19.       HashEntry<K,V> next = e.next;
    20.       // 计算放置的数组下标
    21.       int idx = e.hash & sizeMask;
    22.       // 该位置处为独狼
    23.       if (next == null)   
    24.           newTable[idx] = e;
    25.       else { // Reuse consecutive sequence at same slot
    26.           // e是链表表头
    27.           HashEntry<K,V> lastRun = e;
    28.           // idx 是当前链表的头结点 e 的新位置
    29.           int lastIdx = idx;
    31.           // 下面这个for循环会找到一个lastRun节点，这个节点之后的所有元素是将要放到一起的
    32.           for (HashEntry<K,V> last = next;
    33.                last != null;
    34.                last = last.next) {
    35.               int k = last.hash & sizeMask;
    36.               if (k != lastIdx) {
    37.                   lastIdx = k;
    38.                   lastRun = last;
    39.               }
    40.           }
    42.           // 将lastRun及其之后的所有节点组成的这个链表放到lastIdx这个位置
    43.           newTable[lastIdx] = lastRun;
    44.           // 下面的操作是处理lastRun之前的节点，
    45.           // 这些节点可能分配在另一个链表中，也可能分配到上面的那个链表中
    46.           for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
    47.               V v = p.value;
    48.               int h = p.hash;
    49.               int k = h & sizeMask;
    50.               HashEntry<K,V> n = newTable[k];
    51.               newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
    52.           }
    53.       }
    54.   }
    55. }
    56. // 将新节点放到新数组两个链表之一的头部
    57. int nodeIndex = node.hash & sizeMask; // add the new node
    58. node.setNext(newTable[nodeIndex]);
    59. newTable[nodeIndex] = node;
    60. // 赋值给原数组
    61. table = newTable;
    62. }

    put操作的线程安全性：

  • 初始化槽，使用while循环+CAS操作来初始化Segment中的数组。
  • 头插法。所以，这个时候，get操作在链表遍历的过程以及该到了中间，是不会影响的。另一个并发问题是get操作在put之后，需要保证刚刚插入表头的节点被读取，这个依赖于setEntryAt方法中使用的UNSAFE.putOrderedObject。
  • 扩容操作。扩容是新创建了数组，然后进行数据迁移，最后将newTable赋值给table。所以，如果get操作此时也在进行，那么也没关系，如果get先行，那么就是在旧的table进行查询；如果put先行，那么volatile可以保证可见性。

get过程

get过程比较简单：
（1）计算hash值
（2）根据hash值找到相应的Segment
（3）找到Segment相应位置的链表进行遍历

  1. public V get(Object key) {
  2.     Segment<K,V> s; // manually integrate access methods to reduce overhead
  3.     HashEntry<K,V>[] tab;
  4.     // 1. 计算hash值
  5.     int h = hash(key);
  6.     long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
  7.     // 2. 根据hash值找到对应的segment
  8.     if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
  9.         (tab = s.table) != null) {
  10.         // 3. 找到segment内部素组相应位置的链表，遍历
  11.         for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
  12.                  (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
  13.              e != null; e = e.next) {
  14.             K k;
  15.             if ((k = e.key) == key || (e.hash == h && key.equals(k)))
  16.                 return e.value;
  17.         }
  18.     }
  19.     return null;
  20. }

JDK1.8

4.png

put过程

流程如下：
（1）计算key的hash值。
（2）通过无限循环+CAS插入节点。
（3）如果数组为空，进行数组初始化。
（4）如果数组非空，则计算hash值对应下标，得到相应位置的第一节点。

  1. 如果第一节点为空，用一次CAS操作将这个新节点放在该位置即可；
  2. 如果CAS操作失败，说明存在并发操作，进入下一轮循环。

（6）如果hash值为MOVED，说明在进行扩容操作，然后帮助数据迁移。
（7）如果第一节点不为空，对第一节点加synchonized锁。

  1. 如果hash值大于0，说明是链表。直接遍历链表，若存在相同key则进行值覆盖，然后break。
  2. 如果节点类型为树节点，则调用红黑树的插值方法插入新节点。

（8）判断链表长度是否超过扩容阈值8并且数组长度大于64，是则进行树化操作。
（9）判断是否产生了值覆盖，是则返回旧值，否则返回null。

  1. final V putVal(K key, V value, boolean onlyIfAbsent) {
  2.     if (key == null || value == null) throw new NullPointerException();
  3.     // 计算hash值
  4.     int hash = spread(key.hashCode());
  5.     // 用于记录相应链表的长度
  6.     int binCount = 0;
  7.     for (Node<K,V>[] tab = table;;) {
  8.         Node<K,V> f; int n, i, fh;
  9.         // 如果数组为空，则进行数组初始化
  10.         if (tab == null || (n = tab.length) == 0)
  11.             tab = initTable();
  12.         // 如果数组不为空，则找到hash值对应的数组下标，得到第一个节点
  13.         // 如果第一个节点为空
  14.         else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
  15.             // 用一次CAS操作将这个新值放在该位置即可
  16.             // 如果CAS失败，说明存在并发操作，进入下一轮循环
  17.             if (casTabAt(tab, i, null,
  18.                          new Node<K,V>(hash, key, value, null)))
  19.                 break;                   // no lock when adding to empty bin
  20.         }
  21.         // 如果hash值为MOVED，说明在扩容
  22.         else if ((fh = f.hash) == MOVED)
  23.             // 帮助数据迁移
  24.             tab = helpTransfer(tab, f);
  25.         // 如果第一个节点不为空
  26.         else {
  27.             V oldVal = null;
  28.             // 对第一个节点加锁
  29.             synchronized (f) {
  30.                 if (tabAt(tab, i) == f) {
  31.                     // hash值大于0，说明是链表
  32.                     if (fh >= 0) {
  33.                         // 记录链表长度
  34.                         binCount = 1;
  35.                         for (Node<K,V> e = f;; ++binCount) {
  36.                             K ek;
  37.                             // 发现相等的key则进行值覆盖，然后break
  38.                             if (e.hash == hash &&
  39.                                 ((ek = e.key) == key ||
  40.                                  (ek != null && key.equals(ek)))) {
  41.                                 oldVal = e.val;
  42.                                 if (!onlyIfAbsent)
  43.                                     e.val = value;
  44.                                 break;
  45.                             }
  46.                             // 到达链表最末端，将新值放到链表的最后面
  47.                             Node<K,V> pred = e;
  48.                             if ((e = e.next) == null) {
  49.                                 pred.next = new Node<K,V>(hash, key,
  50.                                                           value, null);
  51.                                 break;
  52.                             }
  53.                         }
  54.                     }
  55.                     // 第一个节点类型位红黑树节点
  56.                     else if (f instanceof TreeBin) {
  57.                         Node<K,V> p;
  58.                         binCount = 2;
  59.                         // 调用红黑树的插值方法插入新节点
  60.                         if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
  61.                                                               value)) != null) {
  62.                             oldVal = p.val;
  63.                             if (!onlyIfAbsent)
  64.                                 p.val = value;
  65.                         }
  66.                     }
  67.                 }
  68.             }
  69.             if (binCount != 0) {
  70.                 // 链表长度超过扩容阈值8，进行树化操作
  71.                 if (binCount >= TREEIFY_THRESHOLD)
  72.                     // 如果当前数组长度<64，进行数组扩容，不会树化
  73.                     treeifyBin(tab, i);
  74.                 // 存在值覆盖，返回旧值
  75.                 if (oldVal != null)
  76.                     return oldVal;
  77.                 break;
  78.             }
  79.         }
  80.     }
  81.     addCount(1L, binCount);
  82.     return null;
  83. }

其中的还有几步关键操作：
（1）数据初始化
初始化一个合适大小的数组，然后设置sizeCtl。
并发问题是通过对sizeCtl进行CAS操作来控制的。

  1. private final Node<K,V>[] initTable() {
  2.     Node<K,V>[] tab; int sc;
  3.     while ((tab = table) == null || tab.length == 0) {
  4.         // 已经被其他线程初始化
  5.         if ((sc = sizeCtl) < 0)
  6.             Thread.yield(); // lost initialization race; just spin
  7.         // 通过CAS操作将sizeCtl设置为-1，代表抢锁成功
  8.         else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
  9.             try {
  10.                 if ((tab = table) == null || tab.length == 0) {
  11.                     // DEFAULT_CAPACITY默认初始容量是16
  12.                     int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
  13.                     @SuppressWarnings("unchecked")
  14.                     Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
  15.                     // 将这个数组赋值给table，table是volatile的
  16.                     table = tab = nt;
  17.                     // 如果n为16的话，那么这里sc=12
  18.                     // 其实就是0.75 * n
  19.                     sc = n - (n >>> 2);
  20.                 }
  21.             } finally {
  22.                 // 设置sizeCtl为sc
  23.                 sizeCtl = sc;
  24.             }
  25.             break;
  26.         }
  27.     }
  28.     return tab;
  29. }

（2）链表转红黑树

  1. private final void treeifyBin(Node<K,V>[] tab, int index) {
  2.     Node<K,V> b; int n, sc;
  3.     if (tab != null) {
  4.         // MIN_TREEIFY_CAPACITY 为 64
  5.         // 所以，如果数组长度小于64的时候，其实也就是32或者16或者更小的时候，会进行数组扩容
  6.         if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
  7.             tryPresize(n << 1);
  8.         // b是头节点
  9.         else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
  10.             // 加锁
  11.             synchronized (b) {
  12.                 if (tabAt(tab, index) == b) {
  13.                     // 遍历链表，建立一颗红黑树
  14.                     TreeNode<K,V> hd = null, tl = null;
  15.                     for (Node<K,V> e = b; e != null; e = e.next) {
  16.                         TreeNode<K,V> p =
  17.                             new TreeNode<K,V>(e.hash, e.key, e.val,
  18.                                               null, null);
  19.                         if ((p.prev = tl) == null)
  20.                             hd = p;
  21.                         else
  22.                             tl.next = p;
  23.                         tl = p;
  24.                     }
  25.                     // 将红黑树设置到数组相应位置中
  26.                     setTabAt(tab, index, new TreeBin<K,V>(hd));
  27.                 }
  28.             }
  29.         }
  30.     }
  31. }

（3）扩容

  1. // 这里的size已经加倍
  2. private final void tryPresize(int size) {
  3.     // 取size的1.5倍，再加1，再往上取最近的2的n次方
  4.     int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
  5.     tableSizeFor(size + (size >>> 1) + 1);
  6.     int sc;
  7.     while ((sc = sizeCtl) >= 0) {
  8.         Node<K,V>[] tab = table; int n;
  9.         if (tab == null || (n = tab.length) == 0) {
  10.             n = (sc > c) ? sc : c;
  11.             // 这个if分支和之前说的初始化数组的代码基本上是一样的
  12.             if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
  13.                 try {
  14.                     if (table == tab) {
  15.                         @SuppressWarnings("unchecked")
  16.                         Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
  17.                         table = nt;
  18.                         sc = n - (n >>> 2);
  19.                     }
  20.                 } finally {
  21.                     sizeCtl = sc;
  22.                 }
  23.             }
  24.         }
  25.         else if (c <= sc || n >= MAXIMUM_CAPACITY)
  26.             break;
  27.         else if (tab == table) {
  28.             int rs = resizeStamp(n);
  29.             if (sc < 0) {
  30.                 Node<K,V>[] nt;
  31.                 if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
  32.                     sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
  33.                     transferIndex <= 0)
  34.                     break;
  35.                 // 用CAS将sizeCtl加1，然后执行transfer
  36.                 if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
  37.                     transfer(tab, nt);
  38.             }
  39.             // 调用transfer方法进行数据迁移
  40.             else if (U.compareAndSwapInt(this, SIZECTL, sc,
  41.                                          (rs << RESIZE_STAMP_SHIFT) + 2))
  42.                 transfer(tab, null);
  43.         }
  44.     }
  45. }

（4）数据迁移
方法很长，主要是将原来的tab元素迁移到新的nextTab数组中

  1. private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
  2.     int n = tab.length, stride;
  4.     // stride在单核下直接等于n，多核模式下为 (n >>> 3) /NCPU，最小值是16
  5.     if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
  6.         stride = MIN_TRANSFER_STRIDE; // subdivide range
  7.     if (nextTab == null) {            // initiating
  8.         try {
  9.             @SuppressWarnings("unchecked")
  10.             Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
  11.             nextTab = nt;
  12.         } catch (Throwable ex) {      // try to cope with OOME
  13.             sizeCtl = Integer.MAX_VALUE;
  14.             return;
  15.         }
  16.         nextTable = nextTab;
  17.         transferIndex = n;
  18.     }
  19.     int nextn = nextTab.length;
  20.     ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
  21.     boolean advance = true;
  22.     boolean finishing = false; // to ensure sweep before committing nextTab
  23.     for (int i = 0, bound = 0;;) {
  24.         Node<K,V> f; int fh;
  25.         while (advance) {
  26.             int nextIndex, nextBound;
  27.             if (--i >= bound || finishing)
  28.                 advance = false;
  29.             else if ((nextIndex = transferIndex) <= 0) {
  30.                 i = -1;
  31.                 advance = false;
  32.             }
  33.             else if (U.compareAndSwapInt
  34.                      (this, TRANSFERINDEX, nextIndex,
  35.                       nextBound = (nextIndex > stride ?
  36.                                    nextIndex - stride : 0))) {
  37.                 bound = nextBound;
  38.                 i = nextIndex - 1;
  39.                 advance = false;
  40.             }
  41.         }
  42.         if (i < 0 || i >= n || i + n >= nextn) {
  43.             int sc;
  44.             if (finishing) {
  45.                 nextTable = null;
  46.                 table = nextTab;
  47.                 sizeCtl = (n << 1) - (n >>> 1);
  48.                 return;
  49.             }
  50.             if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
  51.                 if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
  52.                     return;
  53.                 finishing = advance = true;
  54.                 i = n; // recheck before commit
  55.             }
  56.         }
  57.         else if ((f = tabAt(tab, i)) == null)
  58.             advance = casTabAt(tab, i, null, fwd);
  59.         else if ((fh = f.hash) == MOVED)
  60.             advance = true; // already processed
  61.         else {
  62.             synchronized (f) {
  63.                 if (tabAt(tab, i) == f) {
  64.                     Node<K,V> ln, hn;
  65.                     if (fh >= 0) {
  66.                         int runBit = fh & n;
  67.                         Node<K,V> lastRun = f;
  68.                         for (Node<K,V> p = f.next; p != null; p = p.next) {
  69.                             int b = p.hash & n;
  70.                             if (b != runBit) {
  71.                                 runBit = b;
  72.                                 lastRun = p;
  73.                             }
  74.                         }
  75.                         if (runBit == 0) {
  76.                             ln = lastRun;
  77.                             hn = null;
  78.                         }
  79.                         else {
  80.                             hn = lastRun;
  81.                             ln = null;
  82.                         }
  83.                         for (Node<K,V> p = f; p != lastRun; p = p.next) {
  84.                             int ph = p.hash; K pk = p.key; V pv = p.val;
  85.                             if ((ph & n) == 0)
  86.                                 ln = new Node<K,V>(ph, pk, pv, ln);
  87.                             else
  88.                                 hn = new Node<K,V>(ph, pk, pv, hn);
  89.                         }
  90.                         setTabAt(nextTab, i, ln);
  91.                         setTabAt(nextTab, i + n, hn);
  92.                         setTabAt(tab, i, fwd);
  93.                         advance = true;
  94.                     }
  95.                     else if (f instanceof TreeBin) {
  96.                         TreeBin<K,V> t = (TreeBin<K,V>)f;
  97.                         TreeNode<K,V> lo = null, loTail = null;
  98.                         TreeNode<K,V> hi = null, hiTail = null;
  99.                         int lc = 0, hc = 0;
  100.                         for (Node<K,V> e = t.first; e != null; e = e.next) {
  101.                             int h = e.hash;
  102.                             TreeNode<K,V> p = new TreeNode<K,V>
  103.                                 (h, e.key, e.val, null, null);
  104.                             if ((h & n) == 0) {
  105.                                 if ((p.prev = loTail) == null)
  106.                                     lo = p;
  107.                                 else
  108.                                     loTail.next = p;
  109.                                 loTail = p;
  110.                                 ++lc;
  111.                             }
  112.                             else {
  113.                                 if ((p.prev = hiTail) == null)
  114.                                     hi = p;
  115.                                 else
  116.                                     hiTail.next = p;
  117.                                 hiTail = p;
  118.                                 ++hc;
  119.                             }
  120.                         }
  121.                         ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
  122.                         (hc != 0) ? new TreeBin<K,V>(lo) : t;
  123.                         hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
  124.                         (lc != 0) ? new TreeBin<K,V>(hi) : t;
  125.                         setTabAt(nextTab, i, ln);
  126.                         setTabAt(nextTab, i + n, hn);
  127.                         setTabAt(tab, i, fwd);
  128.                         advance = true;
  129.                     }
  130.                 }
  131.             }
  132.         }
  133.     }
  134. }