Java LinkedHashMap Access Order Explained

When you create a LinkedHashMap in Java, the default iteration order is insertion order. But the constructor also accepts an accessOrder flag that changes how the map keeps track of its entries. Understanding java linkedhashmap access order is essential when you need to build a cache that evicts the least recently used items.

What Access Order Means in LinkedHashMap

A LinkedHashMap maintains a doubly linked list of its entries. The list determines the order in which entries are returned by the iterator. With the default accessOrder value of false, the list is ordered by insertion: the first entry inserted is the first one iterated, and so on.

When you set accessOrder to true, the list is reordered on every access. An access is any call to get, put, putIfAbsent, getOrDefault, or any method that retrieves or updates a value. After such a call, the affected entry is moved to the end of the list, effectively marking it as the most recently used. This behavior is what makes LinkedHashMap suitable for building an LRU (least recently used) cache without writing a separate data structure.

Enabling Access Order Mode

The constructor that accepts the flag is LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder). You can also use the three-argument constructor with a default capacity and load factor, but the most common pattern is to specify all three parameters explicitly.

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

Once the map is created with accessOrder = true, every get or put operation moves the corresponding entry to the tail of the internal linked list. Iteration then reflects the order from least recently accessed to most recently accessed. Note that put on an existing key also counts as an access, because it updates the value and moves the entry.

How Iteration Order Changes with Access

Consider a simple example. Insert three entries, then read one of them, and observe the iteration order.

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

map.get("a"); // access "a"

for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey());
}

The output is:

b
c
a

Initially the order was a, b, c. After accessing a, it moves to the end, so the iteration order becomes b, c, a. If you access b next, the order becomes c, a, b. This reordering happens on every read, which is the key difference from insertion order mode.

Building an LRU Cache with LinkedHashMap

Access order mode is the foundation for a simple LRU cache. The idea is to keep the map size bounded and remove the eldest entry when a new entry is added beyond a limit. LinkedHashMap provides a protected method removeEldestEntry that is called after every put and putAll. By overriding it to return true when the size exceeds a threshold, you can automatically evict the least recently used entry.

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;
    }
}

Here is how you would use it:

LRUCache<String, String> cache = new LRUCache<>(3);
cache.put("user:1", "Alice");
cache.put("user:2", "Bob");
cache.put("user:3", "Carol");

cache.get("user:1"); // marks user:1 as most recently used
cache.put("user:4", "Dave"); // size exceeds 3, so eldest (user:2) is removed

System.out.println(cache.keySet()); // [user:3, user:1, user:4]

Because removeEldestEntry is called after the insertion, the map first adds the new entry, then checks the condition. The eldest entry is the one at the head of the list, which is the least recently accessed. This gives you an efficient LRU cache without external synchronization, provided you do not access the map from multiple threads without additional locking.

Performance and Memory Considerations

LinkedHashMap inherits the O(1) average time complexity for get and put from HashMap. The access order mode does not change that complexity; it only adds a constant overhead of moving a node in the doubly linked list on each access. This is a small cost compared to the benefit of having an LRU ordering built into the map.

Memory usage is higher than a plain HashMap because each entry also holds references to the previous and next nodes in the linked list. For most applications this overhead is acceptable, but if you are storing millions of entries and never need access order, a HashMap is more memory-efficient.

One subtle point: in access order mode, calling containsKey or containsValue does not count as an access. Only operations that retrieve or update the value move the entry. If you need to treat a containsKey check as an access, you must explicitly call get after the check, or design your logic accordingly.

Choosing Between Access Order and Insertion Order

The decision comes down to whether you need to know the order in which entries were added or the order in which they were last used.

Use insertion order (accessOrder = false, the default) when:

• You want to preserve the order in which keys were first added.
• You are building a data structure that must reflect the sequence of insertion, such as a simple cache that evicts the oldest inserted item (FIFO).
• You need predictable iteration that does not change when you read values.

Use access order (accessOrder = true) when:

• You need to evict the least recently used item, not the least recently inserted.
• You are implementing an LRU cache or a similar pattern where the recency of access matters.
• You want iteration to reflect the order of last access, which can be useful for analytics or cleanup tasks.

There is no performance advantage of one mode over the other; the only difference is the reordering behavior. Choose based on the semantic requirement of your application.

Common Pitfalls and Edge Cases

Access order mode changes the map's behavior in ways that can surprise developers who are used to insertion order.

Modification during iteration. If you iterate over the map and call get inside the loop, the iteration order changes while you are iterating. This can lead to ConcurrentModificationException because the internal list is modified. Even if the exception is not thrown, the iteration order becomes unpredictable. If you need to access entries while iterating, collect the keys first or use a separate data structure.

Null keys and values. LinkedHashMap allows one null key and multiple null values, just like HashMap. Access order mode does not change this. However, if you use a custom removeEldestEntry that relies on the key or value, be aware that null may appear.

Thread safety. LinkedHashMap is not thread-safe. In access order mode, concurrent reads and writes can corrupt the linked list. If you need thread safety, wrap the map with Collections.synchronizedMap or use a ConcurrentHashMap with a custom eviction policy, but note that ConcurrentHashMap does not maintain any order. For a thread-safe LRU cache, consider using a ConcurrentSkipListMap with timestamps or a dedicated cache library.

Impact on equals and hashCode. The access order flag does not affect equality or hash code behavior. Two LinkedHashMap instances with the same mappings are equal regardless of their iteration order. This is consistent with the Map contract.

When to avoid access order. If your map is large and you frequently call get on many entries, the reordering overhead becomes noticeable. In such cases, a HashMap or a custom data structure that tracks usage separately may be more appropriate. Measure the actual impact before optimizing prematurely.