Java LinkedHashMap: encounter order and a bounded cache model

Order is part of the contract

A plain HashMap deliberately leaves ordering unspecified. LinkedHashMap maintains an order so an application can produce repeatable output or identify the least recently accessed entry.

Insertion order is the default. Access order requires the constructor’s third argument to be true. Reading an existing entry then moves it to the most recently accessed end. That read can change structural iteration state; it is not a harmless shared read for concurrent code.

The program models a two-entry cache. It overrides removeEldestEntry to remove an old entry after a new mapping exceeds the capacity. Reading account-a before inserting account-c means account-b becomes the eviction candidate.

Bounded entries are not bounded bytes

A maximum entry count only bounds the number of mappings. One value might contain a large payload. Production caches need a memory budget or weighted sizing when payload sizes vary.

An eviction policy does not supply expiration, load coalescing, failure caching, or thread safety. This small model is useful for understanding access order. It is not a replacement for a tested cache library when a service has those requirements.

Cache values also need an ownership rule. A cached mutable object can be changed by any caller holding its reference. If the cached value is a configuration snapshot, prefer immutable content or return a defensive copy.

Working program

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

public class AccessOrderedCache {
    public static void main(String[] args) {
        Map<String, String> cache = new LinkedHashMap<String, String>(4, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
                return size() > 2;
            }
        };
        cache.put("account-a", "active");
        cache.put("account-b", "paused");
        cache.get("account-a");
        cache.put("account-c", "active");
        System.out.println(cache.keySet());
        System.out.println("account-b=" + cache.containsKey("account-b"));
    }
}

Output

[account-a, account-c]
account-b=false

Cost and design choices

Expected hash lookup cost remains constant with good key distribution. Maintaining encounter links adds per-entry references and constant bookkeeping for an access-order move. Iterating n entries follows encounter links in O(n) time.

The demonstration stores two entries, giving O(1) entry-count space under this fixed limit. For a configured maximum k, storage is O(k) entries plus the memory owned by their keys and values.

Do not hold an iterator while repeatedly calling get on the same access-ordered map. A design that needs both traversal and updates should define a snapshot or lock strategy explicitly.

Common Mistakes

• Do not call this cache thread-safe.
• Do not confuse containsKey with an access-order get operation.
• Do not interpret an entry-count limit as a guaranteed byte limit.

Connect the contracts

Compare the boundary explained in Mutation during iteration with the assumptions made by this program.

Compare the boundary explained in Shared state with the assumptions made by this program.

Extend the tested workflow

Continue with Java LinkedHashMap LRU cache: access order changes eviction.