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.
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 aMap
. The data structure in memory looks something like the following:To quote from the Javadocs:
If you explain more about what features you want from
List
, I can answer better whetherConcurrentSkipListSet
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 havecompareTo(...)
return 0. It's a bit of a hack but usingAtomicLong
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 theSet
and kept in the proper order based on the field.