Java LinkedHashMap Insertion Order Explained

What LinkedHashMap Guarantees About Order

When you iterate over a HashMap, the order of entries depends on hash values and the current capacity of the table. That order is not meaningful and can change when the map is resized. LinkedHashMap solves this by combining the hash-based storage of HashMap with a doubly linked list that records the order in which entries were inserted. This is what makes java linkedhashmap insertion order a reliable, documented behavior rather than an accident of the hash table.

Map<String, String> config = new LinkedHashMap<>();
config.put("host", "localhost");
config.put("port", "8080");
config.put("timeout", "30");

for (Map.Entry<String, String> entry : config.entrySet()) {
    System.out.println(entry.getKey() + "=" + entry.getValue());
}

The output is always:

host=localhost
port=8080
timeout=30

Re-inserting an existing key does not change its position. If you call config.put("port", "9090") again, the entry stays in its original position; only the value is updated. Insertion order reflects the first time a key was inserted, not the last time it was written.

How the Doubly Linked List Preserves Insertion Order

LinkedHashMap extends HashMap and adds two pointers to each entry: before and after. These pointers connect every entry in a single linked list. When a new key is inserted, the map appends the new entry to the tail of that list. When an existing key is updated, the list structure is left untouched.

This design means iteration order is independent of the hash table's internal bucket layout. Even if the map is resized or rehashed, the linked list order remains stable. That is why LinkedHashMap can guarantee insertion order while HashMap cannot.

The memory cost is real but small: each entry carries two extra references. For maps with millions of entries, that overhead can matter, but for typical application data it is usually negligible.

The Difference Between Insertion Order and Access Order

LinkedHashMap has a second mode: access order. You enable it by passing true as the third constructor argument:

Map<String, String> recent = new LinkedHashMap<>(16, 0.75f, true);

In access-order mode, every call to get, put, or putIfAbsent moves the affected entry to the tail of the linked list. Iteration then reflects the order of most recent access rather than insertion. This mode exists specifically to support cache eviction policies.

The two modes are mutually exclusive in practice. You choose one at construction time and the behavior stays fixed for the life of the map. If you need both behaviors, you need two separate maps.

Building an LRU Cache with Access-Order Mode

Access-order mode becomes useful when combined with removeEldestEntry. That protected method is called by put and putAll after a new entry is inserted. If it returns true, the oldest entry in the map is removed. This gives you a complete least-recently-used cache in a small amount of code:

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;

    public LRUCache(int maxSize) {
        super(maxSize, 0.75f, true);
        this.maxSize = maxSize;
    }

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

The initial capacity passed to the super constructor is not a hard limit; it is just the initial table size. The real limit is enforced by removeEldestEntry. Once the map exceeds maxSize, the eldest entry is evicted on the next insertion.

This approach is simple and correct for single-threaded use. It does not handle concurrency, and it does not support expiration by time. If those requirements exist, a dedicated cache library is a better fit.

Performance and Memory Cost Compared with HashMap

LinkedHashMap has the same asymptotic complexity as HashMap for get, put, containsKey, and remove: O(1) average case. The linked list adds a constant amount of work per operation because the map must update the before and after pointers on every insertion, removal, and, in access-order mode, every successful get.

Iteration is where LinkedHashMap can actually be faster than HashMap. A HashMap iterator walks the bucket array and skips empty buckets; a LinkedHashMap iterator walks the linked list directly. For sparse tables, the difference is noticeable.

The memory overhead is the main reason not to use LinkedHashMap everywhere. If you never rely on order, HashMap uses less memory and is the simpler choice.

Thread Safety and Concurrent Access

LinkedHashMap is not thread-safe, just like HashMap. Concurrent modification from multiple threads can corrupt the linked list structure, producing lost entries, infinite loops during iteration, or ConcurrentModificationException.

If you need thread-safe access with insertion order, the standard library does not provide a direct concurrent equivalent. ConcurrentHashMap does not preserve any order. ConcurrentSkipListMap preserves sorted order, not insertion order. Collections.synchronizedMap(new LinkedHashMap<>(...)) gives you thread safety by locking the entire map, but it serializes all access and does not support lock-free reads.

For most cache and ordering needs, the practical choice is to protect a LinkedHashMap with explicit synchronization when concurrency is low, or to use a dedicated concurrent cache implementation when it is not.

When to Choose LinkedHashMap Over Other Map Types

Use LinkedHashMap when the order of entries matters and you want predictable iteration. Common cases include:

• Rendering configuration in the order it was defined
• Producing output that must match a fixed field sequence
• Building a simple LRU cache with access-order mode
• Debugging or logging where entry order helps trace execution

Do not use it when you need sorted order; TreeMap is the right tool for that. Do not use it when you need concurrent access without external locking. And do not use it when memory is tight and order is irrelevant.

The decision comes down to one question: does the order of your map entries carry meaning? If yes, LinkedHashMap is the standard answer in the Java collections framework. If no, HashMap is lighter and simpler.