java.util.concurrent包中ConcurrentSkipListMap和ConcurrentHashMap释疑

The follows are edited from http://www.java-forums.org/new-java/13840-hashmap-vs-skiplistmap.html:

Constant concurrency vs constant access time (roughly!)

They're essentially horses for courses: they both have different behaviour in terms of (a) time of operations on the map as the size increases, (b) contention and time of operations as concurrent accesses increase, and (c) the overall time of operations if you need to access the data (or a subset) in sorted order.

With a ConcurrentHashMap, time to perform operations (inserts, removes, updates) is essentially constant whatever the size of the map (with very occasional "blips" when the map needs re-hashing). With ConcurrentSkipListMap, as with a plain TreeMap, the time increases by a roughly constant factor every time the number of items in the map doubles. (On my off-the-shelf AMD dual core, that factor is roughly 1.5.) This means that for most practical sizes and small numbers of concurrent threads, ConcurrentHashMap provides faster access in raw terms (with a size of 16 thousand entries and 4 threads, ConcurrentHashMap is about 4 times faster on my test machine).

However, ConcurrentSkipListMap has at least two interesting features in return for poorer access time:
(1) the keys are kept in sorted order, with fast methods to pull out any sorted subset;
(2) it is highly concurrent: with a given size of map, access time is practically constant however many threads are concurrently accessing it; although ConcurrentHashMap provides "good" concurrency, contention and access times do ultimately increase with concurrency. So although with 4 threads, ConcurrentHashMap is faster in raw terms, there'll reach a certain number of threads where ConcurrentSkipListMap overtakes it. (N.B. In practice, I think this will be scores of threads, though.)

So it depends a bit on if you need constant access time or constant concurrency, and/or permanently sorted keys.

For some measurements on ConcurrentHashMap, you may be interested in an article I put up about the performance of ConcurrentHashMap. I'll be adding similar information about ConcurrentSkipListMap fairly soon.