java - 并发跳过列表？也就是说，不是 ConcurrentSkipListSet

Question

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

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

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

有什么建议吗？

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

Answer 1

The existing ConcurrentSkipListSet would be ideal, if it was a list and not a set.

所以 SkipList data-structure它的核心是一个链表。如果您担心顺序以及轻松有序地遍历它的能力，SkipList 也可以很好地解决这个问题。它也是平衡树的概率替代方案，这就是为什么它也可以是 Set 或 Map 的原因。内存中的数据结构如下所示:

引用自 Javadocs:

This class implements a concurrent variant of SkipLists providing expected average log(n) time cost for the containsKey, get, put and remove operations and their variants. Insertion, removal, update, and access operations safely execute concurrently by multiple threads. Iterators are weakly consistent, returning elements reflecting the state of the map at some point at or since the creation of the iterator. They do not throw ConcurrentModificationException, and may proceed concurrently with other operations. Ascending key ordered views and their iterators are faster than descending ones.

如果您详细说明您希望List 具有哪些功能，我可以更好地回答ConcurrentSkipListSet 是否能够工作。

---

编辑:

啊，我明白了。在评论中反复讨论之后，您似乎需要能够将两个等效的对象粘贴到 Set 中，这是不可能的。我们的工作是永远不要让 compareTo(...) 返回 0。这有点 hack，但是使用 AtomicLong 为每个对象生成一个唯一的数字，你然后可以在实际比较字段(在本例中为数字超时值)相等时比较这些数字。这将允许将具有相同字段的对象插入到 Set 中，并根据字段以正确的顺序保存。