只允许一个线程对表进行初始化，若不巧有其他线程进来了，则会让其他线程交出 CPU 等待下次系统调度。这保证了表同时只会被一个线程初始化。
//检测到桶结点是 ForwardingNode 类型，协助扩容 else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f);
//桶结点是普通的结点，锁住该桶头结点并试图在该链表的尾部添加一个节点 else { V oldVal = null; synchronized (f) { if (tabAt(tab, i) == f) { //向普通的链表中添加元素 if (fh >= 0) { binCount = 1; for (Node<K,V> e = f;; ++binCount) { K ek; if (e.hash == hash &&((ek = e.key) == key ||(ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node<K,V> pred = e; if ((e = e.next) == null) { pred.next = new Node<K,V>(hash, key,value, null); break; } } } //向红黑树中添加元素，TreeBin 结点的hash值为TREEBIN（-2） else if (f instanceof TreeBin) { Node<K,V> p; binCount = 2; if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } } } //binCount != 0 说明向链表或者红黑树中添加或修改一个节点成功 //binCount == 0 说明 put 操作将一个新节点添加成为某个桶的首节点 if (binCount != 0) { //链表深度超过 8 转换为红黑树 if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); //oldVal != null 说明此次操作是修改操作 //直接返回旧值即可，无需做下面的扩容边界检查 if (oldVal != null) return oldVal; break; } } } //CAS 式更新baseCount，并判断是否需要扩容 addCount(1L, binCount); //程序走到这一步说明此次 put 操作是一个添加操作，否则早就 return 返回了 return null;
注意ForwardingNode 节点类型
这个节点内部保存了一个 nextTable 引用，它指向一张 hash 表;
在扩容操作中，我们需要对每个桶中的结点进行分离和转移;
如果某个桶结点中所有节点都已经迁移完成了(已经被转移到新表 nextTable);
那么会在原 table 表的该位置挂上一个 ForwardingNode 结点，说明此桶已经完成迁移.
ForwardingNode继承自 Node 结点,并且它唯一的构造函数将构建一个k/v/next 都为 null 的结点,反正它就是个标识，无需那些属性;
但是 hash 值却为 MOVED.
所以，我们在 putVal 方法中遍历整个 hash 表的桶结点,如果遇到 hash 值等于 MOVED,说明已经有线程正在扩容 rehash 操作,整体上还未完成，,过我们要插入的桶的位置已经完成了所有节点的迁移
由于检测到当前哈希表正在扩容,于是让当前线程去协助扩容.
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) { Node<K,V>[] nextTab; int sc; if (tab != null && (f instanceof ForwardingNode) && (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) { //返回一个 16 位长度的扩容校验标识 int rs = resizeStamp(tab.length); while (nextTab == nextTable && table == tab && (sc = sizeCtl) < 0) { //sizeCtl 如果处于扩容状态的话 //前 16 位是数据校验标识，后 16 位是当前正在扩容的线程总数 //这里判断校验标识是否相等，如果校验符不等或者扩容操作已经完成了，直接退出循环，不用协助它们扩容了 if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || transferIndex <= 0) break; //否则调用 transfer 帮助它们进行扩容 //sc + 1 标识增加了一个线程进行扩容 if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) { transfer(tab, nextTab); break; } } return nextTab; } return table; }
下面我们看这个稍显复杂的 transfer 方法，我们依然分几个部分来细说。
//第一部分 /** * Moves and/or copies the nodes in each bin to new table. See * above for explanation. */ private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) { int n = tab.length, stride; //计算单个线程允许处理的最少table桶首节点个数，不能小于 16 if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE) stride = MIN_TRANSFER_STRIDE; // subdivide range 细分范围 //刚开始扩容，初始化 nextTab if (nextTab == null) { // initiating try { @SuppressWarnings("unchecked") Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1]; nextTab = nt; } catch (Throwable ex) { sizeCtl = Integer.MAX_VALUE; return; } nextTable = nextTab; //transferIndex 指向最后一个桶，方便从后向前遍历 transferIndex = n; } int nextn = nextTab.length; //定义 ForwardingNode 用于标记迁移完成的桶 ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
这部分代码还是比较简单的，主要完成的是对单个线程能处理的最少桶结点个数的计算和一些属性的初始化操作。
//第二部分，并发扩容控制的核心 boolean advance = true; boolean finishing = false; // to ensure sweep before committing nextTab //i 指向当前桶，bound 指向当前线程需要处理的桶结点的区间下限 for (int i = 0, bound = 0;;) { Node<K,V> f; int fh; //这个 while 循环的目的就是通过 --i 遍历当前线程所分配到的桶结点 //一个桶一个桶的处理 while (advance) { int nextIndex, nextBound; if (--i >= bound || finishing) advance = false; //transferIndex <= 0 说明已经没有需要迁移的桶了 else if ((nextIndex = transferIndex) <= 0) { i = -1; advance = false; } //更新 transferIndex //为当前线程分配任务，处理的桶结点区间为（nextBound,nextIndex） else if (U.compareAndSwapInt(this, TRANSFERINDEX, nextIndex,nextBound = (nextIndex > stride ? nextIndex - stride : 0))) { bound = nextBound; i = nextIndex - 1; advance = false; } } //当前线程所有任务完成 if (i < 0 || i >= n || i + n >= nextn) { int sc; if (finishing) { nextTable = null; table = nextTab; sizeCtl = (n << 1) - (n >>> 1); return; } if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) { if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT) return; finishing = advance = true; i = n; } } //待迁移桶为空，那么在此位置 CAS 添加 ForwardingNode 结点标识该桶已经被处理过了 else if ((f = tabAt(tab, i)) == null) advance = casTabAt(tab, i, null, fwd); //如果扫描到 ForwardingNode，说明此桶已经被处理过了，跳过即可 else if ((fh = f.hash) == MOVED) advance = true;
每个新参加进来扩容的线程必然先进 while 循环的最后一个判断条件中去领取自己需要迁移的桶的区间。然后 i 指向区间的最后一个位置，表示迁移操作从后往前的做。接下来的几个判断就是实际的迁移结点操作了。等我们大致介绍完成第三部分的源码再回来对各个判断条件下的迁移过程进行详细的叙述。
//第三部分 else { // synchronized (f) { if (tabAt(tab, i) == f) { Node<K,V> ln, hn; //链表的迁移操作 if (fh >= 0) { int runBit = fh & n; Node<K,V> lastRun = f; //整个 for 循环为了找到整个桶中最后连续的 fh & n 不变的结点 for (Node<K,V> p = f.next; p != null; p = p.next) { int b = p.hash & n; if (b != runBit) { runBit = b; lastRun = p; } } if (runBit == 0) { ln = lastRun; hn = null; } else { hn = lastRun; ln = null; } //如果fh&n不变的链表的runbit都是0，则nextTab[i]内元素ln前逆序，ln及其之后顺序 //否则，nextTab[i+n]内元素全部相对原table逆序 //这是通过一个节点一个节点的往nextTab添加 for (Node<K,V> p = f; p != lastRun; p = p.next) { int ph = p.hash; K pk = p.key; V pv = p.val; if ((ph & n) == 0) ln = new Node<K,V>(ph, pk, pv, ln); else hn = new Node<K,V>(ph, pk, pv, hn); } //把两条链表整体迁移到nextTab中 setTabAt(nextTab, i, ln); setTabAt(nextTab, i + n, hn); //将原桶标识位已经处理 setTabAt(tab, i, fwd); advance = true; } //红黑树的复制算法，不再赘述 else if (f instanceof TreeBin) { TreeBin<K,V> t = (TreeBin<K,V>)f; TreeNode<K,V> lo = null, loTail = null; TreeNode<K,V> hi = null, hiTail = null; int lc = 0, hc = 0; for (Node<K,V> e = t.first; e != null; e = e.next) { int h = e.hash; TreeNode<K,V> p = new TreeNode<K,V>(h, e.key, e.val, null, null); if ((h & n) == 0) { if ((p.prev = loTail) == null) lo = p; else loTail.next = p; loTail = p; ++lc; } else { if ((p.prev = hiTail) == null) hi = p; else hiTail.next = p; hiTail = p; ++hc; } } ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :(hc != 0) ? new TreeBin<K,V>(lo) : t; hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :(lc != 0) ? new TreeBin<K,V>(hi) : t; setTabAt(nextTab, i, ln); setTabAt(nextTab, i + n, hn); setTabAt(tab, i, fwd); advance = true; }
那么至此，有关迁移的几种情况已经介绍完成了，下面我们整体上把控一下整个扩容和迁移过程.
首先，每个线程进来会先领取自己的任务区间，然后开始 --i 来遍历自己的任务区间，对每个桶进行处理。
- 如果遇到桶的头结点是空的,那么使用 ForwardingNode 标识该桶已经被处理完成了
- 如果遇到已经处理完成的桶,直接跳过进行下一个桶的处理
- 如果是正常的桶,对桶首节点加锁,正常的迁移即可,迁移结束后依然会将原表的该位置标识位已经处理
当 i < 0，说明本线程处理速度够快的，整张表的最后一部分已经被它处理完了，现在需要看看是否还有其他线程在自己的区间段还在迁移中。这是退出的逻辑判断部分：
