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

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:

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

where C is a constant. The complexity says nothing about how small or large the C values are. For two different algorithms, the constant C will most likely be different.

(And remember that big-O complexity is about the behavior / performance as N gets very large. It tells you nothing about the behavior / performance for smaller N values.)

---

Having said that:

• The difference in performance between HashMap and LinkedHashMap operations in equivalent use-cases is relatively small.

• A LinkedHashMap uses more memory. For example, the Java 11 implementation has two additional reference fields in each map entry to represent the before/after list. On a 64 bit platform without compressed OOPs the extra overhead is 16 bytes per entry.

• Relatively small differences in performance and/or memory usage can actually matter a lot to people with performance or memory critical applications¹.

^{1 - ... and also to people who obsess about these things unnecessarily.}