图解遍历过程

说明：下文中的tab表示源table。nextTable表示扩容时，迁移的目标table

1 当遍历到fwd节点的时候，说明正在扩容，此节点的数据已经迁移到了nextTable

image.png

2 将tab1的遍历状态（tab1当前的遍历索引index，tab1的长度等信息）push到stack，然后遍历迁移到nextTable(tab2)中的hash桶

（1）由于扩容时，会将tab(tab1)中索引为index的桶，迁移到nextTable(tab2中索引为index和索引为index+tab.length的2个桶中。因此在nextTable(tab2)中的遍历顺序为：index，index+tab.length （tab2中的桶2，和桶4 )

（2）如果桶2和桶4都是正常的节点，遍历完桶2和桶4后，就会将stack中的tab(tab1)弹出，继续遍历tab(tab1)中的桶

（3）但是桶2是fwd节点，说明tab2也被扩容，此节点的node被迁移到了nextTable(tab3)中

image.png

3 将tab2的遍历状态push到stack，跳到nextTable(tab3)中继续遍历

(1) 按照扩容迁移规则，先遍历index=2的hash桶

image.png

（2）然后遍历index=6的hash桶（index+tab2.length=2+4=6）

image.png

4 遍历完tab3后，将tab2出栈，根据记录的遍历信息，继续遍历tab2。

（1）从stack弹出的tab2,进入了spare栈。（spare栈似乎是为了对象重用，减少new对象的内存开销）

（2）弹出的tab2栈节点，记录了tab2的当前index=2。然后接着遍历下一个index=4的桶（index+tab1.length=2+2=4）

（3）tab2的桶4依旧是个fwd节点，那么继续将tab2入栈（此时tab2的index=4)

（4）桶4依旧是一个fwd节点，那么继续将tab2的遍历状态push到stack，然后遍历nextTable(tab3)

(5) 此时入栈的tab2遍历状态节点，并不是重新new的，而是spare所指向的节点

image.png

5 遍历nextTable(tab3)中的桶4（index=4)和桶8(index+tab2.length)

image.png

6 完成了nextTable(tab3)的遍历，弹出tab2的遍历状态节点。

(1) nextTable(tab2)遍历完毕。

image.png

7 弹出tab(tab1), 开始继续遍历tab1

(1) stack栈空了，而且spare栈按照出栈的顺序保存了相关节点

(2) 遍历完毕。

image.png

相关源码分析

ConcurrentHashMap的遍历操作，主要是通过如下迭代器实现： KeyIterator，EntryIterator，ValueIterator

类图如下：

image.png

Traverser类

 static class Traverser<K,V> {
        Node<K,V>[] tab;        // current table; updated if resized
        //下一个要访问的entry
        Node<K,V> next;         // the next entry to use
        //发现forwardingNode时，保存当前tab相关信息
        TableStack<K,V> stack, spare; // to save/restore on ForwardingNodes
        //下一个要访问的hash桶索引
        int index;              // index of bin to use next
        //当前正在访问的初始tab的hash桶索引
        int baseIndex;          // current index of initial table
        //初始tab的hash桶索引边界
        int baseLimit;          // index bound for initial table
        //初始tab的长度
        final int baseSize;     // initial table size
        
        ...
        ...
        
        /**
         * 如果有可能，返回下一个有效节点，否则返回null。
         */
        final Node<K,V> advance() {
            Node<K,V> e;
            //获取Node链表的下一个元素e
            if ((e = next) != null)
                e = e.next;
            for (;;) {
                Node<K,V>[] t; int i, n;  // must use locals in checks
                //e不为空，返回e
                if (e != null)
                    return next = e;
                    
                //e为空，说明此链表已经遍历完成，准备遍历下一个hash桶
                if (baseIndex >= baseLimit || (t = tab) == null ||
                    (n = t.length) <= (i = index) || i < 0)
                    //到达边界，返回null
                    return next = null;
                    
                //获取下一个hash桶对应的node链表的头节点
                if ((e = tabAt(t, i)) != null && e.hash < 0) {
                    //转发节点,说明此hash桶中的节点已经迁移到了nextTable
                    if (e instanceof ForwardingNode) {
                        tab = ((ForwardingNode<K,V>)e).nextTable;
                        e = null;
                        //保存当前tab的遍历状态
                        pushState(t, i, n);
                        continue;
                    }
                    //红黑树
                    else if (e instanceof TreeBin)
                        e = ((TreeBin<K,V>)e).first;
                    else
                        e = null;
                }
                
                
                if (stack != null)
                    //此时遍历的是迁移目标nextTable,尝试回退到源table，继续遍历源table中的节点
                    recoverState(n);
                else if ((index = i + baseSize) >= n)
                    //初始tab的hash桶索引+1 ，即遍历下一个hash桶
                    index = ++baseIndex; // visit upper slots if present
            }
        }
        
        
          /**
         * 在遇到转发节点时保存遍历状态。
         */
        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;
        }

        /**
         * 可能会弹出遍历状态。
         * @param n length of current table
         */
        private void recoverState(int n) {
            TableStack<K,V> s; int len;
            /**
              (s = stack) != null :stack不空，说明此时遍历的是nextTable  
              (index += (len = s.length)) >= n: 确保了按照index,index+tab.length的顺序遍历nextTable,条件成立表示nextTable已经遍历完毕
            */
            
            //nextTable中的桶遍历完毕
            while ((s = stack) != null && (index += (len = s.length)) >= n) {
                //弹出tab，获取tab的遍历状态，开始遍历tab中的桶
                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;
        }
        
             
        
        
  }