关于jdk:ConcurrentHashMap-的-Traverser-阅读

6次阅读

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

    

正文完
jdk
发表至： jdk
2020-12-15
 0
关于jdk:JDK-8-Stream-数据流效率怎么样
关于jdk:请你喝一杯-Corretto谈一谈-JDK-的新选择
关于jdk:一种面向业务配置基于JSF广播定时生效的工具
关于jdk:深入了解JDK源码系统解析