2

我正在寻找一个与线性运算完全相同ConcurrentSkipListSet但没有线性size运算的特定数据结构，对于较大的集合，它可能经常被调用。

我知道Collections.synchronizedNavigableSet(new TreeSet())，但是同步迭代：

synchronized (set) {
    Iterator<T> iter = set.iterator();
    while (iter.hasNext())
    iter.next();
}

很慢。

那么，您是否知道一个与线性操作NavigableSet完全相同ConcurrentSkipListSet但没有线性size操作的实现，例如在 Apache Commons、Guava 中？或者我应该对集合进行不同的迭代？

4

1 回答 1

3

他们没有以这种方式实现它是有充分理由的（即使用计数器）。它是关于多处理器编程的语义。并发程序有许多正确性模型，强（称为顺序一致性）和宽松（称为静态一致性）（参见 Maurice Herlihy 和 Nir ​​Shavit 的 The Art of Multiprocessor Programming 或Quasi-Linearizability）。

计数器的实现未能遵守其中任何一个。如果在实际添加和删除操作之前更新大小，它可能会变为负数（假设您在一个空集上删除和添加，删除首先更新大小导致 -1 大小......）。如果之后更新大小也是如此。即使在添加操作之前增加大小并在删除之后减小大小的解决方案也有一个严重的缺点（但不会产生负值）。考虑两个使用参数“x”的添加操作和一个使用相同参数“x”的删除操作（都具有相同的元素）。可能存在大小将设置为 2 的情况（两次添加操作增加了计数器），一种从未存在过的状态（集合从来没有大小为 2，注意我们总是添加相同的元素 'x'

它的实现方式（通过计算元素，具有线性时间复杂度）至少会产生一个在某个时间点存在的值（更准确地说，它是静态一致的）。

于 2013-08-23T11:29:19.237 回答