java.util.LinkedHashMap<K, V> does exactly one thing that HashMap cannot: it guarantees that iteration always produces entries in the order they were inserted. That single addition — a doubly-linked list threading every entry in insertion sequence — is what separates the two. When an API response must return items in the order they were added, or when a cache needs to evict the least-recently-used entry, LinkedHashMap is the correct data structure.

What Is Java LinkedHashMap?

LinkedHashMap<K, V> is a concrete class in java.util that extends HashMap<K, V> and implements Map<K, V>. It inherits everything from HashMap — the same hash table, the same O(1) average operations, the same load factor and resize behaviour — and adds a doubly-linked list that threads all entries together in a defined order.

The diagram below shows where LinkedHashMap fits in the Map hierarchy.

java.util.Map<K, V>                          ← key-value contract
    ├── java.util.HashMap<K, V>              ← hash table, NO order
    │       └── java.util.LinkedHashMap<K,V> ← THIS CLASS: hash table + linked list
    ├── java.util.SortedMap<K, V>
    │       └── NavigableMap<K, V>
    │               └── TreeMap<K, V>        ← Red-Black tree, sorted by key
    └── java.util.Hashtable<K, V>            ← legacy, synchronised

KEY FACTS:
  Package    : java.util
  Since      : Java 1.4
  Extends    : HashMap<K, V>
  Implements : Map<K, V>, Cloneable, Serializable
  Ordering   : INSERTION ORDER (default) or ACCESS ORDER (constructor flag)
  Null keys  : exactly ONE null key allowed
  Null values: unlimited
  Thread-safe: NO — use Collections.synchronizedMap() or external locking
  Default capacity   : 16 buckets (inherited from HashMap)
  Default load factor: 0.75 (inherited from HashMap)

Basic Overview — The Two-Layer Structure

LinkedHashMap combines two data structures: the hash table from HashMap (for O(1) lookup) and a doubly-linked list (for ordered iteration).

LINKEDHASHMAP INTERNAL STRUCTURE with entries:
  put("C", 3), put("A", 1), put("B", 2)

  HASH TABLE (inherited from HashMap):
    table[0]: null
    table[1]: Entry("A", 1) → null
    table[2]: Entry("C", 3) → null
    table[3]: Entry("B", 2) → null
    ...

  DOUBLY-LINKED LIST (new in LinkedHashMap — maintains insertion order):
    head ↔ [Entry("C",3)] ↔ [Entry("A",1)] ↔ [Entry("B",2)] ↔ tail
              first added         second             third

  Each Entry has FIVE fields (vs HashMap's four):
    int  hash       ← bucket lookup (HashMap)
    K    key        ← key reference (HashMap)
    V    value      ← value reference (HashMap)
    Entry next      ← next in bucket chain (HashMap)
    Entry before    ← previous in insertion-order list (LinkedHashMap ONLY)
    Entry after     ← next in insertion-order list (LinkedHashMap ONLY)

  Iteration follows BEFORE → AFTER pointers — always C, A, B.
  HashMap iteration scans bucket array — unpredictable order.

  MEMORY COST:
    Each LinkedHashMap Entry is ~2 references larger than HashMap Entry.
    On a 64-bit JVM with compressed references: ~8 extra bytes per entry.

Two Ordering Modes

LinkedHashMap supports two distinct ordering strategies, selected at construction time.

MODE 1 — INSERTION ORDER (default):
  new LinkedHashMap<>()
  Entries iterate in the order put() was first called.
  Re-inserting an existing key does NOT change its position.
  put("A", 1); put("B", 2); put("A", 99);  → iterates A(99), B(2)

  USE FOR:
    Deterministic API responses, audit logs, deduplication with order

MODE 2 — ACCESS ORDER:
  new LinkedHashMap<>(capacity, loadFactor, true)  ← third arg = accessOrder
  Every get() and put() on an existing key moves that entry to the TAIL.
  Most-recently-accessed entry is always at the tail.
  Least-recently-accessed entry is always at the head.

  get("A") moves A to tail.
  put("B", newValue) moves B to tail.
  The HEAD always holds the LRU (least recently used) candidate.

  USE FOR:
    LRU cache implementation — override removeEldestEntry() to cap size

When to Use LinkedHashMap

USE LinkedHashMap WHEN:
  1. Iteration order must match insertion order
     — API response bodies where field order matters
     — Deduplication where "first seen wins" position must be preserved
     — Configuration maps where insertion order reflects priority

  2. LRU cache is needed
     — access-order mode + removeEldestEntry() = self-evicting LRU cache
     — avoids external cache libraries for simple bounded caches

  3. Deterministic iteration for tests or output
     — HashMap iteration order is undefined; LinkedHashMap is predictable
     — unit tests that assert map contents as strings benefit from stable order

USE HashMap INSTEAD WHEN:
  - Insertion order is irrelevant
  - Maximum raw speed is required (HashMap is marginally faster — no linked list maintenance)
  - Memory is tight (LinkedHashMap's ~8 extra bytes per entry adds up at millions of entries)

USE TreeMap INSTEAD WHEN:
  - Sorted key order (alphabetical, numeric, custom Comparator) is needed
  - Range operations: headMap(), tailMap(), floor(), ceiling()

USE ConcurrentHashMap INSTEAD WHEN:
  - Multiple threads read and write simultaneously
  - LinkedHashMap is not thread-safe

How LinkedHashMap Works Internally

Insertion Order — How the Linked List Is Maintained

Every put() call that adds a new key appends a new Entry to the tail of the doubly-linked list. Re-inserting a key that already exists updates the value but leaves the entry's position in the linked list unchanged.

INSERTION SEQUENCE: put("X",1), put("Y",2), put("Z",3)

  After put("X", 1):
    head ↔ [X,1] ↔ tail

  After put("Y", 2):
    head ↔ [X,1] ↔ [Y,2] ↔ tail

  After put("Z", 3):
    head ↔ [X,1] ↔ [Y,2] ↔ [Z,3] ↔ tail

  put("X", 99)  — update existing key:
    X's value changes to 99, BUT its position does NOT move.
    head ↔ [X,99] ↔ [Y,2] ↔ [Z,3] ↔ tail

  remove("Y"):
    Y's before.after = Y.after   (X.after = Z)
    Y's after.before = Y.before  (Z.before = X)
    head ↔ [X,99] ↔ [Z,3] ↔ tail   ← O(1) pointer surgery

Access Order — How LRU Tracking Works

With access-order enabled, every get() and every put() on an existing key calls afterNodeAccess(), which unlinks the accessed entry from its current position and relinks it at the tail.

ACCESS ORDER SEQUENCE:
  new LinkedHashMap<>(16, 0.75f, true)
  put("A",1); put("B",2); put("C",3); put("D",4)

  Initial linked list (insertion order = access order initially):
    head ↔ [A] ↔ [B] ↔ [C] ↔ [D] ↔ tail
    HEAD = A (LRU candidate — least recently touched)

  get("A")  — moves A to tail (most recently used):
    head ↔ [B] ↔ [C] ↔ [D] ↔ [A] ↔ tail

  get("C")  — moves C to tail:
    head ↔ [B] ↔ [D] ↔ [A] ↔ [C] ↔ tail

  put("B", 99) — B already exists; moves to tail (access-order treat):
    head ↔ [D] ↔ [A] ↔ [C] ↔ [B] ↔ tail
    HEAD = D  ← Least Recently Used — will be evicted first

  removeEldestEntry() checks the head entry:
    If size > MAX_SIZE → remove head (D) → LRU eviction

removeEldestEntry() — The Self-Evicting Cache Hook

LinkedHashMap provides a protected method specifically for LRU cache construction.

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false; // default: never auto-remove
}

Override it to implement auto-eviction:

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return size() > MAX_SIZE; // remove head entry when over capacity
}

FLOW on put():
  1. New entry appended to tail (access-order: or existing moved to tail)
  2. afterNodeInsertion() called
  3. If removeEldestEntry(head) returns true:
     → Remove the head entry (the LRU candidate)
     → Both hash table bucket and linked list updated
  4. Net result: size stays at MAX_SIZE, oldest entry evicted

Core Operations with Examples

Insertion Order — Predictable Iteration

Java

// File: LinkedHashMapInsertionOrderDemo.java

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

public class LinkedHashMapInsertionOrderDemo {

    public static void main(String[] args) {

        // Default constructor — insertion-order mode
        Map<String, Integer> menuOrder = new LinkedHashMap<>();

        menuOrder.put("Starters",  1);
        menuOrder.put("Main Course", 2);
        menuOrder.put("Beverages",  3);
        menuOrder.put("Desserts",   4);

        System.out.println("=== Insertion-order iteration ===");
        menuOrder.forEach((section, order) ->
            System.out.println("  " + order + ". " + section));

        // Re-inserting an existing key updates value but preserves position
        System.out.println("\n=== Re-insertion preserves position ===");
        menuOrder.put("Starters", 99); // update value — position unchanged
        menuOrder.put("Soups", 5);     // new key — appended at end
        menuOrder.forEach((section, order) ->
            System.out.println("  " + order + ". " + section));

        System.out.println();

        // Contrast with HashMap — unpredictable iteration order
        Map<String, Integer> hashVersion = new java.util.HashMap<>(menuOrder);
        System.out.println("=== HashMap iteration (no order guarantee) ===");
        hashVersion.forEach((section, order) ->
            System.out.println("  " + order + ". " + section));

        System.out.println();

        // Deduplication preserving first-occurrence order
        String[] tags = {"java", "spring", "java", "hibernate", "spring", "kafka"};
        LinkedHashMap<String, Boolean> seen = new LinkedHashMap<>();
        for (String tag : tags) {
            seen.putIfAbsent(tag, Boolean.TRUE); // only inserts if absent — preserves first position
        }
        System.out.println("=== Unique tags (first-seen order) ===");
        System.out.println(seen.keySet()); // [java, spring, hibernate, kafka]
    }
}

Output:
=== Insertion-order iteration ===
  1. Starters
  2. Main Course
  3. Beverages
  4. Desserts

=== Re-insertion preserves position ===
  99. Starters
  2. Main Course
  3. Beverages
  4. Desserts
  5. Soups

=== HashMap iteration (no order guarantee) ===
  3. Beverages
  99. Starters
  5. Soups
  2. Main Course
  4. Desserts

=== Unique tags (first-seen order) ===
[java, spring, hibernate, kafka]

Access Order — LRU Cache Pattern

Java

// File: LRUCacheDemo.java

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

public class LRUCacheDemo {

    // Generic LRU cache built on LinkedHashMap with access-order mode
    static class LRUCache<K, V> extends LinkedHashMap<K, V> {

        private final int maxSize;

        LRUCache(int maxSize) {
            // true = access-order mode; every get/put moves entry to tail
            super(maxSize, 0.75f, true);
            this.maxSize = maxSize;
        }

        // Called after every put() — return true to evict the eldest (head) entry
        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            boolean shouldEvict = size() > maxSize;
            if (shouldEvict) {
                System.out.println("    EVICTED (LRU): " + eldest.getKey() + "=" + eldest.getValue());
            }
            return shouldEvict;
        }

        // Wrap get() to show access-order movement
        public V getAndLog(K key) {
            V value = get(key);
            System.out.println("    GET " + key + " → " + value
                + (value != null ? "  (moved to MRU end)" : " (cache miss)"));
            return value;
        }

        public void printState() {
            System.out.println("    Cache (LRU→MRU): " + keySet());
        }
    }

    public static void main(String[] args) {

        LRUCache<String, String> cache = new LRUCache<>(4);

        System.out.println("=== Loading cache (capacity 4) ===");
        cache.put("user:001", "Priya-session-A");   cache.printState();
        cache.put("user:002", "Rohan-session-B");   cache.printState();
        cache.put("user:003", "Ananya-session-C");  cache.printState();
        cache.put("user:004", "Karan-session-D");   cache.printState();

        System.out.println("\n=== Access operations (move to MRU tail) ===");
        cache.getAndLog("user:001"); cache.printState();
        cache.getAndLog("user:003"); cache.printState();
        cache.getAndLog("user:999"); cache.printState(); // cache miss

        System.out.println("\n=== New entries trigger LRU eviction ===");
        cache.put("user:005", "Divya-session-E");  // evicts user:002 (LRU head)
        cache.printState();

        cache.put("user:006", "Kavya-session-F");  // evicts user:004 (next LRU)
        cache.printState();

        System.out.println("\n=== Final cache state ===");
        cache.forEach((key, value) ->
            System.out.println("    " + key + " → " + value));
    }
}

Output:
=== Loading cache (capacity 4) ===
    Cache (LRU→MRU): [user:001]
    Cache (LRU→MRU): [user:001, user:002]
    Cache (LRU→MRU): [user:001, user:002, user:003]
    Cache (LRU→MRU): [user:001, user:002, user:003, user:004]

=== Access operations (move to MRU tail) ===
    GET user:001 → Priya-session-A  (moved to MRU end)
    Cache (LRU→MRU): [user:002, user:003, user:004, user:001]
    GET user:003 → Ananya-session-C  (moved to MRU end)
    Cache (LRU→MRU): [user:002, user:004, user:001, user:003]
    GET user:999 → null (cache miss)
    Cache (LRU→MRU): [user:002, user:004, user:001, user:003]

=== New entries trigger LRU eviction ===
    EVICTED (LRU): user:002=Rohan-session-B
    Cache (LRU→MRU): [user:004, user:001, user:003, user:005]
    EVICTED (LRU): user:004=Karan-session-D
    Cache (LRU→MRU): [user:001, user:003, user:005, user:006]

=== Final cache state ===
    user:001 → Priya-session-A
    user:003 → Ananya-session-C
    user:005 → Divya-session-E
    user:006 → Kavya-session-F

Iterating and Streaming LinkedHashMap

Java

// File: LinkedHashMapIterationDemo.java

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.stream.Collectors;

public class LinkedHashMapIterationDemo {

    public static void main(String[] args) {

        LinkedHashMap<String, Double> salesByRegion = new LinkedHashMap<>();
        salesByRegion.put("North",  45_200.0);
        salesByRegion.put("South",  38_900.0);
        salesByRegion.put("East",   52_100.0);
        salesByRegion.put("West",   41_750.0);
        salesByRegion.put("Central",29_600.0);

        // entrySet() iteration — preserves insertion order
        System.out.println("=== entrySet() — insertion order preserved ===");
        salesByRegion.entrySet().forEach(e ->
            System.out.printf("  %-10s Rs.%7.2f%n", e.getKey(), e.getValue()));

        // Safe removal during iteration — iterator.remove()
        System.out.println("\n=== Remove regions below Rs.35,000 ===");
        salesByRegion.entrySet().removeIf(e -> e.getValue() < 35_000);
        salesByRegion.forEach((region, sales) ->
            System.out.printf("  %-10s Rs.%7.2f%n", region, sales));

        // Collecting to LinkedHashMap preserves stream encounter order
        System.out.println("\n=== Stream: top 2 regions by sales ===");
        LinkedHashMap<String, Double> top2 = salesByRegion.entrySet().stream()
            .sorted(Map.Entry.<String, Double>comparingByValue().reversed())
            .limit(2)
            .collect(Collectors.toMap(
                Map.Entry::getKey,
                Map.Entry::getValue,
                (a, b) -> a,
                LinkedHashMap::new   // use LinkedHashMap to preserve sorted order
            ));
        top2.forEach((region, sales) ->
            System.out.printf("  %-10s Rs.%7.2f%n", region, sales));
    }
}

Output:
=== entrySet() — insertion order preserved ===
  North      Rs. 45200.00
  South      Rs. 38900.00
  East       Rs. 52100.00
  West       Rs. 41750.00
  Central    Rs. 29600.00

=== Remove regions below Rs.35,000 ===
  North      Rs. 45200.00
  South      Rs. 38900.00
  East       Rs. 52100.00
  West       Rs. 41750.00

=== Stream: top 2 regions by sales ===
  East       Rs. 52100.00
  North      Rs. 45200.00

Real-World Example — Swiggy Configuration Service

A configuration service at Swiggy loads feature flags from the database at startup and serves them to the application layer. The flags must be served in the order they were loaded — priority flags first, experimental flags last. The configuration store also acts as a bounded cache: when the config table grows beyond a set limit, the oldest-loaded entry is evicted automatically.

Java

// File: FeatureFlag.java

public record FeatureFlag(
        String key,
        String value,
        boolean enabled,
        String environment) {

    @Override
    public String toString() {
        return String.format("%-25s = %-8s  [%s]  env=%s",
            key, value, enabled ? "ON " : "OFF", environment);
    }
}

Java

// File: ConfigurationStore.java

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

public class ConfigurationStore {

    private static final int MAX_FLAGS = 8;

    // Insertion-order LinkedHashMap with bounded capacity
    // Anonymous subclass overrides removeEldestEntry for auto-eviction
    private final Map<String, FeatureFlag> store = Collections.synchronizedMap(
        new LinkedHashMap<>(MAX_FLAGS + 1, 0.75f, false) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<String, FeatureFlag> eldest) {
                boolean evict = size() > MAX_FLAGS;
                if (evict) {
                    System.out.println("  AUTO-EVICTED: " + eldest.getKey());
                }
                return evict;
            }
        }
    );

    public void load(FeatureFlag flag) {
        store.put(flag.key(), flag);
        System.out.println("  LOADED: " + flag);
    }

    public FeatureFlag get(String key) {
        return store.get(key);
    }

    public boolean isEnabled(String key) {
        FeatureFlag flag = store.get(key);
        return flag != null && flag.enabled();
    }

    // Returns flags in load order — first loaded = first returned
    public void printAll() {
        System.out.println("=".repeat(70));
        System.out.println("  ACTIVE CONFIGURATION FLAGS  (" + store.size() + "/" + MAX_FLAGS + ")");
        System.out.println("=".repeat(70));
        store.values().forEach(flag -> System.out.println("  " + flag));
        System.out.println("=".repeat(70));
    }

    public static void main(String[] args) {

        ConfigurationStore config = new ConfigurationStore();

        System.out.println("--- Loading feature flags ---");
        config.load(new FeatureFlag("dark_mode_enabled",    "true",  true,  "prod"));
        config.load(new FeatureFlag("new_checkout_flow",    "false", false, "prod"));
        config.load(new FeatureFlag("ai_recommendations",   "true",  true,  "prod"));
        config.load(new FeatureFlag("express_delivery",     "true",  true,  "prod"));
        config.load(new FeatureFlag("subscription_plans",   "false", false, "beta"));
        config.load(new FeatureFlag("loyalty_points",       "true",  true,  "prod"));
        config.load(new FeatureFlag("dynamic_pricing",      "true",  false, "beta"));
        config.load(new FeatureFlag("partner_discounts",    "true",  true,  "prod"));

        System.out.println();
        config.printAll();

        System.out.println("\n--- Loading more flags — oldest evicted at capacity ---");
        config.load(new FeatureFlag("review_highlights",    "false", true,  "beta"));
        config.load(new FeatureFlag("gamification_enabled", "true",  false, "beta"));

        System.out.println();
        config.printAll();

        System.out.println("\n--- Feature flag queries ---");
        System.out.println("dark_mode_enabled  : " + config.isEnabled("dark_mode_enabled"));
        System.out.println("new_checkout_flow  : " + config.isEnabled("new_checkout_flow"));
        System.out.println("dark_mode_enabled get: " + config.get("dark_mode_enabled"));
    }
}

Output:
--- Loading feature flags ---
  LOADED: dark_mode_enabled           = true      [ON ]  env=prod
  LOADED: new_checkout_flow           = false     [OFF]  env=prod
  LOADED: ai_recommendations          = true      [ON ]  env=prod
  LOADED: express_delivery            = true      [ON ]  env=prod
  LOADED: subscription_plans          = false     [OFF]  env=beta
  LOADED: loyalty_points              = true      [ON ]  env=prod
  LOADED: dynamic_pricing             = true      [OFF]  env=beta
  LOADED: partner_discounts           = true      [ON ]  env=prod

======================================================================
  ACTIVE CONFIGURATION FLAGS  (8/8)
======================================================================
  dark_mode_enabled           = true      [ON ]  env=prod
  new_checkout_flow           = false     [OFF]  env=prod
  ai_recommendations          = true      [ON ]  env=prod
  express_delivery            = true      [ON ]  env=prod
  subscription_plans          = false     [OFF]  env=beta
  loyalty_points              = true      [ON ]  env=prod
  dynamic_pricing             = true      [OFF]  env=beta
  partner_discounts           = true      [ON ]  env=prod
======================================================================

--- Loading more flags — oldest evicted at capacity ---
  AUTO-EVICTED: dark_mode_enabled
  LOADED: review_highlights           = false     [ON ]  env=beta
  AUTO-EVICTED: new_checkout_flow
  LOADED: gamification_enabled        = true      [OFF]  env=beta

======================================================================
  ACTIVE CONFIGURATION FLAGS  (8/8)
======================================================================
  ai_recommendations          = true      [ON ]  env=prod
  express_delivery            = true      [ON ]  env=prod
  subscription_plans          = false     [OFF]  env=beta
  loyalty_points              = true      [ON ]  env=prod
  dynamic_pricing             = true      [OFF]  env=beta
  partner_discounts           = true      [ON ]  env=prod
  review_highlights           = false     [ON ]  env=beta
  gamification_enabled        = true      [OFF]  env=beta
======================================================================

--- Feature flag queries ---
dark_mode_enabled  : false
new_checkout_flow  : false
dark_mode_enabled get: null

Performance Considerations

Operation	HashMap	LinkedHashMap	TreeMap
put(k, v)	O(1) avg	O(1) avg	O(log n)
get(k)	O(1) avg	O(1) avg	O(log n)
remove(k)	O(1) avg	O(1) avg	O(log n)
Iteration	O(n + capacity)	O(n)	O(n)
Memory/entry	~48 bytes	~64 bytes (+before/after)	~56 bytes (tree node)
Ordering	None	Insertion or Access	Sorted by key

Iteration performance: HashMap iterates O(n + capacity) because it scans all bucket slots including empty ones. LinkedHashMap iterates in O(n) by following the doubly-linked list — only live entries are touched. For a sparse map (low load factor, large capacity), LinkedHashMap iteration is significantly faster.

Memory cost: Each LinkedHashMap entry carries two extra references — before and after — compared to HashMap. On a 64-bit JVM with compressed references, this is approximately 8 extra bytes per entry. For maps holding millions of entries, this overhead accumulates; for typical application maps in the thousands, it is negligible.

LRU cache performance: In access-order mode, every get() triggers an afterNodeAccess() call — an O(1) pointer rearrangement. The cost is constant regardless of map size. removeEldestEntry() is also O(1) — it checks and removes the head entry. The full LRU put()/get() cycle is O(1) amortised.

Thread safety: LinkedHashMap is not thread-safe. The real-world example wraps it in Collections.synchronizedMap(), which synchronises individual method calls. Iteration must be performed inside a synchronized block. For high-concurrency LRU caches, consider ConcurrentHashMap with computeIfAbsent and a separate eviction mechanism, or a dedicated library like Caffeine.

Best Practices

Declare the variable as Map<K, V> unless LRU-specific behaviour is needed. Map<String, FeatureFlag> config = new LinkedHashMap<>() exposes only the Map interface to callers. LinkedHashMap<String, FeatureFlag> config = new LinkedHashMap<>() couples callers to the implementation. The exception: removeEldestEntry() requires subclassing LinkedHashMap directly — the LRU cache pattern genuinely needs the concrete type.

Wrap in Collections.synchronizedMap() when shared across threads. Collections.synchronizedMap(new LinkedHashMap<>()) synchronises individual operations. This is sufficient for most shared-cache scenarios where operations are atomic. For iteration, you must manually synchronise: synchronized(map) { for (Entry<K,V> e : map.entrySet()) {...} } — failing to do so allows another thread to modify the map during iteration and trigger ConcurrentModificationException.

Use access-order mode only when the LRU eviction pattern is the explicit intent. Access-order mode has a side effect: get() modifies the map structure by moving the accessed entry. This means get() is not a purely read-only operation — it updates the linked-list pointers. Code that iterates and calls get() simultaneously produces ConcurrentModificationException in a single thread. In access-order maps, only use getOrDefault() for reads that must not alter order.

Pre-size the map when the maximum capacity is known. For an LRU cache of capacity N, construct with new LinkedHashMap<>(N + 1, 0.75f, true) — the N + 1 pre-allocation avoids a resize when the map reaches exactly N entries and the next put() would trigger both insertion and removeEldestEntry(). Without pre-sizing, a resize can fire before eviction is given a chance to run.

Common Mistakes

Mistake 1 — Expecting Re-insertion to Move an Entry to the End (Insertion Mode)

Java

// WRONG assumption: putting the same key again moves it to the end
LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
map.put("A", 1); map.put("B", 2); map.put("C", 3);
map.put("A", 99); // updates value — position stays at head

System.out.println(map.keySet()); // [A, B, C] — A is still first

// In INSERTION-ORDER mode, position is fixed at first insertion.
// To move an entry, remove it and re-add:
map.remove("A");
map.put("A", 99); // now at end
System.out.println(map.keySet()); // [B, C, A]

Output:
[A, B, C]
[B, C, A]

Mistake 2 — Calling get() During Iteration in Access-Order Mode

Java

LinkedHashMap<String, String> accessMap =
    new LinkedHashMap<>(16, 0.75f, true); // access-order
accessMap.put("X", "val-X");
accessMap.put("Y", "val-Y");
accessMap.put("Z", "val-Z");

// WRONG — get() in access-order mode modifies the linked list during iteration
try {
    for (Map.Entry<String, String> entry : accessMap.entrySet()) {
        accessMap.get("Z"); // moves Z to tail — structural change → CME
    }
} catch (java.util.ConcurrentModificationException e) {
    System.out.println("CME thrown — get() in access-order mode modified the map");
}

// CORRECT — use entrySet() iteration and avoid get() inside the loop
for (Map.Entry<String, String> entry : accessMap.entrySet()) {
    String value = entry.getValue(); // no structural change
}

Output:
CME thrown — get() in access-order mode modified the map

Mistake 3 — Using LinkedHashMap When HashMap Iteration Behaviour Is Acceptable

Java

// WRONG — using LinkedHashMap when insertion order is never actually used
// This pays the linked-list maintenance cost for no benefit
Map<String, Integer> wordCount = new LinkedHashMap<>();
// ...counting words — order never displayed, never used in any logic

// CORRECT — HashMap if iteration order truly does not matter
Map<String, Integer> wordCount2 = new HashMap<>();
// Slightly faster put/get, less memory per entry

Mistake 4 — Forgetting to Synchronise Iteration on a Shared LinkedHashMap

Java

Map<String, String> sharedConfig = Collections.synchronizedMap(new LinkedHashMap<>());
sharedConfig.put("key1", "value1");

// WRONG — iteration is NOT thread-safe even with synchronizedMap
// Another thread can modify the map between individual iterator.hasNext() calls
for (Map.Entry<String, String> entry : sharedConfig.entrySet()) {
    // potential ConcurrentModificationException from another thread
}

// CORRECT — synchronise the entire iteration block
synchronized (sharedConfig) {
    for (Map.Entry<String, String> entry : sharedConfig.entrySet()) {
        process(entry.getKey(), entry.getValue());
    }
}

Interview Questions

Q1. What is LinkedHashMap in Java and how does it differ from HashMap?

LinkedHashMap extends HashMap and adds a doubly-linked list that threads all entries in insertion order. Every HashMap operation works identically — O(1) average put(), get(), and remove() via the same hash table. The difference is iteration: HashMap iterates in unpredictable bucket-scan order; LinkedHashMap always iterates in the order entries were inserted. Each LinkedHashMap entry carries two extra references (before and after) for the linked list — approximately 8 extra bytes per entry on a modern JVM.

Q2. What are the two ordering modes of LinkedHashMap?

Insertion-order mode (the default, new LinkedHashMap<>()) iterates entries in the sequence put() was first called. Re-inserting an existing key updates its value but does not move its position. Access-order mode (new LinkedHashMap<>(capacity, 0.75f, true)) moves an entry to the tail on every get() or existing-key put() — the head always holds the Least Recently Used entry. Access-order mode is specifically designed for LRU cache construction in combination with removeEldestEntry().

Q3. How do you implement an LRU cache using LinkedHashMap?

Extend LinkedHashMap with access-order enabled and override removeEldestEntry(). The constructor super(maxSize, 0.75f, true) enables access-order. Override protected boolean removeEldestEntry(Map.Entry<K,V> eldest) to return size() > maxSize — this triggers automatic eviction of the head entry (LRU candidate) after every put() that exceeds capacity. Both get() and put() on existing keys move the accessed entry to the tail, maintaining the LRU order. The entire implementation is O(1) per operation because all linked-list operations are pointer updates.

Q4. Why does LinkedHashMap iteration run faster than HashMap iteration on sparse maps?

HashMap iteration scans the entire table[] array from index 0 to capacity - 1, including null slots for empty buckets. For a HashMap with capacity 16,384 but only 10 entries, iteration examines 16,394 array positions. LinkedHashMap iteration follows the doubly-linked list from head to tail — it touches only the n live entries regardless of capacity. For sparse maps, this difference is proportional to capacity / n.

Q5. Is LinkedHashMap thread-safe? How do you make it thread-safe?

LinkedHashMap is not thread-safe. Two threads calling put() or get() simultaneously can corrupt the doubly-linked list pointers or trigger ConcurrentModificationException during iteration. The standard fix for simple concurrent scenarios is Collections.synchronizedMap(new LinkedHashMap<>()), which synchronises individual operations. Iteration still requires an external synchronized block. For high-concurrency LRU caches, LinkedHashMap is usually replaced with a dedicated library like Caffeine (Cache.builder().maximumSize(N).build()), which is lock-free and offers higher throughput.

Q6. What does removeEldestEntry() do and when is it called?

removeEldestEntry(Map.Entry<K,V> eldest) is a protected method in LinkedHashMap called by afterNodeInsertion() after every put() that adds a new entry. The eldest parameter is the current head of the linked list — the oldest (insertion-order) or least-recently-accessed (access-order) entry. If the method returns true, LinkedHashMap immediately removes that entry from both the hash table and the linked list. The default implementation always returns false (no auto-removal). Override it to build a bounded map: return size() > MAX_ENTRIES.

FAQs

Does LinkedHashMap allow null keys and values?

Yes. LinkedHashMap inherits null-key support from HashMap — exactly one null key is allowed, placed in bucket 0. Any number of null values are allowed. This behaviour is the same as HashMap and contrasts with TreeMap (null key throws NullPointerException on compareTo) and Hashtable (neither null key nor null value allowed).

What is the difference between LinkedHashMap and LinkedHashSet?

LinkedHashSet is backed by a LinkedHashMap where elements become keys and a shared dummy PRESENT object becomes the value. Everything you know about LinkedHashMap's insertion-order iteration applies to LinkedHashSet. The relationship is: LinkedHashSet = HashSet + insertion order, exactly as LinkedHashMap = HashMap + insertion order.

How do you copy a HashMap into a LinkedHashMap while preserving insertion order?

new LinkedHashMap<>(sourceHashMap) creates a LinkedHashMap with all entries from the source map. Since HashMap has no defined order, the resulting LinkedHashMap will iterate in whatever order HashMap.entrySet() produces during the copy — which is hash-bucket order, not the original insertion order. If you need original insertion order, you must use a LinkedHashMap from the start.

Can LinkedHashMap be used as a cache without access-order mode?

Yes, but with FIFO eviction rather than LRU. In insertion-order mode, the head always holds the first-inserted entry. Overriding removeEldestEntry() to return size() > MAX evicts the oldest-inserted entry — First-In, First-Out semantics. This is simpler than LRU and appropriate when recency of access is irrelevant — for example, a config cache that loads once at startup and evicts the oldest entries when the config table grows.

What is the iteration order guarantee of LinkedHashMap after remove?

When an entry is removed, it is unlinked from the doubly-linked list in O(1) — its before.after = entry.after and after.before = entry.before. The remaining entries continue to iterate in their original insertion-order sequence with no gaps or shifts. Unlike ArrayList, which shifts elements on removal, LinkedHashMap removal has no effect on the relative order of other entries.

How does LinkedHashMap handle the iteration cost differently from HashMap?

HashMap iterates O(n + capacity) by scanning every slot in the bucket array including nulls. LinkedHashMap iterates O(n) by following the doubly-linked before/after pointers — only live entries are visited. For a HashMap with capacity 16,384 holding 10 entries, iteration visits 16,394 slots. LinkedHashMap with the same 10 entries visits exactly 10 nodes. The linked list makes LinkedHashMap strictly faster to iterate on sparse maps.

Summary

LinkedHashMap<K, V> extends HashMap with a doubly-linked list that threads all entries in a defined order — insertion order by default, access order when the third constructor argument is true. Every hash table operation remains O(1) average. Iteration runs in O(n) by following the linked list rather than scanning all bucket slots.

The two production patterns that make LinkedHashMap uniquely useful: ordered-output maps where insertion sequence must be preserved through serialisation or API responses, and LRU caches built by subclassing with removeEldestEntry() in access-order mode. Both patterns are clean, low-ceremony, and avoid external dependencies.

For interviews: explain the two ordering modes and when each is appropriate, describe removeEldestEntry() and the LRU pattern in access-order mode, clarify that re-insertion in insertion-order mode does not move an entry, and explain why get() causes ConcurrentModificationException during iteration in access-order mode. These questions consistently distinguish candidates who understand the internals from those who only know the class name.

What to Read Next

Topic	Link
How HashMap provides the hash table foundation that LinkedHashMap extends	Java HashMap →
How TreeMap provides sorted key ordering as an alternative ordering strategy	Java TreeMap →
How HashSet and LinkedHashSet relate to HashMap and LinkedHashMap respectively	Java HashSet →
How the Iterator interface enables safe traversal and removal on LinkedHashMap entries	Java Iterator →
How Java Streams process LinkedHashMap entries while preserving insertion order	Java Streams API →