LinkedHashMap in Java

Introduction

When working with Maps in Java, the standard HashMap is incredibly fast, but it suffers from one major drawback: it does not guarantee any order of its elements. When you iterate over a HashMap, the elements come out in seemingly random order.

Enter LinkedHashMap. It offers the lightning-fast O(1) lookups of a HashMap while maintaining a predictable iteration order. By default, it preserves the order in which elements were inserted, but it can also be configured to track the order in which elements were accessed—making it the perfect candidate for building caches (like an LRU Cache).

Core Concept: Deep Dive and Architecture

How It Works Internally

LinkedHashMap is a direct subclass of HashMap.

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

Internally, it uses the exact same hash table structure (an array of nodes/buckets) as HashMap to achieve O(1) time complexity for get() and put() operations.

The Magic: To maintain order, LinkedHashMap modifies the basic Node entry used in HashMap. It augments each entry with before and after pointers, effectively weaving a Doubly-Linked List through all the entries in the map.

• HashMap.Node has: hash, key, value, next (for collision resolution).
• LinkedHashMap.Entry extends this and adds: before, after (for maintaining iteration order).

Insertion Order vs. Access Order

By default, LinkedHashMap maintains Insertion Order. The first item put in is the first item you get out during iteration. However, via a special constructor, you can enable Access Order. In this mode, every time you get() or put() an entry, it is moved to the tail (end) of the doubly-linked list. The head of the list thus represents the Least Recently Used (LRU) element.

Code Examples

1. Beginner Example: Insertion Order

This example demonstrates the default behavior: maintaining insertion order.

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

public class LinkedHashMapBasic {
    public static void main(String[] args) {
        Map<String, Integer> scores = new LinkedHashMap<>();
        
        scores.put("Alice", 90);
        scores.put("Bob", 85);
        scores.put("Charlie", 95);
        
        // Iteration perfectly respects the order of insertion
        for (Map.Entry<String, Integer> entry : scores.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
        // Output: Alice: 90, Bob: 85, Charlie: 95
    }
}

2. Advanced Example: Building an LRU Cache

Because LinkedHashMap can track access order and provides a handy removeEldestEntry() method, it is trivial to implement an LRU (Least Recently Used) cache.

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) {
        // capacity, loadFactor (default 0.75), accessOrder (true)
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    // This method is called by put() and putAll() after inserting a new entry.
    // If it returns true, the eldest entry (the head of the list) is removed.
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > this.capacity;
    }

    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3); // Max 3 items
        
        cache.put(1, "One");
        cache.put(2, "Two");
        cache.put(3, "Three"); // Cache is full: [1, 2, 3]
        
        cache.get(1); // Accesses '1', moving it to the end: [2, 3, 1]
        
        cache.put(4, "Four"); // Triggers removal of eldest ('2'). Cache: [3, 1, 4]
        
        System.out.println(cache); // Output: {3=Three, 1=One, 4=Four}
    }
}

Time Complexity

| Operation | LinkedHashMap Complexity | HashMap Complexity | | :--- | :--- | :--- | | put() | O(1) | O(1) | | get() | O(1) | O(1) | | remove()| O(1) | O(1) | | Iteration | O(N) | O(Capacity + N) |

Note: While LinkedHashMap has the same Big-O time complexity as HashMap, it performs slightly slower in practice due to the overhead of maintaining the doubly-linked list pointers on every insertion/removal.

Common Mistakes Beginners Make

1. Assuming Thread Safety

The Mistake: Using LinkedHashMap in a highly concurrent environment without synchronization. The Fix: Like HashMap, LinkedHashMap is not thread-safe. Use Collections.synchronizedMap(new LinkedHashMap<>()) or consider ConcurrentHashMap (though ConcurrentHashMap does not guarantee order).

2. Using it When Order Doesn't Matter

The Mistake: Using LinkedHashMap everywhere just to be safe. The Fix: If you do not care about the order of iteration, use HashMap. LinkedHashMap consumes more memory (due to before and after pointers) and has a marginally slower insertion/deletion time.

Interview Q&A

Q1: How does LinkedHashMap maintain order? Answer: It maintains a doubly-linked list running through all its entries. Every time a new element is added, it is appended to the tail of this list.

Q2: What is the difference between TreeMap and LinkedHashMap? Answer: LinkedHashMap maintains the order of insertion (or access) and offers O(1) time complexity. TreeMap sorts the keys based on their natural ordering (e.g., alphabetically or numerically) or a custom Comparator, but its time complexity is O(log N) because it is backed by a Red-Black tree.

Q3: How do you configure a LinkedHashMap to be an LRU cache? Answer: Instantiate it using the constructor that takes accessOrder and set it to true. Then, override the removeEldestEntry(Map.Entry<K,V> eldest) method to return true when the size of the map exceeds the desired maximum capacity.

Summary

• LinkedHashMap extends HashMap and implements Map.
• It maintains a predictable iteration order using a doubly-linked list.
• It supports two ordering modes: Insertion-order (default) and Access-order.
• It provides O(1) time complexity for standard operations, mimicking HashMap.
• It is the standard structure used in Java to create LRU Caches.