Java LinkedHashMap: Ordering and LRU Cache Use

java linkedhashmap requires a clear understanding of the core syntax, runtime behavior, and practical implementation patterns demonstrated in the examples below.

Java's LinkedHashMap is a Map implementation that combines the hash-based lookup of HashMap with a doubly-linked list running through its entries. The list gives the map a predictable iteration order, which HashMap does not guarantee. That order can be either the order in which keys were inserted, or the order in which entries were last accessed. The latter mode makes LinkedHashMap a convenient foundation for a simple LRU cache.

How LinkedHashMap Differs from HashMap

HashMap stores entries in an array of nodes, and the position of each node depends on the hash code of the key. Iterating over a HashMap produces entries in the order the nodes happen to appear in the backing table, which is effectively arbitrary. LinkedHashMap extends HashMap and adds a linked list that connects every entry in a defined sequence. The sequence is maintained independently of the hash buckets, so iteration always follows that sequence, regardless of how entries are distributed across the table.

The extra bookkeeping costs memory. Each entry in a LinkedHashMap carries two additional references, one to the entry that precedes it and one to the entry that follows it. For maps with a large number of entries, this overhead is measurable. The time complexity of get and put remains O(1) on average, just like HashMap, but the maintenance of the linked list adds a small constant factor to those operations.

Insertion Order vs. Access Order

The constructor LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) lets you choose the ordering mode. When accessOrder is false, the default, the map iterates in insertion order. When it is true, every successful get or put moves the accessed entry to the end of the linked list, so iteration reflects the order of most recent access.

Map<String, Integer> insertionOrder = new LinkedHashMap<>();
insertionOrder.put("a", 1);
insertionOrder.put("b", 2);
insertionOrder.put("c", 3);
// Iteration order: a, b, c

Map<String, Integer> accessOrder = new LinkedHashMap<>(16, 0.75f, true);
accessOrder.put("a", 1);
accessOrder.put("b", 2);
accessOrder.put("c", 3);
accessOrder.get("a");
// Iteration order now: b, c, a

In access-order mode, calling get on an existing key moves that entry to the tail. Calling put on an existing key also counts as an access and moves the entry. Calling put on a new key appends it to the tail. The remove operation does not reorder the remaining entries.

Using LinkedHashMap as an LRU Cache

The access-order mode is the key to building a least-recently-used cache. When the map reaches a maximum size, you want to evict the entry that has not been accessed for the longest time. That entry is always at the head of the linked list because every access moves the touched entry to the tail. The only remaining task is to remove the head when the size exceeds a threshold.

LinkedHashMap provides a protected method, removeEldestEntry(Map.Entry eldest), that is called after every put and putAll. The default implementation returns false, so the map never removes entries. Overriding it to return true when the size exceeds a limit gives you a working LRU cache.

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;

    public LRUCache(int maxSize) {
        super(16, 0.75f, true);
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }
}

When the map exceeds maxSize, the eldest entry is removed automatically after the insertion. The eldest parameter is the entry that would be removed, which is the head of the linked list. This approach is thread-safe only if you synchronize externally, as LinkedHashMap is not designed for concurrent access.

Iteration and Performance Considerations

Iterating over a LinkedHashMap is slightly more expensive than iterating over a HashMap because the iterator must follow the linked list instead of scanning the backing array. The difference is usually small, but it becomes relevant when you iterate frequently over large maps. The main advantage is that the iteration order is stable and meaningful. If your algorithm relies on the order of keys, LinkedHashMap gives you that without the cost of sorting or maintaining a separate list.

Access-order mode adds a small cost to every get and put because the entry must be unlinked and relinked at the tail. This is a constant-time operation, but it involves more pointer updates than a plain HashMap lookup. For a cache, this cost is acceptable because the eviction policy is simple and correct.

Choosing Between HashMap and LinkedHashMap

Use HashMap when you do not care about iteration order and you want the smallest memory footprint and the fastest possible operations. Use LinkedHashMap when you need predictable iteration order, either insertion order or access order, and you can accept the extra memory and slight overhead. A typical case is building a cache, where access order is required for LRU behavior. Another case is producing a map that can be iterated in the same order entries were added, which is useful for configuration maps or query parameters.

If you need thread safety, neither HashMap nor LinkedHashMap is safe for concurrent modification. You can wrap them with Collections.synchronizedMap, but that locks the entire map. For higher concurrency, consider ConcurrentHashMap, but that class does not maintain any order. If you need both order and concurrency, you must build a custom solution, often by combining a ConcurrentHashMap with a separate ordered structure.

Common Pitfalls and Limitations

One common mistake is assuming that LinkedHashMap is thread-safe because it maintains order. It is not. Concurrent access can corrupt the linked list and produce infinite loops or lost entries. Always synchronize externally or use a thread-safe wrapper.

Another pitfall is relying on the order after modifying the map in access-order mode. If you call get on a key, the iteration order changes. Code that assumes a fixed order will break. In insertion-order mode, put on an existing key does not change the order, but put on a new key appends it to the end. Removing a key and re-adding it moves it to the end, which may surprise developers who expect the original position to be preserved.

The removeEldestEntry method is called only after put and putAll. It is not called after get, so an entry that has not been accessed recently will not be evicted until the next insertion. If you need to evict entries based on time or other criteria, you must implement that logic separately.

Building a Thread-Safe LRU Cache with LinkedHashMap

If you need a thread-safe LRU cache, you can synchronize access to a LinkedHashMap instance. The simplest approach is to use Collections.synchronizedMap, but that returns a Map that does not expose the removeEldestEntry hook. Instead, you can wrap your LinkedHashMap subclass and synchronize all methods that modify or read the map.

class SynchronizedLRUCache<K, V> {
    private final LinkedHashMap<K, V> map;

    public SynchronizedLRUCache(int maxSize) {
        this.map = new LinkedHashMap<K, V>(16, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > maxSize;
            }
        };
    }

    public synchronized V get(K key) {
        return map.get(key);
    }

    public synchronized void put(K key, V value) {
        map.put(key, value);
    }

    public synchronized int size() {
        return map.size();
    }
}

This wrapper ensures that all operations that could modify the linked list are serialized. For a cache with low contention, this is sufficient. For high throughput, consider ConcurrentHashMap with a custom eviction policy, but that requires more work to maintain order.

Compatibility and Version Notes

LinkedHashMap has been part of the Java standard library since Java 1.4. Its behavior has remained stable across versions. The constructor with accessOrder and the removeEldestEntry method have not changed. If you are using a modern JDK, you can rely on the same semantics. There is no version-specific behavior that would affect the patterns shown here.

One detail to note: the removeEldestEntry method is called by put and putAll after the entry is inserted. In a subclass, you can inspect the eldest entry to decide whether to evict it, but you cannot prevent the insertion itself. If you need to reject an insertion before it happens, you must override put and check the size beforehand.