ConcurrentSkipListSet internal working, difference from TreeSet

Question

Only difference I understand is between iterators. SkipList has weakly consistent, while TreeSet has fail-fast. Other than that I don't see any synchronized methods inside SkipList (although it is in Concurrent package).

Can someone please explain to me how is SkipList concurrent when it doesn't have any synchronization in it? What problems can it help me with and why should I ever use it other than this difference between Iterators?

Answer 1

„…how is SkipList concurrent when it doesn't have any synchronization in it?…“

TL;DR — ConcurrentSkipListSet is concurrent because the elements it holds cannot be written to at the same time by concurrently executing threads. It achieves its concurrency without using synchronized and locks.

---

The long version

Concurrency in the context of the concurrent collections, does not necessarily mean those classes all implement thread safety using monitors (aka, the synchronized keyword).

First you should understand that thread safety is essentially about ensuring that two or more competing threads do not modify the shared state of an application. Then you realize that there are ways (some more performant) other than synchronized to achieve thread safety.

Making sure your state cannot be modified (that it's immutable) in the first place is one simple but very effective way to get thread safety.

Also, a class can be thread safe by delegating its thread safety responsibilities to a different, thread-safe class.

ConcurrentSkipListSet is considered to be concurrent because, as its Javadoc says, its: „Insertion, removal, update, and access operations safely execute concurrently by multiple threads“.

It achieves its concurrency because it delegates its thread safety responsibilities to a thread-safe class; namely: ConcurrentSkipListMap.

ConcurrentSkipListSet is thread-safe because ConcurrentSkipListMap is. And ConcurrentSkipListMap is thread-safe because, by using AbstractMap.SimpleImmutableEntry<K,V> internally, it guarantees that none of its state (its keys and values) can be modified by currently executing threads, because its state is immutable.

You can see ConcurrentSkipListSet delegating to ConcurrentSkipListMap at several places in the source code I linked to above. If you're interested in learning more about delegating thread safety, I recommend you read Chapter 4, Composing Objects, Java Concurrency In Practice.

„…What problems can it help me with“

Using it gets you free thread-safety. The kind that is way more performant — and with way less risk of shooting yourself in the foot — than using synchronized.

„…why should I ever use it other than this difference between Iterators?“

If the state of your application needs to be stored in some collection and that collection will be accessible in any way to concurrently executing threads, then using ConcurrentSkipListSet is a thread-safe option that you have.