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”和该集合不能包含重复项)。

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