Thread: 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.

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?

Originally Posted by Kerr

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.

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

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?

Originally Posted by Kerr

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.