Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 8 of 8

Thread: TreeMap vs HashMap

  1. #1
    Member
    Join Date
    Mar 2011
    Location
    Earth!
    Posts
    77
    Thanks
    2
    Thanked 1 Time in 1 Post

    Default TreeMap vs HashMap

    Hi all.

    I have been wondering about TreeMaps and HashMaps for a while. Here is what I have understood from the javadocs.

    TreeMap is based on a a form of binary tree (red-back tree?). TreeMap is also sorted, and has an usage time, or whatever the proper term is, of log(n) for get, out, remove and containsKey. After testing a bit it appears to permit null values, but not null keys.

    HashMap is more like an array where elements are found/added/removed based on hashes (basically a hash table). It has a more or less constant performance for basic operations, get and put. Permits both null keys and values.

    None of are thread safe, and both of them are fail fast, meaning that if you use and iterator and then modify the collection then the iterator will throw an exception (unless you modified it with the iterators remove method).

    So my question is, how do they compare to each other? How do their performance compare to each other? When is which one appropriate to use? When should they not be used? I know it is a theoretical question, but it is something I want to understand, and any answers would be appriciated.

    Take care,
    Kerr.
    Last edited by Kerr; March 9th, 2011 at 06:27 AM.


  2. #2
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    4,972
    My Mood
    Hungover
    Thanks
    133
    Thanked 555 Times in 476 Posts

    Default Re: TreeMap vs HashMap

    From the API for TreeMap: This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.

    From the API for HashMap: This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings).

    TreeMaps preserve order, at the cost of lookup and placement time.

    Does that answer your question?
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  3. #3
    Member
    Join Date
    Mar 2011
    Location
    Earth!
    Posts
    77
    Thanks
    2
    Thanked 1 Time in 1 Post

    Default Re: TreeMap vs HashMap

    So, basically it is best to use HashMap unless you are interested in preserving order?

  4. #4
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    4,972
    My Mood
    Hungover
    Thanks
    133
    Thanked 555 Times in 476 Posts

    Default Re: TreeMap vs HashMap

    Quote Originally Posted by Kerr View Post
    So, basically it is best to use HashMap unless you are interested in preserving order?
    It really depends on context, but I'd say that's a fair enough statement.
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  5. #5
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: TreeMap vs HashMap

    One thing to keep in mind about hash maps: They're fairly good at telling you if something is in them, but poor at determining if something is not in them (depending on the way their implementation handles collisions), and even worse at determining the order of the items inside (as already stated). In most simple hash map implementations checking if an item is not in the hash map requires O(m), where m is the size of the array holding the hashed items, not the number of items in the hash map. I wouldn't be surprised if Java does a better job of handling collisions than the simple case, but it's not something you should count on, and likely won't give you too much of a boost over the simple case performance-wise. Also, you must have a good hashing function to get an optimal hash map (i.e. avoid as many collisions as possible), where-as tree maps are a "dumb" data structure (i.e. you can give it pretty much anything and it will give you roughly the same performance every time).
    Last edited by helloworld922; March 9th, 2011 at 04:33 PM.

  6. #6
    Member
    Join Date
    Mar 2011
    Location
    Earth!
    Posts
    77
    Thanks
    2
    Thanked 1 Time in 1 Post

    Default Re: TreeMap vs HashMap

    Thanks .

    helloworld922, about that hash function thing, does this mean that if I make a class that I use as a key, I should provide my own hash function?
    Last edited by Kerr; March 10th, 2011 at 04:30 AM.

  7. #7
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    4,972
    My Mood
    Hungover
    Thanks
    133
    Thanked 555 Times in 476 Posts

    Default Re: TreeMap vs HashMap

    Quote Originally Posted by Kerr View Post
    Thanks .

    helloworld922, about that hash function thing, does this mean that if I make a class that I use as a key, I should provide my own hash function?
    I'll answer this one even though you directed it towards helloworld922. Hope he doesn't mind.

    You don't have to write your own hash function- there's already a hashcode() function in Object, which every other Object inherits. However, if you override equals(), and you're using the class in a hash, then you should override the hashcode() function (or vice versa) to make sure that the contracts are preserved.

    I'd recommend a quick google of "java override hashcode". The links explain it better than I can.
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  8. The Following User Says Thank You to KevinWorkman For This Useful Post:

    Kerr (March 10th, 2011)

  9. #8
    Member
    Join Date
    Mar 2011
    Location
    Earth!
    Posts
    77
    Thanks
    2
    Thanked 1 Time in 1 Post

    Default Re: TreeMap vs HashMap

    Ok, thanks, will take a look.

Similar Threads

  1. [SOLVED] TreeSet to TreeMap Problem
    By MoniD in forum What's Wrong With My Code?
    Replies: 4
    Last Post: January 25th, 2011, 12:27 PM
  2. Problem in HashMap
    By Hikari9 in forum Collections and Generics
    Replies: 2
    Last Post: April 19th, 2010, 10:44 PM
  3. treemap Duplicates
    By debug in forum What's Wrong With My Code?
    Replies: 3
    Last Post: March 6th, 2010, 10:52 AM
  4. Student TreeMap
    By raphytaffy in forum Algorithms & Recursion
    Replies: 6
    Last Post: March 1st, 2010, 11:11 PM
  5. Bitstrings vs Hashmap
    By April in forum Collections and Generics
    Replies: 3
    Last Post: February 2nd, 2010, 10:56 AM