1.源码文档相关说明
参考先前ConcurrentHashMap类实现说明翻译：
Each bin transfer requires its bin lock, which can stall
waiting for locks while resizing. However, because other
threads can join in and help resize rather than contend for
locks, average aggregate waits become shorter as resizing
progresses. The transfer operation must also ensure that all
accessible bins in both the old and new table are usable by any
traversal. This is arranged in part by proceeding from the
last bin (table.length - 1) up towards the first.
Upon seeing
a forwarding node, traversals (see class Traverser) arrange to
move to the new table without revisiting nodes. To ensure that
no intervening nodes are skipped even when moved out of order,
a stack (see class TableStack) is created on first encounter of
a forwarding node during a traversal, to maintain its place if
later processing the current table. The need for these
save/restore mechanics is relatively rare, but when one
forwarding node is encountered, typically many more will be.
So Traversers use a simple caching scheme to avoid creating so
many new TableStack nodes. (Thanks to Peter Levart for
suggesting use of a stack here.)
多线程协助扩容会使得锁等待时间变短。transfer操作必须保证在新表和旧表所有可访问的桶能被任何遍历使用。最后一个桶向上指向第一个桶。
当看到一个forwarding结点，遍历会被安排到新表。为了确保在无序移动中不会跳过中间结点，在遍历期间首次遇到forwarding结点时会创建一个TableStack，以便在以后处理当前表时保持其位置。
对保存/恢复机制的需求相对较少，但是当遇到一个forwarding时，通常会有更多forwarding。Traverser使用了一个简单的缓存机制避免创建过多新的TableStack结点。
2.遍历的源码
final Node<K,V> advance() {
Node<K,V> e;
if ((e = next) != null)
e = e.next;
for (;;) {
Node<K,V>[] t; int i, n; // must use locals in checks
if (e != null)
return next = e;
if (baseIndex >= baseLimit || (t = tab) == null ||
(n = t.length) <= (i = index) || i < 0)
return next = null;
if ((e = tabAt(t, i)) != null && e.hash < 0) {
if (e instanceof ForwardingNode) {
tab = ((ForwardingNode<K,V>)e).nextTable;
e = null;
pushState(t, i, n);
continue;
}
else if (e instanceof TreeBin)
e = ((TreeBin<K,V>)e).first;
else
e = null;
}
if (stack != null)
recoverState(n);
else if ((index = i + baseSize) >= n)
index = ++baseIndex; // visit upper slots if present
}
}
pushState()源码，压入当前的状态：
/**
* Saves traversal state upon encountering a forwarding node.
*/
private void pushState(Node<K,V>[] t, int i, int n) {
TableStack<K,V> s = spare; // reuse if possible
if (s != null)
spare = s.next;
else
s = new TableStack<K,V>();
s.tab = t;
s.length = n;
s.index = i;
s.next = stack;
stack = s;
}
recoverState出栈，恢复之前的状态：
private void recoverState(int n) {
TableStack<K,V> s; int len;
while ((s = stack) != null && (index += (len = s.length)) >= n) {
n = len;
index = s.index;
tab = s.tab;
s.tab = null;
TableStack<K,V> next = s.next;
s.next = spare; // save for reuse
stack = next;
spare = s;
}
if (s == null && (index += baseSize) >= n)
index = ++baseIndex;
}
为了与扩容操作并发执行，遍历操作执行步骤如下：
- step1. 从前往后逐个访问每个bin
- step2. 如果遇到FordwardingNode，则把当前table引用、当前bin的访问位置和当前table总长度保存到table stack中，然后跳转到FordwardingNode所指向的新table
- step3. 当前的索引index保持不变，在新table中按这个index访问（因为map每次扩容都是大小扩展为原来的2倍，每个Node在新table中的索引要么保持不变要么后移baseSize）
- step4. 访问完新table中的index位置的bin之后，再访问index+baseSize这个位置上的bin (baseSize是老table的总长度)；这也是为什么recoverState要加一个条件：(index += (len = s.length)) >= n的原因。
- step5. 从table stack还原出之前的table引用、index访问位置和table总长度，继续向后遍历。
这样就可以在有扩容操作在进行的条件下，同时并发支持遍历操作，且保证每个Node只被访问一次。因为Node在老table和新table之间有固定对应关系。
