CODEWITHSUNDEEP
javamultithreadingthread-safetyconcurrentskiplistmap
Deepak
Deepak

Reputation: 45

Is ConcurrentSkipListMap put method thread-safe?

Recently while exploring ConcurrentSkipListMap I went through its implementation and found that its put method is not thread-safe. It internally calls doPut which actually adds the item. But I found that this method does not use any kind of lock similar to ConcurrentHashMap.

Therefore, I want to know whether add is thread-safe or not. Looking at the method it seems that it is not thread-safe--that is if this method is executed by two threads simultaneously then a problem may occur.

I know ConcurrentSkipListMap internally uses a skiplist data structure but I was expecting add method to be thread safe. Am I understanding anything wrong ? Is ConcurrentSkipListMap really not thread-safe ?

Upvotes: 0

Views: 1493

Answers (3)

DrunkenPope
DrunkenPope

Reputation: 576

The comments in the implementation say:

Given the use of tree-like index nodes, you might wonder why this doesn't use some kind of search tree instead, which would support somewhat faster search operations. The reason is that there are no known efficient lock-free insertion and deletion algorithms for search trees. The immutability of the "down" links of index nodes (as opposed to mutable "left" fields in true trees) makes this tractable using only CAS operations.

So they use some low level programming features with compare-and-swap operations to make changes to the map atomic. With this they ensure thread safety without the need to synchronize access.

You can read it in more detail in the source code.

Upvotes: 2

OldCurmudgeon
OldCurmudgeon

Reputation: 65793

Just because it doesn't use a Lock doesn't make it thread unsafe. The Skip list structure can be implemented lock free.

You should read the API carefully.

... 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. ...

Upvotes: 3

Evgeniy Dorofeev
Evgeniy Dorofeev

Reputation: 135992

We should trust Java API. And this is what java.util.concurrent package docs says:

Concurrent Collections

Besides Queues, this package supplies Collection implementations designed for use in multithreaded contexts: ConcurrentHashMap, ConcurrentSkipListMap, ConcurrentSkipListSet, CopyOnWriteArrayList, and CopyOnWriteArraySet.

Upvotes: 1

Related Questions