Results 1 to 3 of 3
  1. #1
    stsm is offline Member
    Join Date
    Dec 2008
    Posts
    1
    Rep Power
    0

    Default HashMap vs. SkipListMap

    Hello,

    i'm wondering what will be faster:

    ConcurrentHashMap< String, String >

    or:

    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?

    Thank you

  2. #2
    Nicholas Jordan's Avatar
    Nicholas Jordan is offline Senior Member
    Join Date
    Jun 2008
    Location
    Southwest
    Posts
    1,018
    Rep Power
    8

    Cool research / thesis op

    Quote Originally Posted by stsm View Post
    .... advantages and disadvantages of them and what about the costs for insert/delete/retrieve?..
    Probabalistic data structures are a relatively new addition to Java, I suggest everyone get their test code ready as this is going to be fun fun fun till the anti-bean tries to fudge the data by putting lucid, verbose, detailed explainations of, ahem, "how it works" without any testing anywhere......

    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

  3. #3
    neilcoffey is offline Senior Member
    Join Date
    Nov 2008
    Posts
    286
    Rep Power
    7

    Default 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.

Similar Threads

  1. Hashmap to TXT and TXT to Hashmap
    By elvinny in forum Advanced Java
    Replies: 4
    Last Post: 02-17-2011, 12:12 AM
  2. hashmap
    By tOpach in forum New To Java
    Replies: 2
    Last Post: 09-24-2008, 01:55 PM
  3. what is hashmap
    By gabriel in forum New To Java
    Replies: 5
    Last Post: 08-03-2007, 02:23 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •