Results 1 to 3 of 3
Thread: HashMap vs. SkipListMap
- 12-01-2008, 08:42 PM #1Member
- Join Date
- Dec 2008
- Rep Power
HashMap vs. SkipListMap
i'm wondering what will be faster:
ConcurrentHashMap< String, String >
ConcurrentSkipListSet< String, String >
apart from the key ordering of the SkipList, what are the advantages and disadvantages of them and what about the costs for insert/delete/retrieve?
- 12-02-2008, 12:57 AM #2
research / thesis op
Hmmmm, probablistic data structure - has obvious application in sampling streams under load for sampling, to get order O(log n) average time for most operations on a list, they likely will have some other data structure driving the ( supposed ) list. ( think suppository )
Much more fun than the closest common ancestor in Inheritance, and likely to produce some valuable research work. Have you read anything about the question at hand or an application arena to consider your design paradim?
A question like that with no backdop is like a candy drop on a sidewalk, sorta sticky...... makes excellent thesis material.Introduction to Programming Using Java.
Cybercartography: A new theoretical construct proposed by D.R. Fraser Taylor
- 12-10-2008, 01:58 AM #3Senior Member
- Join Date
- Nov 2008
- Rep Power
Constant concurrency vs constant access time (roughly!)
@stsm -- 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.Neil Coffey
Javamex - Java tutorials and performance info