java - 具有恒定大小操作的线程安全 NavigableSet？

Question

我正在寻找与 ConcurrentSkipListSet 完全相同的特定数据结构但没有线性 size - 操作，对于较大的集合可能会经常调用。

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

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

很慢。

那么，你知道 NavigableSet吗？完全类似于 ConcurrentSkipListSet 的实现但没有线性 size操作，例如在 Apache Commons、Guava 中？或者我应该对集合进行不同的迭代？

Answer 1

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

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

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