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 and LinkedHashSet: The Predictable Iteration Order That Can Cost You Memory

LinkedHashMap and LinkedHashSet are Java's hash-based collections that maintain a doubly linked list running through their entries, giving them predictable iteration order — either insertion-order or access-order. Unlike HashMap or HashSet, which offer no ordering guarantees, these classes let you iterate in the order entries were added or last accessed. The core mechanic is a linked list that shadows the hash table, adding O(1) overhead for each put/get but preserving order without requiring a separate sort.

In practice, LinkedHashMap's access-order mode (via constructor accessOrder=true) combined with removeEldestEntry makes it a ready-made LRU cache. Each get or put moves the accessed entry to the tail; the eldest entry (head) is evicted when removeEldestEntry returns true. The default implementation always returns false — a common oversight that silently turns your cache into a memory leak. LinkedHashSet is simply a LinkedHashMap with a dummy value, inheriting the same ordering behavior.

Use LinkedHashMap when you need predictable iteration without the overhead of TreeMap's O(log n) operations, or when building an LRU cache with bounded memory. LinkedHashSet is ideal for deduplication where insertion order matters, like maintaining a unique event log. In production, the access-order variant is the go-to for caches up to tens of thousands of entries; beyond that, consider a dedicated cache library with more sophisticated eviction policies.

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());
        }
    }
}

Why the Underlying Doubly-Linked List Changes Your GC Behavior

Most devs treat LinkedHashMap like 'HashMap with order'. That's dangerous. The linked list that gives you predictable iteration also pins every entry in memory. Each Entry object carries two extra references (before, after) plus the next pointer from the HashMap bucket chain. That's three pointers per entry versus one in a plain HashMap. In high-throughput services with millions of cached objects, those extra references bloat the young generation and increase GC pause frequency. I once saw a Spring Boot 3.1 service crater under load because a LinkedHashMap used for a session cache kept every object tenured long before it was needed. The fix: use a HashMap with manual eviction or a Caffeine cache that uses weak references. If you absolutely need insertion order, set an explicit max size and enable removeEldestEntry to force eviction. Otherwise, you're paying for iteration order you rarely iterate.

// io.thecodeforge
import java.util.*;

public class LinkedHashMapMemoryFootprint {
    // Compare memory: 1M entries
    public static void main(String[] args) {
        // LinkedHashMap: ~ 88 MB (Java 17, compressed oops)
        Map<String, String> ordered = new LinkedHashMap<>();
        // HashMap: ~ 72 MB
        Map<String, String> unordered = new HashMap<>();

        for (int i = 0; i < 1_000_000; i++) {
            String key = "key-" + i;
            String val = "val-" + i;
            ordered.put(key, val);
            unordered.put(key, val);
        }

        // Force GC to get approximate heap usage
        System.gc();
        Runtime rt = Runtime.getRuntime();
        long orderedMem = rt.totalMemory() - rt.freeMemory();

        unordered.clear();
        System.gc();
        long unorderedMem = rt.totalMemory() - rt.freeMemory();

        System.out.println("LinkedHashMap: " + orderedMem / 1_048_576 + " MB");
        System.out.println("HashMap:       " + unorderedMem / 1_048_576 + " MB");
        System.out.println("Overhead:      " + (orderedMem - unorderedMem) / 1_048_576 + " MB");
    }
}

When Iteration Order Lies: Access-Order LinkedHashMap Under Concurrency

Access-ordered LinkedHashMap is seductive for LRU caches. You call get(), the entry moves to the end of the list. Simple. Wrong. The access-order modification is not atomic with the get operation. Under concurrent access, two threads reading the same key can both trigger structural modifications to the linked list. Even with ConcurrentHashMap's segment locks, LinkedHashMap's internal list is unprotected. You'll see the classic ConcurrentModificationException or, worse, silent data corruption where iteration returns null or skips entries. In Spring Boot 3.x, I debugged a rate-limiter that used an access-ordered LinkedHashMap. Under load test with 500 concurrent users, the cache returned wrong ordering every third request. We replaced it with a ConcurrentLinkedDeque + ConcurrentHashMap pair. That gave us LRU semantics without the linked-list race. If you need thread-safe access order, avoid the OOTB LinkedHashMap. Roll your own with synchronization or use a library like Guava's CacheBuilder.

// io.thecodeforge
import java.util.*;
import java.util.concurrent.*;

public class ConcurrentAccessOrderBug {
    public static void main(String[] args) throws Exception {
        Map<String, String> lru = new LinkedHashMap<>(16, 0.75f, true);
        lru.put("A", "1");
        lru.put("B", "2");
        lru.put("C", "3");

        ExecutorService pool = Executors.newFixedThreadPool(10);
        // Simulates concurrent cache access
        for (int i = 0; i < 100; i++) {
            pool.submit(() -> {
                String val = lru.get("A");  // modifies access order
                if (val == null) {
                    System.err.println("BROKEN: null returned for key A");
                }
            });
        }
        pool.shutdown();
        pool.awaitTermination(5, TimeUnit.SECONDS);

        System.out.println("Final iteration order: " + lru.keySet());
        // May print: [A, B, C] or throw ConcurrentModificationException
    }
}