46

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?

Gray
  • 115,027
  • 24
  • 293
  • 354
Rollerball
  • 12,618
  • 23
  • 92
  • 161
  • Your question is not understandable. What about each object? Why it exists? What it does? How it smells? – nanofarad Jul 15 '13 at 14:15
  • 2
    to whom says it's not related to programming. API are related to programming. – Rollerball Jul 15 '13 at 14:16
  • I never said it wasn't related. I just said it's completely unclear. – nanofarad Jul 15 '13 at 14:17
  • @hexafraction I did not say it was you. – Rollerball Jul 15 '13 at 14:19
  • I'm still answering your inquiry. – nanofarad Jul 15 '13 at 14:19
  • 1
    I think even for the ones who said the question was unclear now should be quite clear and the question can be reopened. Thanks for your feedback. – Rollerball Jul 16 '13 at 10:48
  • checkout https://github.com/arunmoezhi/ConcurrentTreeMap for a C++ implementation – arunmoezhi Sep 03 '16 at 09:04
  • BTW, here's how to synchronize one (excerpt from javadoc): Note that this implementation is not synchronized. If multiple threads access a map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. [...] the map should be "wrapped" using the Collections.synchronizedSortedMap method. This is best done at creation time, to prevent accidental unsynchronized access to the map: `SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));` – ACV Oct 21 '22 at 18:55

2 Answers2

53

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.

Gray
  • 115,027
  • 24
  • 293
  • 354
11

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.

Joni
  • 108,737
  • 14
  • 143
  • 193