Java LinkedHashMap Usage: Ordering and Cache Patterns

LinkedHashMap is the Java map implementation to reach for when iteration order matters. Unlike HashMap, which makes no guarantee about iteration order, LinkedHashMap maintains a doubly linked list across its entries. That list preserves either insertion order or access order, depending on the constructor you choose. For many real-world tasks — building an LRU cache, keeping configuration keys in declaration order, or producing deterministic output from a map — java linkedhashmap usage is the practical answer.

How LinkedHashMap Maintains Order

LinkedHashMap extends HashMap and adds a linked list that connects every entry in the map. When you put a new key-value pair, the entry is appended to the end of this list. Iterating over the map — via keySet(), values(), or entrySet() — follows the linked list, so entries come back in the order they were inserted.

This ordering costs a small amount of memory per entry (two extra references for the linked list pointers) and a small constant overhead per put and get operation. The asymptotic complexity remains the same as HashMap: O(1) average for put, get, and remove.

Map<String, Integer> ordered = new LinkedHashMap<>();
ordered.put("first", 1);
ordered.put("second", 2);
ordered.put("third", 3);

for (Map.Entry<String, Integer> entry : ordered.entrySet()) {
    System.out.println(entry.getKey());
}
// Output: first, second, third

The iteration order here is guaranteed by the LinkedHashMap contract. A plain HashMap could return the keys in any order, and that order can change when the map is resized.

The Two Ordering Modes

LinkedHashMap supports two ordering modes, selected through the constructor.

The default constructor new LinkedHashMap<>() uses insertion order. Re-inserting an existing key does not change its position in the iteration order; the entry stays where it was first placed.

The three-argument constructor new LinkedHashMap<>(initialCapacity, loadFactor, accessOrder) enables access order when the third argument is true. In access-order mode, every successful get or put moves the accessed entry to the end of the list. The most recently accessed entry is last, and the least recently accessed entry is first.

Map<String, Integer> accessOrdered = new LinkedHashMap<>(16, 0.75f, true);
accessOrdered.put("a", 1);
accessOrdered.put("b", 2);
accessOrdered.put("c", 3);

accessOrdered.get("a");

for (String key : accessOrdered.keySet()) {
    System.out.println(key);
}
// Output: b, c, a

Accessing "a" moved it to the end. This behavior is what makes LinkedHashMap suitable for LRU-style eviction.

Building an LRU Cache with removeEldestEntry

The protected removeEldestEntry(Map.Entry eldest) method is the hook that turns LinkedHashMap into a bounded cache. The method is called by put and putAll after the new entry has been inserted. If it returns true, the eldest entry — the first entry in the linked list — is removed.

public class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxEntries;

    public LruCache(int maxEntries) {
        super(16, 0.75f, true);
        this.maxEntries = maxEntries;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxEntries;
    }
}

When the map exceeds maxEntries, the eldest entry is evicted automatically. Combined with access-order mode, this gives a correct LRU eviction policy: the entries that have not been accessed for the longest time are the first entries in the list, so they are the ones removed.

The removeEldestEntry method is not called during get operations, only during put and putAll. That is the correct behavior for an LRU cache because eviction only needs to happen when the map grows.

Performance Characteristics and Memory Cost

LinkedHashMap has the same asymptotic performance as HashMap for all core operations. The linked list adds a constant overhead per operation because each put, get, and remove must also update the list pointers.

The memory overhead is one additional reference per entry for the linked list node. In access-order mode, get operations also require updating the list, which adds a small constant cost to what would otherwise be a read-only operation.

For most applications this overhead is negligible. If you are working with millions of entries and iteration order is irrelevant, a plain HashMap will use less memory. If you need deterministic iteration order, LinkedHashMap is the standard choice — there is no built-in map that gives you ordering without some cost.

When to Choose LinkedHashMap Over Other Maps

The decision between LinkedHashMap, HashMap, TreeMap, and ConcurrentHashMap depends on what you need.

Use LinkedHashMap when you need deterministic iteration order without paying for the logarithmic cost of TreeMap. Use access-order mode when you need an LRU cache. Use TreeMap when entries must be sorted by key. Use ConcurrentHashMap when multiple threads mutate the map concurrently.

LinkedHashMap is not thread-safe. If multiple threads access it and at least one modifies it, external synchronization is required. The Collections.synchronizedMap wrapper can be used, but for a concurrent LRU cache you would typically need a different design.

Common Pitfalls with Access Order

Access-order mode has a few behaviors that can surprise developers.

First, put on an existing key counts as an access. If you update the value of an existing key, that entry moves to the end of the list. This is usually what you want, but it means a cache refresh also resets the entry's position.

Second, containsKey does not trigger the reordering in access-order mode. Only get, put, and putAll move entries. The default getOrDefault implementation delegates to get, so it does refresh recency, but a direct containsKey call followed by a separate get will not move the entry until the get executes.

// This does NOT update recency
boolean exists = cache.containsKey("key");

// This DOES update recency
V value = cache.get("key");

If you need to check for presence and refresh recency in one step, call get and handle the null return value instead of using containsKey.

Third, iterating over the map in access-order mode does not change the order. Iteration is read-only with respect to the linked list structure.

Overriding removeEldestEntry for Different Policies

The default removeEldestEntry returns false, so a LinkedHashMap behaves like a regular map unless you override it. The override can implement any policy, not just a size bound.

For example, you could evict entries based on a timestamp stored in the value, or evict when a specific key is the eldest. The method receives the eldest entry, so the policy has access to both the key and the value.

@Override
protected boolean removeEldestEntry(Map.Entry<String, CacheValue> eldest) {
    return eldest.getValue().isExpired();
}

This gives you time-based eviction without a background thread. The check runs on every put, which is usually sufficient for a cache that is written to regularly.

One limitation: removeEldestEntry only sees the eldest entry. If you need to evict multiple entries at once, or evict based on a condition that applies to other entries, LinkedHashMap is not the right tool. A dedicated cache library such as Caffeine would be a better fit for complex eviction policies.

LinkedHashMap as a Deterministic Map for Serialization

One practical use of LinkedHashMap is producing deterministic output when serializing or hashing a map. A HashMap's iteration order can vary between JVM runs and even between map resize operations, which makes output non-deterministic. Replacing it with a LinkedHashMap in insertion order guarantees that keys are processed in the order they were added.

This matters for JSON serialization when key order should be stable, for generating signatures over map contents, and for producing reproducible test fixtures. The cost is minimal, and the benefit is that the output no longer depends on hash codes or map capacity.