How is the implementation of LinkedHashMap different from HashMap?

Question

If LinkedHashMap's time complexity is same as HashMap's complexity why do we need HashMap? What are all the extra overhead LinkedHashMap has when compared to HashMap in Java?

Answer 1

LinkedHashMap will take more memory. Each entry in a normal HashMap just has the key and the value. Each LinkedHashMap entry has those references and references to the next and previous entries. There's also a little bit more housekeeping to do, although that's usually irrelevant.

Answer 2

• LinkedHashMap additionally maintains a doubly-linked list running through all of its entries, that will provide a reproducable order. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).
• HashMap doesn't have these extra costs (runtime,space) and should prefered over LinkedHashMap when you don't care about insertion order.

Answer 3

LinkedHashMap is useful datastructure when you need to know the insertion order to the Map. One suitable use case is for the implementation of an LRU cache. Due to order maintainence of the LinkedHashMap, the performance of the datastructure is slightly lower compared to that of a randomized Map such as HashMap. In case you do not need to know the insertion order, you should always go for the HashMap for better performance.

Answer 4

If LinkedHashMap's time complexity is same as HashMap's complexity why do we need HashMap?

You should not confuse complexity with performance. Two algorithms can have the same complexity, yet one can consistently perform better than the other.

Remember that f(N) is O(N) means that:

C1*N <= limit(f(N), N -> infinity) <= C2*N  

where C1 and C2 are strictly positive constants. The complexity says nothing about how small or large the C values are.