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

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}