ConcurrentHashMap弱一致性迭代器Iterator

小灰灰 2022-05-12 02:14 126阅读 0赞

之前查看[ArrayList中迭代器实现源码][ArrayList]，明白为啥通常用的迭代器在迭代的过程中不能作add和remove操作。但在支持并发数据结构的情况下，还会存在这种情况吗？

答案是不会，少见多怪了，util包中的迭代器实现是fast-failed迭代器，说白了就是一旦由修改就抛异常，在current包中迭代器是弱一致性迭代器，原来两种迭代器情况不一样。

测试代码用以ConcurrentHashMap为例，预先添加部分元素，然后启动线程不断往ConcurrentHashMap中添加元素，同时通过迭代器不断输出。此代码运行的结果是，不会抛出ConcurrentModificationException，同时添加到hashMap中的部分元素也会被迭代器迭代输出。

测试代码如下：

public class TestConcurrentHashMap {
    
        public static void main(String[] args) {
    
            ConcurrentHashMap<String, String> hashMap = new ConcurrentHashMap<String, String>();
            
            for(int i=0; i< 100; i++) {
                hashMap.put(""+i, ""+i);
            }
            
    
            Thread thread = new Thread(new Runnable() {
    
                @Override
                public void run() {
    
                    for(int i=200; i< 10000000; i++) {
                        
                        hashMap.put(""+i, ""+i);
                        try {
                            Thread.sleep(50);
                        }
                        catch (InterruptedException e) {
                            e.printStackTrace();
                        }
                    }
                    
                }
                
            });
            
            thread.start();
            
            Iterator<String> iterator = hashMap.keySet().iterator();
            while(iterator.hasNext()) {
                
                String key = (String) iterator.next();
                System.out.println(key);
                try {
                    Thread.sleep(50);
                }
                catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }

原来在并发包下迭代器迭代时是可以增删元素的，当然这也是理想中的迭代器的模样。

先看源码，这种迭代器和fast-failded迭代器有什么区别？  
**ConcurrentHashMap的keySet方法，返回了一个KeySetView内部类的实例。**

public KeySetView<K,V> keySet() {
            KeySetView<K,V> ks;
            return (ks = keySet) != null ? ks : (keySet = new KeySetView<K,V>(this, null));
        }

**KeySetView类内容，类代码不多，重点关注iterator方法，此方法返回了一个KeyIterator对象，并且包含5个参数，这个就是迭代用的迭代器**

public static class KeySetView<K,V> extends CollectionView<K,V,K>
            implements Set<K>, java.io.Serializable {
            private static final long serialVersionUID = 7249069246763182397L;
            private final V value;
            KeySetView(ConcurrentHashMap<K,V> map, V value) {  // non-public
                super(map);
                this.value = value;
            }
    
            public V getMappedValue() { return value; }
    
            public boolean contains(Object o) { return map.containsKey(o); }
    
            public boolean remove(Object o) { return map.remove(o) != null; }
    
            /**
             * @return an iterator over the keys of the backing map
             */
            public Iterator<K> iterator() {
                Node<K,V>[] t;
                ConcurrentHashMap<K,V> m = map;
                int f = (t = m.table) == null ? 0 : t.length;
                return new KeyIterator<K,V>(t, f, 0, f, m);
            }
            
            public Spliterator<K> spliterator() {
                Node<K,V>[] t;
                ConcurrentHashMap<K,V> m = map;
                long n = m.sumCount();
                int f = (t = m.table) == null ? 0 : t.length;
                return new KeySpliterator<K,V>(t, f, 0, f, n < 0L ? 0L : n);
            }

**KeyIterator类继承至BaseIterator类，而BaseIterator又继承至Traverser，具体代码不贴了，JDK1.8源码中查看，重要的实现在Traverser中**

KeyIterator在调用next方法时，最终会作用在Traverser类的advance方法中，advance方法负责寻找下一个元素。此方法中不会抛出ConcurrentModificationException；advance方法中通过不断循环遍历，其中考虑到table的大小发生变化，并且节点的组织方式可能是链表也可能是红黑树，遍历的过程中可能会有部分数据遍历不到，此为弱一致性的表现。

static class Traverser<K,V> {
            Node<K,V>[] tab;        // current table; updated if resized
            Node<K,V> next;         // the next entry to use
            TableStack<K,V> stack, spare; // to save/restore on ForwardingNodes
            int index;              // index of bin to use next
            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;
            }
    
            /**
             * Advances if possible, returning next valid node, or null if none.
             */
            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
                }
            }
        }

代码为JDK1.8版本

[ArrayList]: https://blog.csdn.net/qq_36101933/article/details/82632137