共计 6517 个字符，预计需要花费 17 分钟才能阅读完成。
ConcurrentHashMap 源码目前在网络上已有泛滥解析。本文章次要关注其基于 Traverser 的遍历实现，试图认真解析该实现，如有错漏，请斧正。
ConcurrentHashMap 的 Traverser 次要是用于外部数组的遍历性能反对，如何实现在外部数组扩容阶段期间，其余线程也可能正确地遍历输入，并保障良好的性能（不应用各种锁），Traverser 提供了一个优良的设计实现。
1. 相干概念
2. 解析
1. 相干概念
1.1 ConcurrentHashMap 反对办法 forEach(Consumer<? super K> action)、keys、elements、contains 等办法，它们的外部实现都基于 Traverser；
1.2 ConcurrentHashMap 的遍历可能保障在外部数组扩容期间，也具备优良的性能和并发安全性。
1.3 Traverser 的次要办法：advance，其示意为：推动，与扩容期间时的 boolean 变量 advance 具备类似的意义，都是推动索引 （index） 的增长，以便继续向前推动元素定位。
1.4 了解在 类 Traverser 中的变量的命名，有利于对实现的了解，如：baseXxx 的变量是针对 ConcurrentHashMap 中的旧表，没有 base- 前缀的则同时针对旧表与新表（以后遍历上下文）。
2. 解析
2.1 ConcurrentHashMap 对立了遍历的根底实现，即：Traverser 负责元素推动，并将元素返回；而 BaseIterator 则负责对元素进行判断，并提供迭代实现：hasNext、next；XxxIterator 则是基于 BaseIterator 提供不同的实现：针对 keys 的迭代、针对 value 的迭代、针对 entry 的迭代。
2.2 Traverser 类放弃了迭代的索引：index，和对所在 ConcurrentHashMap 的外部数组—— 可能是旧表，也可能是新表的援用
static class Traverser<K,V> {
// 默认是以后 table，如果正在重组，则会被间断性替换为 nextTable
Node<K,V>[] tab; // current table; updated if resized
// next 是一个要害的根底变量，作为迭代中的以后元素，次要实现：next() 和 hasNext()
Node<K,V> next; // the next entry to use
// 为了达到复用成果，应用一个 TableStack 在 这两个变量之间互相替换
TableStack<K,V> stack, spare; // to save/restore on ForwardingNodes 保留或复原
// 真正遍历时的索引，有可能重复横跳，默认应用中为 index，而在 resize 中，则可能是 index、baseIndex+baseSize（因为翻倍）int index; // index of bin to use next
/**
* base* 是基于旧 tab（如果扩容，则存在 新 tab）* baseIndex 是在旧 tab 上的偏移
* baseSize 是旧 tab 的大小
* baseLimit 是要遍历的区间范畴（也就是必定是 limit <= size）*/
int baseIndex; // current index of initial table
int baseLimit; // index bound for initial table
final int baseSize; // initial table size
Traverser(Node<K,V>[] tab, int size, int index, int limit) {
this.tab = tab;
this.baseSize = size;
this.baseIndex = this.index = index;
this.baseLimit = limit;
this.next = null;
}
// ...
} 在 Traverser 的构造方法中，目前的援用，都是 limit = size，也就是说，目前被援用的中央，都是对整个外部数组进行迭代，区间管制在 0 ~ limit = size。
2.3 Traverser 的裸露的办法（修饰符为 default），只有：advance。
advance 负责推动元素，在扩容阶段，也可能让索引到新表中进行元素遍历。
final Node<K,V> advance() {
Node<K,V> e;
// 这是推动胜利（索引减少）让内部获取到元素后，内部从新进入的流程
// 尝试赋值为 e.next，如果不为 null，则进行链表的迭代或树的遍历，不推动到下一节点
if ((e = next) != null)
e = e.next;
for (;;) {
// t -> table，要遍历的 table
// i -> index；n -> length/number
Node<K,V>[] t; int i, n; // must use locals in checks
// 曾经在上一步赋值为 e.next，进行迭代，如果为 null，才推动下一节点
if (e != null)
return next = e;
/**
* baseIndex >= baseLimit 最开始传入的 index 就超过 limit，显然是不正确的，间接返回 null
* 边界判断，这里的 tab 有可能即是 old table 也有可能是 nextTable，* 这也导致 n 的值重复横跳，有时是 old table 的长度，有时是 nextTable 的长度
* 但 t.length（新旧表的大小）总会比以后正在遍历的偏移 index 大。* 并且上面的判断：(index = i + baseSize) >= n 是有可能成立的
*/
if (baseIndex >= baseLimit || (t = tab) == null ||
(n = t.length) <= (i = index) || i < 0)
return next = null;
/**
* 如果节点的 哈希 < 0，有多种状况：* 一是判断是否正在重组（在重组中被转移了）* 如果是 ForwardingNode(hash=-1) 阐明该旧表节点曾经在重组中被转移了，* 应用的算法是：对于曾经挪动的节点（ForwardingNode），换到新表（nextTable），index 放弃不变，* continue 跳出，筹备到新表进行迭代
* 存储信息到 长期 stack 中
* 将该节点的索引推入到栈中，并更新遍历的表格为 nextTable，从新进入（index 不变），* 则 tabAt(t,i)
* 下轮遍历开始，tabAt 曾经是针对 nextTable，此时不再可能是 ForwardingNode，在 nextTable 遍历完后
* 回来通过 recoverState 将 tab 从新替换为 旧 table，并推动索引
* 二是：标识该节点是树节点，是则获取树结构的 first 节点，并向下执行，在 recoverState 中，将 index = index+baseSize
* 也就是，将 index 跨幅度减少为元素索引在新表中 rehash 后的地位，以便下次循环从该地位开始
* 总结：也就是说，在旧表遇到 ForwardingNode 后，遍历将切换到新表，* 对索引 index 和 baseIndex + baseSize 上的元素进行遍历
*/
if ((e = tabAt(t, i)) != null && e.hash < 0) {if (e instanceof ForwardingNode) {tab = ((ForwardingNode<K,V>)e).nextTable;
// 赋值为 null，并 continue，以便去进行 recoverState 操作
e = null;
// 保留长期信息（以后索引到的地位、旧表大小、旧表援用）pushState(t, i, n);
// 假如在这里，扩容阶段被实现了，将呈现什么状况？continue;
}
// 树节点类型的 hash 也为正数：-2
else if (e instanceof TreeBin)
e = ((TreeBin<K,V>)e).first;
else
e = null;
}
/**
* 无论如何，程序总是会跑到此判断上。* 如果 stack 不为 null，阐明索引 i 曾经被扩容进行过 rehash，* 那么就须要遍历完新表上的索引：baseIndex 和 baseIndex+baseSize，* 再从新赋值会旧表，从 ++baseIndex 开始
*/
if (stack != null)
// 辅助跳到新表的 2 倍 index 地位
recoverState(n);
else if ((index = i + baseSize) >= n)
// 超过 n（tab 大小，复原为基于旧表偏移的大小并加 1）// 如果呈现此状况，拜访回旧槽
index = ++baseIndex; // visit upper slots if present
}
}
简化形容迭代的代码：
A. 遍历器进行一般的遍历，通过索引的增长（+1），来获取节点，节点可能为 链表构造、树节点、null。如果为链表节点，则须要当初该索引上进行：e.next 获取节点的下一节点直到为 null，才推动 index；如果为 树节点，则须要获取 e.first，而后再通过 e.next 获取下一个树节点，直到为 null；如果为 null，则间接推动 index。
B. 遍历过程中，如果节点为 ForwardingNode（不是以上三种类型），则将以后遍历的数据（或称旧表）替换为新数组（新表），并将以后遍历的信息保存起来，次要有：以后在旧表上遍历的索引、旧表、旧表大小。
C. 基于新表，先在新表上对索引 baseIndex 进行第一步的节点获取，而后通过 recoverState 对索引进行推动，推动算法为：index = baseIndex + baseSize。因为在 ConcurrentHashMap 中，扩容的新数组大小为：2 * 旧表大小。
D. 基于新表，对 baseIndex + baseSize 上的元素获取应用实现后，推动索引，此时算法中将比拟，此次推动的大小是否超过新表大小，如是，则将长期信息复原，从新回到旧表上进行遍历。推动算法为：
/** * n 总是为新表大小，即：2 * baseSize
* Possibly pops traversal state.
*
* @param n length of current table */
private void recoverState(int n) {
// ...// s == null 作为先决条件，示意退回旧表进行操作
if (s == null && (index += baseSize) >= n)
index = ++baseIndex;
} E. 最终，是通过边界判断让遍历器退出。
2.4 advance 实现了在新旧表间切换遍历的实现，次要是借助于两个办法：pushState、recoverState。其中，pushState 次要是负责存储长期信息，而 recoverState 则负责：当表处于新表时，辅组推动索引跨幅度增长，同时还负责切换为旧表时，将索引回退为旧表的索引地位并 +1.
/**
* <pre>
* 为了达到复用的成果，* spare 总是被清理，称为 null，在 recoverState 中将被赋值一个清空的 stack
* stack 总是被负责，以便在 recoverState 被应用，而后进行清空，等下次 pushState 被从新赋值 spare
* </pre>
* Saves traversal state upon encountering a forwarding node.
*/
private void pushState(Node<K,V>[] t, int i, int n) {
// spare 备用
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 存储了节点
stack = s;
}
/**
* n 总是为新表大小，即：2 * baseSize
* Possibly pops traversal state.
*
* @param n length of current table
*/
private void recoverState(int n) {
TableStack<K,V> s; int len;
// 此办法的第一次是为 index 提供跨幅度减少，调整 index = baseIndex + baseSize
// 此时的 index 总是 < n 的，所以循环不成立，退出到内部办法进行元素获取
// 第二次，此时 index + baseSize = 2*baseSize + baseIndex > n，// 此状况下，新表对应索引上的元素曾经被获取了，没有其余元素，则复原长期信息
while ((s = stack) != null && (index += (len = s.length)) >= n) {
n = len;
index = s.index;
// 将旧表赋值回遍历器，而后将存储值置为 null
tab = s.tab;
s.tab = null;
TableStack<K,V> next = s.next; // null
s.next = spare; // save for reuse
stack = next;
spare = s;
}
// 此处复原 index 为 baseIndex + 1
// 将 index 调整为旧表 index，并自增推动到下一个元素
// s == null 作为先决条件，示意退回旧表进行操作
if (s == null && (index += baseSize) >= n)
index = ++baseIndex;
}
}
pushState 和 recoverState 除了实现索引的变换，实际上对 TableStack 的操作，也达到通过复用独自一个 TableStack 实现入栈出栈，重复使用的成果。次要是通过 TableStack 的 next 属性。因为在算法中，通过判断 TableStack 是否为 null 来作为先决条件管制将索引复原为旧表索引+1，所以须要将实例化好的惟一一个 TableStack 一直关联到 next 属性上，便于下次应用时，从 next 上获取该对象。赋值 TableStack 为 null 是在 recoverState 中解决的。通过两个指针一直循环关联到 next 属性上达到了复用的成果。
2.5 其余问题：
-
当遍历到
ForwardingNode，将信息长期存储起来后，如果此时ConcurrentHashMap的扩容完结，会产生什么状况？- 实际上，
Traverser的遍历是与内部的扩容关联不大（解决新表），因为 Traverser 在创立的时候，曾经应用了外部变量存储了 旧表 的援用，所以即便内部的扩容完结，原ConcurrentHashMap的表援用被更新为新表，但Traverser的旧表援用还在，还可能统一基于旧表进行遍历，但这个时候，因为旧表上曾经全副是ForwardingNode了，所以会一直地通过ForwardingNode找到新表，并进行TableStack的存储和复原，每一次元素遍历都在baseIndex和baseIndex + baseSize索引上获取节点数据。
- 实际上，
-
当遍历过程中，有新元素增加，如果增加到
index索引之前，会产生什么状况？- 什么都不会产生，在
Traverser的算法中，认为这即便产生了，也属于 可保障的一致性，对遍历没有影响。当然如果是被增加到index之后，还是可能被遍历到的。
- 什么都不会产生，在
总结：
- 如果可能在脑海中，将遍历设想成两个表，一个旧表，一个新表（新表大小为旧表的 2 倍），索引挪动遇到元素标识为
rehashed时，就切换到新表做（2 处不同索引的）元素获取，那这个Traverser就不难理解。 - 在遍历中为了保留长期信息，同时为了尽可能地复用，
Traverser实现了TableStack的构造，尽管看起来有点绕，但复用杠杠的 Traverser的遍历实现也得益于ConcurrentHashMap的扩容是 2 倍扩容，便于揣测新数组的边界范畴- 简略图如下：
