ConcurrentSkipList? That is, not a ConcurrentSkipListSet

Question

I need a very fast (insert, remove, contains) highly concurrent list that can be sorted using a comparator/comparable.

The existing ConcurrentSkipListSet would be ideal, if it was a list and not a set. I need to insert multiple items which are equal into the data structure.

I'm currently thinking of using a LinkedDeque if I can't find anything better, but that structure is considerably slower than a skiplist at high contention.

Any suggestions?

EDIT: What I actually need, bare minimum, is something that is sorted using compareTo, can insert concurrently and can remove/get items using object identity. All other concurrent requirements mentioned in comments still apply.

Answer 1

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

So the SkipList data-structure at it's core is a linked list. If you are worried about order and the ability to traverse it easily and in order, the SkipList will work very well for that as well. It is also a probabilistic alternative to a balanced tree which is why it can also be a Set or a Map. The data structure in memory looks something like the following:

To quote from the 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.

If you explain more about what features you want from List, I can answer better whether ConcurrentSkipListSet will be able to work.

---

Edit:

Ah, I see. After some back and forth in the comment, it seems like you need to be able to stick two objects that are equivalent into the Set which isn't possible. What we worked out is to never have compareTo(...) return 0. It's a bit of a hack but using AtomicLong to generate a unique number for each object, you can then compare those numbers whenever the real comparison field (in this case a numerical timeout value) is equal. This will allow objects with the same field to be inserted into the Set and kept in the proper order based on the field.