When should I use ConcurrentSkipListMap?

Question

In Java, ConcurrentHashMap is there for better multithreading solution. Then when should I use ConcurrentSkipListMap? Is it a redundancy?

Does multithreading aspects between these two are common?

Answer 1

See Skip List for a definition of the data structure. A ConcurrentSkipListMap stores the Map in the natural order of its keys (or some other key order you define). So it'll have slower get/put/contains operations than a HashMap, but to offset this it supports the SortedMap and NavigableMap interfaces.

Answer 2

These two classes vary in a few ways.

ConcurrentHashMap does not guarantee* the runtime of its operations as part of its contract. It also allows tuning for certain load factors (roughly, the number of threads concurrently modifying it).

ConcurrentSkipListMap, on the other hand, guarantees average O(log(n)) performance on a wide variety of operations. It also does not support tuning for concurrency's sake. ConcurrentSkipListMap also has a number of operations that ConcurrentHashMap doesn't: ceilingEntry/Key, floorEntry/Key, etc. It also maintains a sort order, which would otherwise have to be calculated (at notable expense) if you were using a ConcurrentHashMap.

Basically, different implementations are provided for different use cases. If you need quick single key/value pair addition and quick single key lookup, use the HashMap. If you need faster in-order traversal, and can afford the extra cost for insertion, use the SkipListMap.

_{*Though I expect the implementation is roughly in line with the general hash-map guarantees of O(1) insertion/lookup; ignoring re-hashing}