6

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

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

如果找不到更好的东西，我目前正在考虑使用 LinkedDeque，但是这种结构比高争用的跳过列表要慢得多。

有什么建议么？

编辑：我真正需要的，最低限度，是使用 compareTo 排序的东西，可以同时插入并且可以使用对象标识删除/获取项目。评论中提到的所有其他并发要求仍然适用。

4

2 回答 2

7

现有的 ConcurrentSkipListSet 将是理想的，如果它是一个列表而不是一个集合。

所以SkipList 数据结构的核心是一个链表。如果您担心顺序以及轻松有序地遍历它的能力，那么 SkipList 也可以很好地工作。它也是平衡树的概率替代方案，这就是为什么它也可以是 aSet或 a Map。内存中的数据结构如下所示：

在此处输入图像描述

引用 Javadocs：

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

如果您更多地解释您想要的功能List，我可以更好地回答是否ConcurrentSkipListSet能够工作。

编辑：

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

于 2013-09-03T14:17:23.377 回答
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;
   })

;

于 2019-10-02T08:24:35.763 回答