HashMap vs LinkedHashMap vs TreeMap Java | Fresher Interview

All three implement the Map interface, so they share the same basic API, but they differ in ordering and performance. HashMap is the default. It's backed by a bucket array, it gives no ordering guarantee at all, and its get and put are O of one on average. The mistake to avoid is assuming HashMap preserves insertion order; it doesn't, and the iteration order can even change after a resize. LinkedHashMap extends HashMap and additionally threads a doubly linked list through all the entries, so it remembers the order you inserted keys, and iteration follows that order. It's still O of one. It can also run in access-order mode, which is exactly what you want for building an LRU cache, combined with overriding removeEldestEntry. TreeMap is different: it's backed by a red-black tree and keeps the keys in sorted order. That sorting costs you, so its operations are O of log n instead of O of one. But in return you get navigation methods that the others don't have, like floorKey for the largest key less than or equal to a value, ceilingKey for the smallest key greater than or equal, and subMap for a sorted range. So my decision rule is simple. If I just need fast lookups and don't care about order, HashMap. If I need to preserve insertion order or build an LRU cache, LinkedHashMap. If I need sorted keys or range queries, TreeMap, and I accept the log n cost. One more detail: TreeMap doesn't allow a null key, because it has to compare keys to sort them.