Why is there not a concurrent TreeMap?

java concurrency treemap
Rollerball picture Rollerball · Jul 15, 2013 · Viewed 24.3k times · Source

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?

Answer

Gray picture Gray · Jul 15, 2013

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.

Related questions

How to wait for all threads to finish, using ExecutorService?

I need to execute some amount of tasks 4 at a time, something like this: ExecutorService taskExecutor = Executors.newFixedThreadPool(4); while(...) { taskExecutor.execute(new MyTask()); } //...wait for completion somehow How can I get notified once all of them are complete? For now …

Read More
What's the difference between ConcurrentHashMap and Collections.synchronizedMap(Map)?

I have a Map which is to be modified by several threads concurrently. There seem to be three different synchronized Map implementations in the Java API: Hashtable Collections.synchronizedMap(Map) ConcurrentHashMap From what I understand, Hashtable is an old implementation (…

Read More
When and how should I use a ThreadLocal variable?

When should I use a ThreadLocal variable? How is it used?

Read More