Concurrent Sets - liweiyap/foxtrot-comic-browser-android GitHub Wiki

Concurrent/Thread-safe Sets

ConcurrentHashMap.newKeySet()

WHAT

For the ConcurrentHashMap (and the Set derived from it): Here most basic options are (on average, if you have a good and fast hashCode()) in O(1) (but might degenerate to O(n) when many keys have the same hash code), like for HashMap/HashSet. There is a limited concurrency for writing (the table is partitioned, and write access will be synchronized on the needed partition), while read access is fully concurrent to itself and the writing threads (but might not yet see the results of the changes currently being written). The iterator may or may not see changes since it was created, and bulk operations are not atomic. Resizing is slow (as for HashMap/HashSet), thus you should try to avoid this by estimating the needed size on creation (and using about 1/3 more of that, as it resizes when 3/4 full).

WHEN

Use this when you have large sets, a good (and fast) hash function and can estimate the set size and needed concurrency before creating the map.

ConcurrentSkipListSet

WHAT

ConcurrentSkipListSet is the concurrent SortedSet implementation, with most basic operations in O(log n). It allows concurrent adding/removing and reading/iteration, where iteration may or may not tell about changes since the iterator was created. The bulk operations are simply multiple single calls, and not done atomically – other threads may observe only some of them.

WHEN

Obviously you can use this only if you have some total order on your elements (note that ConcurrentSkipListSet's elements should be Comparable). This looks like an ideal candidate for high-concurrency situations, for not-too-large sets (because of the O(log n)).

WHY NOT

Don't use ConcurrentSkipListSet unless you want a SortedSet. A usual operation like add or remove should be O(1) for a HashSet, but is O(log(n)) for a SortedSet.

Collections.synchronizedSet

WHAT

Collections.synchronizedSet will simply wrap a synchronized-block around each method of the original set. You should not access the original set directly. This means that no two methods of the set can be executed concurrently (one will block until the other finishes) - this is thread-safe, but you will not have concurrency if multiple threads are using the set. If you use the iterator, you usually still need to synchronize externally to avoid ConcurrentModificationExceptions when modifying the set between iterator calls. The performance will be like the performance of the original set (but with some synchronization overhead, and blocking if used concurrently).

WHEN

Use this if you only have low concurrency, and want to be sure all changes are immediately visible to the other threads.

WHY NOT

The synchronizedSet method just wraps the set into a synchronized decorator. On the other hand, ConcurrentHashMap actually implements low-level concurrency, using non-blocking algorithms and "low-level" synchronisations without any locks of the whole collection. So wrappers from Collections.synchronized...Set is worse in multi-threaded environments for performance reasons.

CopyOnWriteArraySet

WHAT

The CopyOnWriteArraySet is a quite simple implementation - it basically has a list of elements in an array, and when changing the list, it copies the array. Iterations and other accesses which are running at this time continue with the old array, avoiding necessity of synchronization between readers and writers (though writing itself needs to be synchronized). The normally fast set operations (especially contains()) are quite slow here, as the arrays will be searched in linear time (O(n)).

WHEN

Use this only for really small sets which will be read (iterated) often and changed seldom. (Swing's listener-sets would be an example, but these are not really sets, and should be only used from the EDT anyway.)

WHY NOT

CopyOnWriteArraySet copies the entire collection on any state mutation, which is not always wanted due to the performance impact. It's designed to work only in special cases. Additionally CopyOnWriteArraySet.contains() has a run-time of O(n) (has to check every entry) whereas HashSet/HashMap has O(1).

Sources

Motivations