Datastructure : hashmap vs linkedhashmap vs treemap

Question

I saw there are a lot of questions about the differences between these three. Tell me if I am wrong, but if I sum up what I could read:

• Hashmap : will be more efficient in general; O(1) (normal case), O(N) (worst case, only with bad hash algorithm)
• LinkedHashmap : maintains insertion order of elements, take more memory than hashmap
• Treemap : maintains elements sorted, O(log(n)) (when balanced)

My question is : Why do we need to maintain insertion order or elements sorted, if at the end the performance to insert, lookup.. are better with hashmap?

Answer 1

We sometimes need to main insertion order because we need the insertion order to solve the problem at hand. Sounds a bit tautological, but that's really pretty much the reason. Some data is ordered but also benefits from random access.

Likewise for sorting. It gives a way to find the "next" or "previous" item very cheaply, while still being reasonably efficient for arbitrary lookup. One example are approximate lookups, say, you know the entry you're looking for starts with Foo but you don't know what the rest of the key is.

Hashmap exists to make things faster and simpler (no concept of order) when you don't need any of these operations, only exact lookup.

Answer 2

I use Treemap and LinkedHashMap because, while I can sort a HashMap myself, I doubt my solution will be as fast or memory efficient as Java's.