LinkedHashMap LRU Cache - Missing removeEldestEntry OOM

HashMap and HashSet are fast but their iteration order is undefined — you get a different order on different JVM runs. LinkedHashMap and LinkedHashSet solve this by maintaining a doubly-linked list through their entries in addition to the hash table.

The most practical consequence: if you need a Map that remembers insertion order (for example, building JSON, preserving request parameter order, or implementing an LRU cache), LinkedHashMap is the right tool.

LinkedHashMap — Insertion Order

LinkedHashMap extends HashMap and adds a doubly-linked list that runs through all entries. The list defines the iteration ordering, which by default is insertion-order: the order in which keys were inserted into the map. This is guaranteed as long as no rehash operations disrupt the list. Rehashing does not change the order because the list is maintained separately from the bucket array.

When you put a key that already exists, the mapping is updated but the entry stays in its original position in the list. This is the key behavior that differs from access-order mode.

package io.thecodeforge.java.collections;

import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapDemo {
    public static void main(String[] args) {
        // Insertion-order map
        Map<String, Integer> scores = new LinkedHashMap<>();
        scores.put("Alice", 95);
        scores.put("Charlie", 88);
        scores.put("Bob", 92);

        // Iteration order = insertion order — always
        scores.forEach((name, score) ->
            System.out.println(name + ": " + score));
        // Alice: 95
        // Charlie: 88
        // Bob: 92

        // HashMap would print in some arbitrary order — not predictable
    }
}

LRU Cache Using Access-Order LinkedHashMap

Pass true as the third constructor argument (accessOrder=true) and override removeEldestEntry to cap the size. This is a textbook LRU cache.

In access-order mode, every get or put moves the accessed entry to the tail of the list. The head of the list is the least recently used entry. When removeEldestEntry returns true (typically when size() exceeds a threshold), that eldest (head) entry is removed. This gives you O(1) get, put, and eviction — but the eviction is lazy, occurring only on new inserts after the threshold is passed.

This implementation is not thread-safe. For a concurrent LRU cache, use Caffeine or Guava's CacheBuilder.

package io.thecodeforge.java.collections;

import java.util.LinkedHashMap;
import java.util.Map;

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

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);  // accessOrder = true
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;  // evict when over capacity
    }

    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);
        cache.put(1, "one");
        cache.put(2, "two");
        cache.put(3, "three");
        System.out.println(cache.keySet()); // [1, 2, 3]

        cache.get(1);  // access 1 — moves to tail (most recently used)
        System.out.println(cache.keySet()); // [2, 3, 1]

        cache.put(4, "four");  // capacity exceeded — removes 2 (least recently used)
        System.out.println(cache.keySet()); // [3, 1, 4]
        System.out.println(cache.containsKey(2)); // false — evicted
    }
}

LinkedHashSet — Insertion-Order Set

LinkedHashSet is backed by a LinkedHashMap (with dummy values). It inherits all properties of HashSet plus a guaranteed iteration order — the order in which elements were inserted.

This is incredibly useful when you need to deduplicate a stream of data while preserving the order of first occurrence. Common use cases include building a list of unique recent actions, maintaining a priority order for a job queue, or generating a unique list of visited URLs in a web crawler.

Like LinkedHashMap, the order is unaffected by rehashing and is consistent over time if no modifications are made.

package io.thecodeforge.java.collections;

import java.util.LinkedHashSet;
import java.util.Set;

public class LinkedHashSetDemo {
    public static void main(String[] args) {
        Set<String> visited = new LinkedHashSet<>();
        visited.add("/home");
        visited.add("/about");
        visited.add("/home");   // duplicate — ignored
        visited.add("/contact");

        System.out.println(visited);  // [/home, /about, /contact]
        // Order preserved, duplicates removed

        // Deduplication while preserving order
        String[] input = {"banana", "apple", "banana", "cherry", "apple"};
        Set<String> deduped = new LinkedHashSet<>(java.util.Arrays.asList(input));
        System.out.println(deduped);  // [banana, apple, cherry]
    }
}

Performance and Memory Overhead

LinkedHashMap and LinkedHashSet have the same O(1) average complexity for add, remove, contains, and get as their parent classes. The only difference is the linked list, which adds two references (prev, next) per entry. On a 64-bit JVM with compressed OOPs, that's about 16 bytes per entry extra.

Iteration over a LinkedHashMap is actually slightly faster than over a HashMap because it traverses the linked list rather than the entire bucket array (which can be sparse). But for very large maps, the extra memory can be significant.

Access-order mode does not add computational overhead on get/put beyond the O(1) operation to move the entry to the tail (which is a constant-time pointer update).

Thread Safety and Synchronization

Like HashMap and HashSet, LinkedHashMap and LinkedHashSet are not thread-safe. If multiple threads access them concurrently and at least one modifies the structure, external synchronization is required.

You can wrap them with Collections.synchronizedMap(new LinkedHashMap(...)), but that only protects individual method calls. Iteration still requires manual synchronization. For an LRU cache that needs concurrency, use java.util.concurrent.ConcurrentHashMap with additional logic, or better, use a dedicated library like Caffeine.

One common pattern is to use a synchronized block around the entire put-get-evict sequence in an LRU cache, but that quickly becomes a bottleneck under high concurrency.

package io.thecodeforge.java.collections;

import java.util.*;

public class SynchronizedLRU<K, V> {
    private final Map<K, V> cache;
    private final int capacity;

    public SynchronizedLRU(int capacity) {
        this.cache = Collections.synchronizedMap(
            new LinkedHashMap<K, V>(capacity, 0.75f, true) {
                @Override
                protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                    return size() > capacity;
                }
            }
        );
        this.capacity = capacity;
    }

    // But iteration is not thread-safe; you must synchronize on cache
    public List<Map.Entry<K, V>> snapshot() {
        synchronized (cache) {
            return new ArrayList<>(cache.entrySet());
        }
    }
}

Frequently Asked Questions