LinkedHashMap

// ── LinkedHashMap preserves insertion order: ─────────────────────────
Map<String, Integer> linked = new LinkedHashMap<>();
linked.put("Charlie", 3);
linked.put("Alice",   1);
linked.put("Bob",     2);

System.out.println(linked);   // {Charlie=3, Alice=1, Bob=2}
// Insertion order is preserved — NOT alphabetical

// Compare with HashMap (unpredictable order):
Map<String, Integer> hash = new HashMap<>();
hash.put("Charlie", 3);
hash.put("Alice",   1);
hash.put("Bob",     2);
System.out.println(hash);     // {Bob=2, Charlie=3, Alice=1} — arbitrary

// ── Re-insert does NOT change position: ──────────────────────────────
linked.put("Charlie", 99);   // updates value, order unchanged
System.out.println(linked);  // {Charlie=99, Alice=1, Bob=2} — Charlie still first

// ── Iteration in insertion order: ────────────────────────────────────
for (Map.Entry<String, Integer> e : linked.entrySet()) {
    System.out.printf("%-10s → %d%n", e.getKey(), e.getValue());
}
// Charlie    → 99
// Alice      → 1
// Bob        → 2

// ── Access-order mode: ────────────────────────────────────────────────
// Constructor: LinkedHashMap(initialCapacity, loadFactor, accessOrder)
Map<String, Integer> accessOrder = new LinkedHashMap<>(16, 0.75f, true);
accessOrder.put("a", 1);
accessOrder.put("b", 2);
accessOrder.put("c", 3);
System.out.println(accessOrder);  // {a=1, b=2, c=3}

accessOrder.get("a");             // access "a" — moves to tail
System.out.println(accessOrder);  // {b=2, c=3, a=1} — "a" moved to end

accessOrder.get("c");             // access "c" — moves to tail
System.out.println(accessOrder);  // {b=2, a=1, c=3}
// Head is LRU (least recently used) — "b" was accessed least recently

// ── LRU Cache using LinkedHashMap: ───────────────────────────────────
public class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxCapacity;

    public LruCache(int maxCapacity) {
        super(maxCapacity, 0.75f, true);  // true = access-order
        this.maxCapacity = maxCapacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // Called after each put() — remove head (LRU) when over capacity:
        return size() > maxCapacity;
    }
}

// ── Using the LRU cache: ──────────────────────────────────────────────
LruCache<Integer, String> cache = new LruCache<>(3);
cache.put(1, "one");
cache.put(2, "two");
cache.put(3, "three");
System.out.println(cache);   // {1=one, 2=two, 3=three}

cache.get(1);                // access key 1 — moves to tail (most recent)
System.out.println(cache);   // {2=two, 3=three, 1=one}

cache.put(4, "four");        // capacity exceeded — evicts LRU (key 2)
System.out.println(cache);   // {3=three, 1=one, 4=four}  — key 2 evicted

cache.put(5, "five");        // evicts LRU (key 3)
System.out.println(cache);   // {1=one, 4=four, 5=five}

// ── Thread-safe LRU cache: ────────────────────────────────────────────
Map<Integer, String> syncCache = Collections.synchronizedMap(
    new LruCache<>(100));
// Individual operations are thread-safe; iteration still needs sync.

// ── Practical: computeIfAbsent for cache-aside pattern: ───────────────
LruCache<String, User> userCache = new LruCache<>(500);

public User getUser(String userId) {
    return userCache.computeIfAbsent(userId, id -> database.findUser(id));
    // Cache miss → calls database.findUser → caches result
    // Cache hit  → returns cached value without touching database
}