从并发修改的ConcurrentSkipListSet创建TreeSet的异常

Question

通常,并发集合可以安全迭代; 根据Javadoc的说法:'迭代器是弱一致的,在迭代器创建时或之后的某个时刻返回反映集合状态的元素.它们不会抛出ConcurrentModificationException,并且可能与其他操作同时进行.但是,考虑一下:

import java.util.Random;
import java.util.TreeSet;
import java.util.concurrent.ConcurrentSkipListSet;

public class ConcurrencyProblem {
    private static volatile boolean modifierIsAlive = true;

    public static void main(String[] args) {
        final ConcurrentSkipListSet<Integer> concurrentSet = new ConcurrentSkipListSet<>();
        Thread modifier = new Thread() {
            private final Random randomGenerator = new Random();

            public void run() {

                while (modifierIsAlive) {
                    concurrentSet.add(randomGenerator.nextInt(1000));
                    concurrentSet.remove(randomGenerator.nextInt(1000));
                }
            };
        };
        modifier.start();
        int sum = 0;
        while (modifierIsAlive) {
            try {
                TreeSet<Integer> sortedCopy = new TreeSet<>(concurrentSet);
                // make sure the copy operation is not eliminated by the compiler
                sum += sortedCopy.size();
            } catch (RuntimeException rte) {
                modifierIsAlive = false;
                rte.printStackTrace();
            }
        }
        System.out.println("Dummy output: " + sum);
    }
}

输出是

java.util.NoSuchElementException
at java.util.concurrent.ConcurrentSkipListMap$Iter.advance(ConcurrentSkipListMap.java:2299)
at java.util.concurrent.ConcurrentSkipListMap$KeyIterator.next(ConcurrentSkipListMap.java:2334)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2559)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2547)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2504)
at java.util.TreeMap.addAllForTreeSet(TreeMap.java:2462)
at java.util.TreeSet.addAll(TreeSet.java:308)
at java.util.TreeSet.<init>(TreeSet.java:172)
at mtbug.ConcurrencyProblem.main(ConcurrencyProblem.java:27)
Dummy output: 44910

我想知道这是一个错误还是一个功能; 我们没有得到ConcurrentModificationException,但仍然,不得不关心迭代(回落到同步块或其他方式)那样会破坏ConcurrentSkipListSet/Map的目的.我已经能够使用Java 7和8(目前,我的Linux机器上的8u72)重现这一点.

Answer 1

据浏览源代码我可以理解,问题TreeSet是它size()在迭代之前调用然后使用它而不是调用hasNext().这可能是一个错误,但我认为这只是红黑树是需要仔细平衡的复杂结构的结果,因此需要提前知道尺寸以在创建期间在线性时间内适当地平衡它.

您可以通过手动迭代并向其添加元素来避免这种情况TreeSet,但这会导致n log n复杂性,这可能是TreeSet构造函数不这样做的原因(其API规范保证线性时间).当然,它仍然hasNext()可以在构建树时调用,但是在构造完成后可能需要一些额外的操作来重新平衡树,这可能导致分摊的线性复杂性.但是红黑树本来就是一团糟,而那种破解会使实施更加混乱.

尽管如此,我认为它非常混乱,应该在API文档中的某处记录,但我不确定究竟在哪里.可能在他们解释什么是弱一致迭代器的部分.具体来说,应该提到的是,某些库类依赖于返回的大小,因此可能会抛出NoSuchElementException.提及具体课程也会有所帮助.