The java.util.LinkedHashMap is a hash table and linked list implementation of the Map interface. It inherits from HashMap and provides a predictable iteration order, which is normally the order in which keys were inserted into the map (insertion-order).
A HashMap is a collection of "buckets" scattered in memory. A LinkedHashMap is the exact same set of buckets, but it adds a Doubly-Linked List that connects all entries. Every entry "knows" who came before it and who is coming after it.
Provides the logic for put() and get(). Using the key's hashCode(), it jumps to the correct bucket in $O(1)$ time.
Maintains a "head" and "tail" pointer. When you iterate, it follows the chain rather than scanning the buckets, ensuring a consistent order.
One of the most powerful features of LinkedHashMap is that it can be configured to re-order itself based on Access rather than Insertion. This is controlled by a special constructor:
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
get() or put(), that entry moves to the end of the list. The least-accessed items stay at the front.Because of the accessOrder and the method removeEldestEntry(), the LinkedHashMap is the standard way to build an LRU (Least Recently Used) Cache in Java. As the map hits a size limit, it automatically drops the oldest, least-accessed items.
LinkedHashMap performs slightly slower than HashMap for put() and remove() because it has the extra step of updating the linked list pointers. However, iteration is actually faster.
| Operation | LinkedHashMap Complexity | Advantage |
|---|---|---|
| Get/Put | $O(1)$ | Instant lookup, same as HashMap. |
| Iteration | $O(size)$ | Faster than HashMap ($O(capacity)$) when many buckets are empty. |
| Memory | $O(n)$ | Uses ~20-30% more memory than HashMap for pointers. |
This is a frequent "Senior Level" interview task. We will create a cache that only holds 3 items. As soon as a 4th is added, the "Eldest" (oldest/least used) is deleted.
Because the order is guaranteed, iterating is very clean. You can use the `forEach` method introduced in Java 8 for the most readable code:
map.forEach((key, value) -> System.out.println(key + " => " + value));
While elegant, the LinkedHashMap consumes more memory than a standard HashMap. Every single entry must store two extra object references (before and after). In a map with millions of small entries, this overhead can add up to dozens of megabytes of wasted RAM. If you don't care about order, always stick to the standard HashMap.
Q: How does LinkedHashMap preserve insertion order?
A: It maintains a doubly-linked list running through all its entries. Each entry has a before and after pointer that connects it to its chronological neighbors.
Q: What is the main use case for access-order?
A: Implementing caches. It allows the map to keep track of which items were used most recently, enabling the Least Recently Used (LRU) eviction policy.
Q: Can LinkedHashMap have nulls?
A: Yes, it supports one null key and multiple null values, just like its parent HashMap.
The LinkedHashMap is the engineer’s Swiss Army knife for data associations. It provides the speed of hashing, the predictability of a list, and the specialized logic for caching. When you need to provide a consistent view of data to a user or manage memory via an LRU policy, LinkedHashMap is the most efficient and readable choice in the JDK.