☕ JavaCollections Framework

LinkedHashMap

LinkedHashMap extends HashMap and maintains a doubly-linked list running through all its entries, preserving the order in which entries were inserted. Iteration over a LinkedHashMap always returns entries in insertion order. Optionally, it can be constructed in access-order mode where entries are ordered by most-recently accessed, making it the perfect foundation for implementing a Least Recently Used (LRU) cache. LinkedHashMap has slightly higher memory overhead than HashMap due to the extra linked list pointers.

How LinkedHashMap Maintains Order

LinkedHashMap inherits all of HashMap's buckets-and-chains structure but augments each entry node with two additional pointers: before and after. These form a doubly-linked list that runs through all entries in the map, independent of the bucket structure. The LinkedHashMap maintains a head (oldest entry) and tail (newest entry) for this doubly-linked list. When a new entry is added, it is appended to the tail of the doubly-linked list. When an entry is removed, its before and after pointers are updated to skip it, maintaining list integrity. Iterating over entrySet(), keySet(), or values() follows this doubly-linked list from head to tail, producing entries in the preserved order rather than the arbitrary bucket order of a plain HashMap. LinkedHashMap has two ordering modes: insertion order (default, where the list orders by when each key was first inserted) and access order (enabled by the third constructor parameter, where any get() or put() moves the accessed entry to the tail, making the head the least recently accessed entry). In insertion-order mode, re-inserting an existing key (calling put() with a key already in the map) updates the value but does not change the key's position in the order — the original insertion order is preserved. Only genuinely new keys move to the tail. This makes LinkedHashMap's insertion-order the order of first insertion for each unique key.

Java

// ── LinkedHashMap preserves insertion order: ─────────────────────────
Map<String, Integer> linked = new LinkedHashMap<>();
linked.put("Charlie", 3);
linked.put("Alice",   1);
linked.put("Bob",     2);

System.out.println(linked);   // {Charlie=3, Alice=1, Bob=2}
// Insertion order is preserved — NOT alphabetical

// Compare with HashMap (unpredictable order):
Map<String, Integer> hash = new HashMap<>();
hash.put("Charlie", 3);
hash.put("Alice",   1);
hash.put("Bob",     2);
System.out.println(hash);     // {Bob=2, Charlie=3, Alice=1} — arbitrary

// ── Re-insert does NOT change position: ──────────────────────────────
linked.put("Charlie", 99);   // updates value, order unchanged
System.out.println(linked);  // {Charlie=99, Alice=1, Bob=2} — Charlie still first

// ── Iteration in insertion order: ────────────────────────────────────
for (Map.Entry<String, Integer> e : linked.entrySet()) {
    System.out.printf("%-10s → %d%n", e.getKey(), e.getValue());
}
// Charlie    → 99
// Alice      → 1
// Bob        → 2

// ── Access-order mode: ────────────────────────────────────────────────
// Constructor: LinkedHashMap(initialCapacity, loadFactor, accessOrder)
Map<String, Integer> accessOrder = new LinkedHashMap<>(16, 0.75f, true);
accessOrder.put("a", 1);
accessOrder.put("b", 2);
accessOrder.put("c", 3);
System.out.println(accessOrder);  // {a=1, b=2, c=3}

accessOrder.get("a");             // access "a" — moves to tail
System.out.println(accessOrder);  // {b=2, c=3, a=1} — "a" moved to end

accessOrder.get("c");             // access "c" — moves to tail
System.out.println(accessOrder);  // {b=2, a=1, c=3}
// Head is LRU (least recently used) — "b" was accessed least recently

LRU Cache Implementation with LinkedHashMap

Access-order LinkedHashMap with removeEldestEntry() overridden is the simplest and most efficient way to implement a Least Recently Used cache in Java. The removeEldestEntry() hook method is called after each put() and gives you the chance to evict the oldest entry. In access-order mode, the oldest entry is the one accessed least recently. The LRU cache keeps the most recently used entries and evicts the least recently used when capacity is reached. Access-order LinkedHashMap achieves this because every get() or put() moves the accessed entry to the tail. The head is therefore always the LRU entry. removeEldestEntry() is called with the head entry (eldest), and if you return true, LinkedHashMap removes it automatically. This pattern produces a fully functional LRU cache in approximately ten lines of code, with O(1) get and put. The LRU cache is useful for caching expensive computations, database query results, or remote API responses where some keys are accessed much more frequently than others and you need to bound memory usage. The protected removeEldestEntry() hook is the cleanest Java design for this — it is an extension point that the framework calls, and the subclass defines policy. This is the Template Method pattern in action. The framework controls when to check (after each put) and the hook defines whether to evict.

Java

// ── LRU Cache using LinkedHashMap: ───────────────────────────────────
public class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxCapacity;

    public LruCache(int maxCapacity) {
        super(maxCapacity, 0.75f, true);  // true = access-order
        this.maxCapacity = maxCapacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // Called after each put() — remove head (LRU) when over capacity:
        return size() > maxCapacity;
    }
}

// ── Using the LRU cache: ──────────────────────────────────────────────
LruCache<Integer, String> cache = new LruCache<>(3);
cache.put(1, "one");
cache.put(2, "two");
cache.put(3, "three");
System.out.println(cache);   // {1=one, 2=two, 3=three}

cache.get(1);                // access key 1 — moves to tail (most recent)
System.out.println(cache);   // {2=two, 3=three, 1=one}

cache.put(4, "four");        // capacity exceeded — evicts LRU (key 2)
System.out.println(cache);   // {3=three, 1=one, 4=four}  — key 2 evicted

cache.put(5, "five");        // evicts LRU (key 3)
System.out.println(cache);   // {1=one, 4=four, 5=five}

// ── Thread-safe LRU cache: ────────────────────────────────────────────
Map<Integer, String> syncCache = Collections.synchronizedMap(
    new LruCache<>(100));
// Individual operations are thread-safe; iteration still needs sync.

// ── Practical: computeIfAbsent for cache-aside pattern: ───────────────
LruCache<String, User> userCache = new LruCache<>(500);

public User getUser(String userId) {
    return userCache.computeIfAbsent(userId, id -> database.findUser(id));
    // Cache miss → calls database.findUser → caches result
    // Cache hit  → returns cached value without touching database
}

LinkedHashMap

How LinkedHashMap Maintains Order

LRU Cache Implementation with LinkedHashMap

Related Topics in Collections Framework