首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >从并发修改的ConcurrentSkipListSet创建TreeSet时出现异常

从并发修改的ConcurrentSkipListSet创建TreeSet时出现异常
EN

Stack Overflow用户
提问于 2016-02-28 22:29:32
回答 1查看 886关注 0票数 19

一般来说,并发集合在迭代时是安全的;根据Javadoc的说法:“迭代器是弱一致的,返回的元素反映了在迭代器创建时或自创建以来的某个时刻集合的状态。它们不会抛出ConcurrentModificationException,并且可以与其他操作并发进行。”但是,请考虑以下内容:

代码语言:javascript
复制
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);
    }
}

输出为

代码语言:javascript
复制
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

我想知道这是一个bug还是一个特性;我们没有得到一个ConcurrentModificationException,但是仍然,不得不关心迭代(回退到同步块或其他)有点违背了ConcurrentSkipListSet/Map的目的。我已经能够在Java 7和8(目前在我的Linux机器上是8u72 )上重现这一点。

EN

回答 1

Stack Overflow用户

发布于 2016-02-28 23:24:05

据我浏览源代码所知,TreeSet的问题在于它在迭代之前调用size(),然后使用它而不是调用hasNext()。这可能是一个bug,但我认为这只是红黑树复杂结构需要仔细平衡的结果,因此需要提前知道大小,以便在创建过程中在线性时间内正确地平衡它。

你可以通过手动迭代和向TreeSet添加元素来规避这个问题,但这会导致n log n复杂性,这可能是TreeSet的构造函数不这样做的原因(它的API规范保证线性时间)。当然,它仍然可以在构建树时调用hasNext(),但在构建完成后可能需要一些额外的操作来重新平衡树,这可能会导致分期线性复杂性。但是红黑树本来就是一团糟的,这种黑客攻击会使实现更加混乱。

尽管如此,我仍然认为它非常令人困惑,应该在API文档中的某个地方记录下来,但我不确定具体在哪里。可能是在他们解释什么是弱一致性迭代器的部分。特别要指出的是,一些库类依赖于返回的大小,因此可能会抛出NoSuchElementException。提到特定的类也会有所帮助。

票数 6
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/35683724

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档