ConcurrentSkipListSet and re-sorting (java)

Question

I am using a ConcurrentSkipListSet, that is obviously accessed through multiple threads. Now, the values that are used by the compareTo-method of the underlying objects change overtime. Because of this, I want to 'update' the ordering of the list (by resorting it, or something similar).

However, java.util.Collections.sort(list) doesn't work, and just rebuilding the list is probably too slow (and would mess up the whole concurrency-proofness). Is there any other solution I should look at?

It does not have to lead to an optimal sort (which is near-impossible with concurrency and changing values anyway). Near optimal would suffice, as long as any remove/add-calls remain thread-proof (this would be a real issue when rebuilding the list when sorting).

Answer 1

Every time you edit an item such that it's sort order may potentially change, you have to remove it from the list then change the key and then re-insert it.

---

Dr Cliff Click at Azul Systems has a very nice presentation of how they do lock-free hash-tables using tombstones and such. If you go towards writing your own skip-list/tree to make the reordering of an item into a single - and hopefully faster - op, then you might also go this lock-free route too. And be sure to share your results :)

Answer 2

These types of collections in the Java API do not support mutable elements (i.e. elements where the compareTo method changes). As such, the only way to do it is re-assemble a new list in an atomic way, or as Will suggests you can perform a remove, mutate and re-insert of the element.

HashSet has the same problem - the hash bucket is calculated on insertion of an object, then you won't be able to do set.contains( ... ) if you mutate the object's hash code.

To be exact, collections like ConcurrentSkipListSet and HashSet perform their comparisons/hashing on insertion and removal. The only collections that 'support' mutable elements do not perform special insertion logic based on the state of the elements (e.g. an ArrayList).

The documentation for the Set interface states:

Note: Great care must be exercised if mutable objects are used as set elements. The behavior of a set is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is an element in the set. A special case of this prohibition is that it is not permissible for a set to contain itself as an element.

and the documentation for the SortedSet interface states:

Note that the ordering maintained by a sorted set (whether or not an explicit comparator is provided) must be consistent with equals if the sorted set is to correctly implement the Set interface. (See the Comparable interface or Comparator interface for a precise definition of consistent with equals.) This is so because the Set interface is defined in terms of the equals operation, but a sorted set performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the sorted set, equal. The behavior of a sorted set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.