Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why is there not a concurrent TreeMap? [closed]

I have a few question related to java.util.concurrent package:

  1. Why in the java API there is the non-concurrent TreeMap on one side and the concurrent ConcurrentSkipListMap on one other?

  2. Why did not they call it ConcurrentTreeMap? Is it safe to say that a SkipListMap includes a TreeMap?

For example a non concurrent HashMap has got its concurrent counterpart ConcurrentHashMap. Why does it not happen for the TreeMap?

like image 710
Rollerball Avatar asked Jul 15 '13 14:07

Rollerball


People also ask

Is TreeMap concurrent?

TreeMap and TreeSet are not thread-safe collections, so care must be taken to ensure when used in multi-threaded programs. Both TreeMap and TreeSet are safe when read, even concurrently, by multiple threads.

How do you make TreeMap thread-safe?

TreeMap can be synchronized using the Collections. synchronizedMap() method. The synchronizedMap() method of the Collections class takes the Map that has to be synchronized as a parameter and returns a thread-safe synchronized Map. The synchronizedMap() method of java.

Why is ConcurrentHashMap thread-safe?

ConcurrentHashMap class achieves thread-safety by dividing the map into segments, the lock is required not for the entire object but for one segment, i.e one thread requires a lock of one segment. In ConcurrentHashap the read operation doesn't require any lock.

Can ConcurrentHashMap throws ConcurrentModificationException?

They do not throw ConcurrentModificationException.


2 Answers

Why there is the non-concurrent TreeMap on one side and the ConcurrentSkipListMap on one other?

I suspect this was done because making a tree structure concurrent was too difficult or suffered from locking performance problems. In terms of ordered collections, SkipLists are very simple data structures and provide similar behavior and performance to trees so the ConcurrentSkipListMap (and Set) might have been easier to make concurrent.

I'm actually more disappointed that there isn't a non-concurrent SkipList collection myself.

Is it safe to say that a SkipListMap included a TreeMap?

No. It is safe to say that a SkipList gives similar features in terms of an ordered collection of items that gives O(logN) performance for lookup, insert, delete, etc.. At least it gives a probabilistic approximation of that performance.

Here's a good page about skiplists. They are extremely cool data structures. I can only hope the are taught in modern programming data structures classes.

like image 117
Gray Avatar answered Sep 19 '22 12:09

Gray


The TreeMap class is called that way because it is implemented using a balanced search tree. The ConcurrentSkipListMap is called that way because it's implemented using a skip list. Why is there no concurrent version of TreeMap? Possibly because it's hard to make a tree structure that scales to high levels of concurrency; a concurrent skip list is easier to implement correctly.

like image 45
Joni Avatar answered Sep 19 '22 12:09

Joni