Java LinkedHashMap: Ordering and LRU Cache Use

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 put or putAll inserts a new entry. 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 after a new insertion, the eldest entry is removed automatically. 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 differs from iterating over a HashMap: the iterator follows the linked list instead of scanning the backing table and its non-empty buckets. The relative cost depends on the table's size and density, so it is not always more expensive. 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 constant cost to operations that move an existing entry, such as get and put on an existing key, because the entry must be unlinked and relinked at the tail. A put that inserts a new key appends it to the tail. 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 will need 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 triggered by new-entry insertions, not by get, so an entry that has not been accessed recently will not be evicted until a later 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, synchronize all access to the map. Collections.synchronizedMap works with a LinkedHashMap subclass because the wrapper delegates put and putAll to the underlying map, where the overridden removeEldestEntry is invoked internally. The returned Map does not expose the protected hook, but eviction still happens. If you prefer a small wrapper that exposes only the methods you need, you can synchronize those methods explicitly.

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

    public SynchronizedLRUCache(final 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 higher throughput, consider ConcurrentHashMap with a custom eviction policy, but that requires more work to maintain order.

Compatibility and Version Notes

LinkedHashMap and the constructor with accessOrder have been available since Java 1.4, so the examples work on modern JDKs. For a specific JDK, check its documentation for implementation notes.

One detail to note: the removeEldestEntry method is invoked after a new 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, add the check to the insertion path yourself, for example by overriding put and putAll, or by wrapping the map in your own Map implementation.