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倍扩容，便于揣测新数组的边界范畴- 简略图如下：