ConcurrentSkipList是什么？它不是ConcurrentSkipListSet吗？

Question

ConcurrentSkipList是什么？它不是ConcurrentSkipListSet吗？

javaconcurrencyskip-lists

7

我需要一个非常快速（插入、删除、查询）高度并发的列表，可以使用比较器/可比较器进行排序。

如果ConcurrentSkipListSet是列表而不是集合，则现有的结构将非常理想。我需要将多个相等的项插入到数据结构中。

如果找不到更好的结构，我目前正在考虑使用LinkedDeque，但在高争用情况下，该结构比skiplist慢得多。

有什么建议吗？

编辑：实际上，我所需要的最基本要求是，使用compareTo进行排序，可以同时插入，并且可以使用对象标识删除/获取项。所有其他并发需求仍然适用。

- MarcB

2

你所说的“非常快”是什么意思？我见过人们用汇编语言编写冒泡排序算法赢得编程性能比赛。你指的是与列表中元素数量相比的常数时间还是线性时间？ - Daniel S.

1

你知道列表更改次数与读取访问次数之比的估计值吗？ - Daniel S.

1

我曾经在维基百科页面上作为SkipLists的早期实现之一，因为我在很久很久以前将其放入了我的内存调试dmalloc库中。 :-) - Gray

非常快的意思是在至少有20个核心的多处理器机器上，在高争用情况下比LinkedBlockingQueue更快。基本上，它使用CAS内部而不是在所有内容上同步（或者至少使用分段锁）。使用案例是我需要跟踪超时，我找到的最快方法是使用timeout作为排序键的ConcurrentSkipListSet，然后另一个线程迭代该集合，休眠直到下一个超时...不幸的是，当两个对象具有相同的超时值时，它停止工作。 - MarcB

啊...我突然意识到我大脑一片空白。实际上我需要的是一个可以迭代的排序列表。它可以在任何地方插入和根据对象标识而不是compareTo进行删除。 - MarcB

显示剩余4条评论

2个回答

0

您可以使用一个永远不会返回0的比较器来创建Set。

private Set<Obj> entities = new ConcurrentSkipListSet<>((o1, o2) -> {
      if (o1.equals(o2)) {
         // Return -1 or 1 - decide where you want to place an object when it's equals to another one
         return -1;
      }
      // Implement the sorting order below
      if (o1.getTimestamp() < o2.getTimestamp()) {
         return -1;
      }
      if (o1.getTimestamp() > o2.getTimestamp()) {
         return 1;
      }

      return -1;
   })

;

- P Sh

这将产生一个不稳定的排序。 - Dave

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Gray · Accepted Answer

现有的ConcurrentSkipListSet如果是一个列表而不是集合，就会很理想。

所以SkipList数据结构在其核心是一个链表。如果你担心排序和轻松按顺序遍历它的能力，SkipList也将非常适用。它还是平衡树的概率性替代方案，这也是为什么它可以是一个Set或Map。内存中的数据结构看起来像下面这样:

引用Javadocs的话：

这个类实现了SkipLists的并发变体，提供了containsKey、get、put和remove操作及其变种的预期平均log(n)时间成本。插入、删除、更新和访问操作可以安全地由多个线程同时执行。迭代器是弱一致的，返回反映迭代器创建时或之后某个时间点映射状态的元素。它们不会抛出ConcurrentModificationException，并且可以与其他操作同时进行。升序键排序视图及其迭代器比降序键排序视图更快。

如果您能详细解释您想从List中获得哪些功能，我可以更好地回答是否可以使用ConcurrentSkipListSet。

编辑：

啊，我明白了。在评论中经过一些来回交流，看起来您需要能够将两个等效的对象粘贴到Set中，这是不可能的。我们想出来的办法是永远不要让compareTo(...)返回0。虽然有点小技巧，但使用AtomicLong为每个对象生成唯一数字，然后比较这些数字，每当真正的比较字段（在本例中是数值超时值）相等时。这将允许具有相同字段的对象被插入到Set中，并根据字段保持正确的顺序。