Java Notes

LinkedHashMap in Java

Complete guide to Java LinkedHashMap — insertion-order and access-order maintenance, internal doubly-linked list, LRU cache implementation, comparison with HashMap and TreeMap.

What is LinkedHashMap?

java.util.LinkedHashMap is a HashMap with predictable iteration order. It maintains a doubly-linked list running through all entries, preserving either:

Insertion order (default) — entries iterate in the order they were added
Access order — entries iterate from least-recently-accessed to most-recently-accessed (useful for LRU caches)

java example

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

Constructors

java example

// Default: insertion order, capacity 16, load factor 0.75
LinkedHashMap<String, Integer> map1 = new LinkedHashMap<>();

// Custom capacity and load factor (still insertion order)
LinkedHashMap<String, Integer> map2 = new LinkedHashMap<>(32, 0.8f);

// ACCESS ORDER — third parameter = true
LinkedHashMap<String, Integer> map3 = new LinkedHashMap<>(16, 0.75f, true);

Insertion Order (Default)

java example

import java.util.*;

public class InsertionOrderDemo {
    public static void main(String[] args) {
        Map<String, Integer> map = new LinkedHashMap<>();
        map.put("Banana", 2);
        map.put("Apple", 5);
        map.put("Cherry", 3);
        map.put("Date", 1);
        map.put("Elderberry", 4);

        // Iteration preserves insertion order!
        System.out.println("Insertion order:");
        map.forEach((k, v) -> System.out.println("  " + k + " = " + v));

        // Updating a value does NOT change position
        map.put("Apple", 10);

        System.out.println("\nAfter updating Apple:");
        map.forEach((k, v) -> System.out.println("  " + k + " = " + v));
        // Apple is still in position 2 (not moved to end)
    }
}

Output:

Insertion order

Banana = 2

Apple = 5

Cherry = 3

Date = 1

Elderberry = 4

After updating Apple

Banana = 2

Apple = 10

Cherry = 3

Date = 1

Elderberry = 4

Access Order Mode

Example

import java.util.*; public class AccessOrderDemo { public static void main(String[] args) { // Third parameter = true → access order LinkedHashMap<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true); map.put("A", 1); map.put("B", 2); map.put("C", 3); map.put("D", 4); map.put("E", 5); System.out.println("Initial order: " + map.keySet()); // [A, B, C, D, E] // Access some entries — they move to the end map.get("B"); // B moves to tail map.get("A"); // A moves to tail System.out.println("After accessing B, A: " + map.keySet()); // [C, D, E, B, A] — B and A moved to end (most recently accessed) // put() also counts as access map.put("C", 30); // Updates C — moves to tail System.out.println("After updating C: " + map.keySet()); // [D, E, B, A, C] } }

Output

{A=1, B=2, C=3}
After get(A): {B=2, C=3, A=1}
After put(B,22): {C=3, A=1, B=22}

LRU Cache Implementation

The most famous use of LinkedHashMap — a Least Recently Used cache:

Example

import java.util.*; public class LRUCache<K, V> extends LinkedHashMap<K, V> { private final int maxSize; public LRUCache(int maxSize) { super(maxSize, 0.75f, true); // access-order = true this.maxSize = maxSize; } @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > maxSize; // Remove oldest when over capacity } public static void main(String[] args) { LRUCache<String, String> cache = new LRUCache<>(3); cache.put("page1", "Content 1"); cache.put("page2", "Content 2"); cache.put("page3", "Content 3"); System.out.println("Cache: " + cache.keySet()); // [page1, page2, page3] cache.get("page1"); // Access page1 — moves to most recent System.out.println("After accessing page1: " + cache.keySet()); // [page2, page3, page1] cache.put("page4", "Content 4"); // Exceeds capacity → evicts page2 (eldest) System.out.println("After adding page4: " + cache.keySet()); // [page3, page1, page4] cache.put("page5", "Content 5"); // Evicts page3 System.out.println("After adding page5: " + cache.keySet()); // [page1, page4, page5] } }

Output

Cache: [page1, page2, page3]
After accessing page1: [page2, page3, page1]
After adding page4 (capacity=3): [page3, page1, page4]
page2 was evicted (least recently used)

The removeEldestEntry() Hook

java example

// Called by put() AFTER inserting the new entry
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;  // Default: never remove (map grows forever)
}

// Override to implement auto-eviction:
// - LRU cache: return size() > maxCapacity;
// - Time-based: return eldest.getValue().isExpired();
// - Memory-based: return Runtime.getRuntime().freeMemory() < threshold;

Time Complexity

Operation	Time Complexity	Notes
-----------	:-:	---
`put(key, value)`	O(1)	Same as HashMap + O(1) list maintenance
`get(key)`	O(1)	Same as HashMap + O(1) reorder (access mode)
`remove(key)`	O(1)	Same as HashMap + O(1) unlink
`containsKey(key)`	O(1)	Inherited from HashMap
`containsValue(value)`	O(n)	Must iterate linked list
Iteration	O(n)	Only n entries (not capacity!)

Iteration Performance: LinkedHashMap vs HashMap

Map Type	Iteration Time
----------	:-:
HashMap	O(capacity + n) — iterates all buckets, even empty ones
LinkedHashMap	O(n) — follows the linked list, skips empty buckets

This is a significant advantage when the map is sparse (few entries, large capacity).

LinkedHashMap vs HashMap vs TreeMap

Feature	HashMap	LinkedHashMap	TreeMap
Ordering	None	Insertion or access order	Sorted by key
get/put performance	O(1)	O(1)	O(log n)
Iteration performance	O(capacity)	O(n)	O(n)
Memory overhead	Lowest	Medium (+before/after pointers)	Highest (tree nodes)
Null keys	One	One	None
Use case	General purpose	Order matters, LRU cache	Sorted navigation

Practical Use Cases

1. Maintaining Configuration Order

java example

// Config entries stay in order they were defined
Map<String, String> config = new LinkedHashMap<>();
config.put("host", "localhost");
config.put("port", "8080");
config.put("protocol", "https");
// Iterating always gives: host → port → protocol

2. Building Ordered JSON-like Structures

java example

Map<String, Object> json = new LinkedHashMap<>();
json.put("name", "Alice");
json.put("age", 30);
json.put("email", "alice@example.com");
// Serializes in predictable order

3. Deduplication with Order Preservation

Example

List<String> withDupes = Arrays.asList("B", "A", "C", "A", "B", "D"); List<String> unique = new ArrayList<>(new LinkedHashSet<>(withDupes)); // [B, A, C, D] — order preserved, duplicates removed

4. Bounded Size Map (Most Recent N Entries)

java example

// Keep only the last 100 entries
Map<String, String> recentLogs = new LinkedHashMap<>(128, 0.75f, false) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
        return size() > 100;
    }
};

Thread Safety

LinkedHashMap is NOT thread-safe:

java example

// Option 1: Synchronized wrapper
Map<String, Integer> syncMap = Collections.synchronizedMap(new LinkedHashMap<>());

// Option 2: For concurrent LRU, use external locking
// There is NO ConcurrentLinkedHashMap in the JDK — use Caffeine or Guava's Cache

Common Mistakes

1. ConcurrentModificationException in Access-Order Mode

java example

// DANGEROUS — iterating access-order LinkedHashMap with get() inside loop
LinkedHashMap<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true);
map.put("A", 1); map.put("B", 2); map.put("C", 3);

// This throws ConcurrentModificationException!
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    map.get(entry.getKey());  // Structurally modifies the linked list!
}

2. Forgetting Access Order Changes Structure

java example

// In access-order mode, even get() modifies the iteration order
// This can surprise code that assumes iteration is stable

3. Not Understanding removeEldestEntry Timing

java example

// removeEldestEntry is called AFTER the new entry is added
// So size() already includes the new entry when this method runs
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return size() > maxSize;  // Correct — checks after addition
}

Interview Questions

Q1: How does LinkedHashMap maintain insertion order?

A: It extends HashMap and adds a doubly-linked list (before/after pointers) threading through all entries. New entries are appended to the tail of this list.

Q2: What is access-order mode and when would you use it?

A: When constructed with accessOrder=true, entries are reordered on every get() or put(). The least-recently-accessed entry is at the head. Used for LRU cache implementations.

Q3: How would you implement an LRU cache using LinkedHashMap?

A: Extend LinkedHashMap with accessOrder=true and override removeEldestEntry() to return true when size() > maxCapacity.

Q4: What is the time complexity of iteration for LinkedHashMap vs HashMap?

A: LinkedHashMap iterates in O(n) — follows the linked list. HashMap iterates in O(capacity + n) — must check every bucket including empty ones.

Q5: Does LinkedHashMap allow null keys?

A: Yes, exactly one null key (inherited from HashMap). The null key's position in iteration order follows the same insertion/access rules.

Q6: What happens when you call get() during iteration in access-order mode?

A: It throws ConcurrentModificationException because get() structurally modifies the linked list order.

Q8: How do you implement LRU Cache using LinkedHashMap?

A: Create a LinkedHashMap with access-order enabled (new LinkedHashMap<>(capacity, 0.75f, true)) and override removeEldestEntry() to return true when size() > maxCapacity. This automatically evicts the least recently used entry when the cache is full.

Q9: What is the difference between insertion-order and access-order mode?

A: Insertion-order (default): entries maintain the order they were first inserted. Access-order (constructor flag true): entries are moved to the end whenever accessed via get() or put(). Access-order is essential for LRU cache implementation.

Q10: Does LinkedHashMap have any performance overhead compared to HashMap?

A: Minimal. LinkedHashMap maintains a doubly-linked list threading through all entries for ordering. This adds ~16 bytes per entry (two extra pointers). put/get/remove operations remain O(1) but with slightly higher constant factor due to linked list maintenance.

Q11: Is LinkedHashMap thread-safe?

A: No, like HashMap. For thread-safe ordered maps, use Collections.synchronizedMap(new LinkedHashMap<>()) or ConcurrentHashMap (which doesn't preserve insertion order). There's no concurrent LinkedHashMap in the standard library.

Q12: How does iteration performance of LinkedHashMap compare to HashMap?

A: LinkedHashMap iterates in O(n) where n is the number of entries. HashMap iterates in O(capacity + n) because it must scan all buckets (including empty ones). For maps with high capacity but few entries, LinkedHashMap's iteration is significantly faster.

Summary

Aspect	LinkedHashMap
Extends	HashMap
Ordering	Insertion order (default) or access order
Performance	Same as HashMap — O(1) for get/put
Extra memory	~16 bytes per entry (before/after pointers)
Best for	Predictable iteration, LRU caches, ordered JSON
Thread-safe	No
Null keys	One allowed
Key feature	`removeEldestEntry()` hook for bounded maps

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for LinkedHashMap in Java.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Java Master Course topic.

Search Terms

java-master-course, java master course, java, master, course, collections, framework, map

Continue learning this concept

PreviousHashtable in Java NextTreeMap in Java

Java Notes

LinkedHashMap in Java

Complete guide to Java LinkedHashMap — insertion-order and access-order maintenance, internal doubly-linked list, LRU cache implementation, comparison with HashMap and TreeMap.

What is LinkedHashMap?

java.util.LinkedHashMap is a HashMap with predictable iteration order. It maintains a doubly-linked list running through all entries, preserving either:

Insertion order (default) — entries iterate in the order they were added
Access order — entries iterate from least-recently-accessed to most-recently-accessed (useful for LRU caches)

java example

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

Constructors

java example

// Default: insertion order, capacity 16, load factor 0.75
LinkedHashMap<String, Integer> map1 = new LinkedHashMap<>();

// Custom capacity and load factor (still insertion order)
LinkedHashMap<String, Integer> map2 = new LinkedHashMap<>(32, 0.8f);

// ACCESS ORDER — third parameter = true
LinkedHashMap<String, Integer> map3 = new LinkedHashMap<>(16, 0.75f, true);

Insertion Order (Default)

java example

import java.util.*;

public class InsertionOrderDemo {
    public static void main(String[] args) {
        Map<String, Integer> map = new LinkedHashMap<>();
        map.put("Banana", 2);
        map.put("Apple", 5);
        map.put("Cherry", 3);
        map.put("Date", 1);
        map.put("Elderberry", 4);

        // Iteration preserves insertion order!
        System.out.println("Insertion order:");
        map.forEach((k, v) -> System.out.println("  " + k + " = " + v));

        // Updating a value does NOT change position
        map.put("Apple", 10);

        System.out.println("\nAfter updating Apple:");
        map.forEach((k, v) -> System.out.println("  " + k + " = " + v));
        // Apple is still in position 2 (not moved to end)
    }
}

Output:

Insertion order

Banana = 2

Apple = 5

Cherry = 3

Date = 1

Elderberry = 4

After updating Apple

Banana = 2

Apple = 10

Cherry = 3

Date = 1

Elderberry = 4

Access Order Mode

Example

Output

{A=1, B=2, C=3}
After get(A): {B=2, C=3, A=1}
After put(B,22): {C=3, A=1, B=22}

LRU Cache Implementation

The most famous use of LinkedHashMap — a Least Recently Used cache:

Example

Output

Cache: [page1, page2, page3]
After accessing page1: [page2, page3, page1]
After adding page4 (capacity=3): [page3, page1, page4]
page2 was evicted (least recently used)

The removeEldestEntry() Hook

java example

// Called by put() AFTER inserting the new entry
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;  // Default: never remove (map grows forever)
}

// Override to implement auto-eviction:
// - LRU cache: return size() > maxCapacity;
// - Time-based: return eldest.getValue().isExpired();
// - Memory-based: return Runtime.getRuntime().freeMemory() < threshold;

Time Complexity

Operation	Time Complexity	Notes
-----------	:-:	---
`put(key, value)`	O(1)	Same as HashMap + O(1) list maintenance
`get(key)`	O(1)	Same as HashMap + O(1) reorder (access mode)
`remove(key)`	O(1)	Same as HashMap + O(1) unlink
`containsKey(key)`	O(1)	Inherited from HashMap
`containsValue(value)`	O(n)	Must iterate linked list
Iteration	O(n)	Only n entries (not capacity!)

Iteration Performance: LinkedHashMap vs HashMap

Map Type	Iteration Time
----------	:-:
HashMap	O(capacity + n) — iterates all buckets, even empty ones
LinkedHashMap	O(n) — follows the linked list, skips empty buckets

This is a significant advantage when the map is sparse (few entries, large capacity).

LinkedHashMap vs HashMap vs TreeMap

Feature	HashMap	LinkedHashMap	TreeMap
Ordering	None	Insertion or access order	Sorted by key
get/put performance	O(1)	O(1)	O(log n)
Iteration performance	O(capacity)	O(n)	O(n)
Memory overhead	Lowest	Medium (+before/after pointers)	Highest (tree nodes)
Null keys	One	One	None
Use case	General purpose	Order matters, LRU cache	Sorted navigation

Practical Use Cases

1. Maintaining Configuration Order

java example

// Config entries stay in order they were defined
Map<String, String> config = new LinkedHashMap<>();
config.put("host", "localhost");
config.put("port", "8080");
config.put("protocol", "https");
// Iterating always gives: host → port → protocol

2. Building Ordered JSON-like Structures

java example

Map<String, Object> json = new LinkedHashMap<>();
json.put("name", "Alice");
json.put("age", 30);
json.put("email", "alice@example.com");
// Serializes in predictable order

3. Deduplication with Order Preservation

Example

List<String> withDupes = Arrays.asList("B", "A", "C", "A", "B", "D"); List<String> unique = new ArrayList<>(new LinkedHashSet<>(withDupes)); // [B, A, C, D] — order preserved, duplicates removed

4. Bounded Size Map (Most Recent N Entries)

java example

// Keep only the last 100 entries
Map<String, String> recentLogs = new LinkedHashMap<>(128, 0.75f, false) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
        return size() > 100;
    }
};

Thread Safety

LinkedHashMap is NOT thread-safe:

java example

// Option 1: Synchronized wrapper
Map<String, Integer> syncMap = Collections.synchronizedMap(new LinkedHashMap<>());

// Option 2: For concurrent LRU, use external locking
// There is NO ConcurrentLinkedHashMap in the JDK — use Caffeine or Guava's Cache

Common Mistakes

1. ConcurrentModificationException in Access-Order Mode

java example

// DANGEROUS — iterating access-order LinkedHashMap with get() inside loop
LinkedHashMap<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true);
map.put("A", 1); map.put("B", 2); map.put("C", 3);

// This throws ConcurrentModificationException!
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    map.get(entry.getKey());  // Structurally modifies the linked list!
}

2. Forgetting Access Order Changes Structure

java example

// In access-order mode, even get() modifies the iteration order
// This can surprise code that assumes iteration is stable

3. Not Understanding removeEldestEntry Timing

java example

// removeEldestEntry is called AFTER the new entry is added
// So size() already includes the new entry when this method runs
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return size() > maxSize;  // Correct — checks after addition
}

Interview Questions

Q1: How does LinkedHashMap maintain insertion order?

A: It extends HashMap and adds a doubly-linked list (before/after pointers) threading through all entries. New entries are appended to the tail of this list.

Q2: What is access-order mode and when would you use it?

A: When constructed with accessOrder=true, entries are reordered on every get() or put(). The least-recently-accessed entry is at the head. Used for LRU cache implementations.

Q3: How would you implement an LRU cache using LinkedHashMap?

A: Extend LinkedHashMap with accessOrder=true and override removeEldestEntry() to return true when size() > maxCapacity.

Q4: What is the time complexity of iteration for LinkedHashMap vs HashMap?

A: LinkedHashMap iterates in O(n) — follows the linked list. HashMap iterates in O(capacity + n) — must check every bucket including empty ones.

Q5: Does LinkedHashMap allow null keys?

A: Yes, exactly one null key (inherited from HashMap). The null key's position in iteration order follows the same insertion/access rules.

Q6: What happens when you call get() during iteration in access-order mode?

A: It throws ConcurrentModificationException because get() structurally modifies the linked list order.

Q8: How do you implement LRU Cache using LinkedHashMap?

Q9: What is the difference between insertion-order and access-order mode?

Q10: Does LinkedHashMap have any performance overhead compared to HashMap?

Q11: Is LinkedHashMap thread-safe?

Q12: How does iteration performance of LinkedHashMap compare to HashMap?

Summary

Aspect	LinkedHashMap
Extends	HashMap
Ordering	Insertion order (default) or access order
Performance	Same as HashMap — O(1) for get/put
Extra memory	~16 bytes per entry (before/after pointers)
Best for	Predictable iteration, LRU caches, ordered JSON
Thread-safe	No
Null keys	One allowed
Key feature	`removeEldestEntry()` hook for bounded maps

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for LinkedHashMap in Java.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Java Master Course topic.

Search Terms

java-master-course, java master course, java, master, course, collections, framework, map

Continue learning this concept

PreviousHashtable in Java NextTreeMap in Java