Rollerball Rollerball - 4 months ago 16
Java Question

ConcurrentTreeMap in java

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

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.

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?

Uh, 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.. Or 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 Data Structures 305 classes.