SyntaxPilot
Courses/Low-Level Design/Lesson 65
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Low-Level Design · Lesson 65 of 90

Design an LRU cache

cacheeviction policyLRUHashMap plus doubly linked listO(1) get and putsentinel nodesLinkedHashMap with accessOrderremoveEldestEntrycapacitygeneric cache interfacethread-safe LRU

These are the notes for Low-Level Design (LLD) episode 65: the LRU cache, one of the most asked interview questions and a real part of almost every fast system. We start from what a cache is, watch "keep everything" and "evict the oldest" fail, invent the LRU eviction policy, build it with a list (correct but slow), then with a HashMap plus a doubly linked list and sentinel nodes for O(1) get and put, behind a generic cache interface. Then Java's shortcut, LinkedHashMap with accessOrder and removeEldestEntry, and a thread-safe LRU.

How the code was run: every program was saved as Main.java in a fresh folder and run with javac Main.java && java -cp . Main on OpenJDK 21. Every output below is the real output, pasted exactly. The users, ids and the "slow database" are made up for teaching.

1. The problem: the kitchen counter

In the kitchen In software
The storeroom: every jar, but a walk away The database: all the data, but slow to reach
The counter by the stove: room for 3 jars The cache: small and fast
Needing a 4th jar: one must go back Eviction: removing an item to make room
Putting back the jar untouched longest; salt never leaves LRU: evict the least recently used item

2. What a cache is

  • Cache: a small, fast store that keeps copies of data that is slow to get. Example: user profiles kept in memory in front of a database.
  • Hit: the answer is already in the cache. Fast.
  • Miss: it isn't; go to the slow source, and keep a copy for next time.
  • Capacity: the most items the cache may hold, like 3 jars on the counter.
  • Hit rate: hits ÷ (hits + misses). Higher is better.

Our pretend database takes about 200 ms a call, so we count database calls: fewer is better.

3. Attempt 1 and 2: keep everything, or evict the oldest

import java.util.*;
public class Main {
    static int dbCalls = 0;
    static String slowDb(int id) { dbCalls++;  return "user" + id; }      // pretend: 200 ms each
    public static void main(String[] args) {
        Map<Integer, String> all = new HashMap<>();                       // attempt 1: keep everything
        for (int id = 0; id < 1_000_000; id++) all.computeIfAbsent(id, Main::slowDb);
        System.out.println("no limit: " + all.size() + " entries in memory, and growing");

        int capacity = 3;  dbCalls = 0;  int hits = 0;                     // attempt 2: 3 slots
        Map<Integer, String> cache = new HashMap<>();  Deque<Integer> order = new ArrayDeque<>();
        for (int id : new int[]{7, 1, 7, 2, 7, 3, 7, 4, 7, 5, 7}) {         // user 7 is the hot one
            if (cache.containsKey(id)) { hits++;  continue; }
            if (cache.size() == capacity) {
                int old = order.pollFirst();                              // evict the OLDEST put
                cache.remove(old);  System.out.println("evict " + old); }
            cache.put(id, slowDb(id));  order.addLast(id);
        }
        System.out.println("oldest-first: hits " + hits + ", db calls " + dbCalls);
    }
}

Real output:

no limit: 1000000 entries in memory, and growing
evict 7
evict 1
evict 2
evict 3
oldest-first: hits 4, db calls 7
  • Keep everything: a million entries and growing. Memory is finite; a cache with no limit is just a slow copy of the database.
  • Evict the oldest put (FIFO, first in, first out): the very first eviction is user 7, the hot one, requested every other time. 4 hits, 7 database calls.

Why it failed: an eviction policy is the rule that picks who leaves. FIFO looks only at when an item arrived, never at when it was last used.

4. LRU: least recently used

LRU (Least Recently Used): when the cache is full, evict the item that hasn't been used for the longest time. Every get or put makes that key the most recently used. It's a bet that what you used just now, you'll use again soon, which is true for many real workloads (a few hot users, a few hot pages).

Attempt 3: LRU with a plain list

The list keeps the order: front = least recently used, back = most recently used. We count every element walked past (indexOf) or shifted (remove in an ArrayList) as a step.

import java.util.*;
class ListLRU {                                   // LRU with a plain list: front = least recently used
    final int capacity;  final Map<Integer, String> map = new HashMap<>();
    final List<Integer> order = new ArrayList<>();  long steps = 0;  int hits = 0, misses = 0;
    ListLRU(int capacity) { this.capacity = capacity; }
    void touch(int id) { int i = order.indexOf(id);  steps += i + 1;      // walk the list to find it
                         order.remove(i);  steps += order.size() - i;  order.add(id); }  // shift the rest
    String get(int id) {
        if (map.containsKey(id)) { hits++;  touch(id);  return map.get(id); }
        misses++;
        if (map.size() == capacity) { int lru = order.remove(0);  steps += order.size();  map.remove(lru);
                                      if (capacity == 3) System.out.println("evict " + lru); }
        map.put(id, "user" + id);  order.add(id);  return map.get(id); } }
public class Main { public static void main(String[] args) {
    ListLRU small = new ListLRU(3);
    for (int id : new int[]{7, 1, 7, 2, 7, 3, 7, 4, 7, 5, 7}) small.get(id);
    System.out.println("LRU: hits " + small.hits + ", db calls " + small.misses);

    ListLRU big = new ListLRU(10_000);  Random r = new Random(42);
    for (int i = 0; i < 200_000; i++) big.get(r.nextInt(12_000));
    System.out.printf("200,000 gets: %,d hits, %,d list steps%n", big.hits, big.steps);
}}

Real output:

evict 1
evict 2
evict 3
LRU: hits 5, db calls 6
200,000 gets: 160,235 hits, 1,873,324,054 list steps

Correct: now 1, 2 and 3 are evicted and user 7 stays (5 hits, 6 database calls). But 1,873,324,054 steps for 200,000 gets: almost 10,000 steps per get.

5. Why the list is slow, and what we need

Big-O (episode 4) describes how the work grows with n, the number of items.

Operation ArrayList What we need
Find a key's position indexOf: walk the list, O(n) O(1): a HashMap
Remove from the middle shift everything after it, O(n) O(1): a doubly linked list
Add at the end O(1) (amortised) O(1)

O(1) ("order one", constant time): the same small amount of work whether the cache holds 3 items or 3 million.

A doubly linked list is a chain of nodes where each node knows both its previous and its next node. A node can leave the chain by joining its two neighbours to each other: no walking, no shifting.

The idea: a HashMap from key to its node, and the nodes in a doubly linked list ordered from most to least recently used. The map finds; the list orders.

6. Sentinel nodes

A sentinel node is a dummy node that holds no data and is always there. We keep two: head (before the most recent) and tail (after the least recent). Because every real node always has a prev and a next, unlink and addFront never need if (x == null) checks, and the least recently used node is simply tail.prev.

head ⇄ [7] ⇄ [5] ⇄ [4] ⇄ tail        get(4):  unlink [4], addFront [4]
head ⇄ [4] ⇄ [7] ⇄ [5] ⇄ tail        full?    victim = tail.prev = [5]

7. HashMap + doubly linked list, behind a generic cache interface

A generic cache interface uses type parameters K and V (episode 3), so the same cache works for any key and value types: Cache<Integer, String>, Cache<String, byte[]>.

import java.util.*;
interface Cache<K, V> { Optional<V> get(K key);  void put(K key, V value);  int size(); }
class LRUCache<K, V> implements Cache<K, V> {
    private class Node { K key;  V val;  Node prev, next;  Node(K k, V v) { key = k;  val = v; } }
    private final int capacity;  private final Map<K, Node> map = new HashMap<>();
    private final Node head = new Node(null, null), tail = new Node(null, null);  // sentinels
    LRUCache(int capacity) { this.capacity = capacity;  head.next = tail;  tail.prev = head; }
    private void unlink(Node n) { n.prev.next = n.next;  n.next.prev = n.prev; }
    private void addFront(Node n) { n.next = head.next;  n.prev = head;  head.next.prev = n;  head.next = n; }
    public Optional<V> get(K key) {
        Node n = map.get(key);  if (n == null) return Optional.empty();
        unlink(n);  addFront(n);  return Optional.of(n.val); }        // now the MOST recently used
    public void put(K key, V value) {  Node n = map.get(key);
        if (n != null) { n.val = value;  unlink(n);  addFront(n);  return; }
        if (map.size() == capacity) { Node lru = tail.prev;  unlink(lru);  map.remove(lru.key);
                                      if (capacity == 3) System.out.println("evict " + lru.key); }
        n = new Node(key, value);  map.put(key, n);  addFront(n); }
    public int size() { return map.size(); } }
public class Main {  static int hits, misses;
    static void load(Cache<Integer, String> c, int id) {
        if (c.get(id).isPresent()) hits++;  else { misses++;  c.put(id, "user" + id); } }
    public static void main(String[] args) {
        Cache<Integer, String> small = new LRUCache<>(3);
        for (int id : new int[]{7, 1, 7, 2, 7, 3, 7, 4, 7, 5, 7}) load(small, id);
        System.out.println("LRU: hits " + hits + ", db calls " + misses);
        Cache<Integer, String> big = new LRUCache<>(10_000);  Random r = new Random(42);  hits = 0;
        for (int i = 0; i < 200_000; i++) load(big, r.nextInt(12_000));
        System.out.printf("200,000 gets: %,d hits, size %,d, no list walking%n", hits, big.size()); } }

Real output:

evict 1
evict 2
evict 3
LRU: hits 5, db calls 6
200,000 gets: 160,235 hits, size 10,000, no list walking

The same answer as the list (5 hits, 6 database calls; and the very same 160,235 hits in the big test), but every get and put is a fixed handful of pointer changes: O(1).

Method Steps Cost
get(k) map.get → unlink → addFront O(1)
put(k) existing update value → unlink → addFront O(1)
put(k) new, full tail.prev → unlink → map.remove → new node → map.put → addFront O(1)

8. Java's shortcut: LinkedHashMap with accessOrder and removeEldestEntry

LinkedHashMap (episode 4) is exactly a HashMap plus a doubly linked list inside.

  • new LinkedHashMap<>(16, 0.75f, accessOrder): initial size 16, load factor 0.75 (how full the table gets before it grows), and accessOrder.
  • accessOrder = false (the default): the order keys were first inserted. That is FIFO.
  • accessOrder = true: every get or put moves the key to the end: LRU order.
  • removeEldestEntry(eldest): a method LinkedHashMap calls after every put, passing the eldest entry (the least recently used, in access order). Return true and it is removed.
import java.util.*;
class LRU<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    LRU(int capacity, boolean accessOrder) { super(16, 0.75f, accessOrder);  this.capacity = capacity; }
    @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {   // asked after every put
        return size() > capacity;                          // true = remove the eldest entry
    }
}
public class Main {
    static void demo(String name, Map<Integer, String> c) {
        c.put(1, "a");  c.put(2, "b");  c.put(3, "c");
        c.get(1);                                          // user 1 was just used
        c.put(4, "d");                                     // one too many: who leaves?
        System.out.println(name + ": " + c.keySet());
    }
    public static void main(String[] args) {
        demo("accessOrder false", new LRU<>(3, false));
        demo("accessOrder true ", new LRU<>(3, true));
    }
}

Real output:

accessOrder false: [2, 3, 4]
accessOrder true : [3, 1, 4]

With false, user 1 was evicted although it was just used. With true, user 2 (untouched longest) left. One boolean changes the whole policy.

9. A thread-safe LRU

A thread is one path of work; a server runs many at once (episode 46). A race condition is when two threads change shared data at the same moment and their changes mix up. Thread-safe means it stays correct even when many threads call it.

The trap: in an LRU cache even get changes the list (it moves the key), so get is not a harmless read.

import java.util.*;
class LRU<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    LRU(int capacity) { super(16, 0.75f, true);  this.capacity = capacity; }
    @Override protected boolean removeEldestEntry(Map.Entry<K, V> e) { return size() > capacity; } }
public class Main {
    static void hammer(String name, Map<Integer, Integer> cache) throws InterruptedException {
        List<Thread> threads = new ArrayList<>();
        for (int t = 0; t < 4; t++) threads.add(Thread.ofPlatform().start(() -> {   // 4 threads at once
            Random r = new Random();
            for (int i = 0; i < 200_000; i++) { int k = r.nextInt(200);  cache.get(k);  cache.put(k, i); }
        }));
        for (Thread t : threads) t.join();
        System.out.println(name + ": size " + cache.size() + ", capacity 100");
    }
    public static void main(String[] args) throws InterruptedException {
        hammer("no lock     ", new LRU<>(100));
        hammer("synchronized", Collections.synchronizedMap(new LRU<>(100)));
    }
}

One real run:

no lock     : size 203, capacity 100
synchronized: size 100, capacity 100

With no lock the size runs far past the capacity (it changes every run: we saw 216, 202 and 199 in other runs; with only 200 distinct keys, 216 means the list was corrupted). With one lock (Collections.synchronizedMap wraps every call in synchronized), it is exactly 100.

A read lock on get is not enough. We also tried a ReentrantReadWriteLock with the read lock on get (many readers at once) and the write lock on put. Three real runs printed:

read lock on get: size 100, capacity 100
read lock on get: size 100, capacity 100
read lock on get: size 199, capacity 100

It passes sometimes and breaks sometimes: the worst kind of bug. Because get reorders the list, it needs the same exclusive lock as put. For more speed under many threads, split the cache into shards (several smaller caches, each with its own lock, chosen by the key's hash).

10. The class diagram

Cache<K, V>  (interface: get, put, size)
 └─implemented by─▶ LRUCache<K, V>
      ├─has──▶ HashMap<K, Node>         key → its node, found in O(1)
      └─has──▶ doubly linked list       head ⇄ MRU ⇄ ... ⇄ LRU ⇄ tail  (sentinels)
get(k):  map → node → unlink → addFront                 O(1)
put(k):  full? → remove tail.prev from list and map → addFront   O(1)
shortcut: LinkedHashMap(16, 0.75f, true) + removeEldestEntry
threads:  one lock around get AND put (get changes the order too)

11. Interview follow-ups

Follow-up Answer
Expire old entries TTL (time to live): store expiresAt; an expired entry is a miss (practice 2)
Faster under many threads Shards: N small LRUs, each with its own lock, picked by hash(key) % N
How good is the cache? Cache statistics: hits, misses, evictions, hit rate (mini project)
Frequency matters more than recency LFU: next episode
Limit in bytes, not items Give each entry a weight; evict until the new one fits
Swap the policy An EvictionPolicy interface: next episode
Two threads miss the same key at once Both load it from the database; fix with a per-key "loading" future (computeIfAbsent on a ConcurrentHashMap<K, CompletableFuture<V>>)

12. Common mistakes

Mistake What you see (real) Why Fix
No capacity 1000000 entries in memory, and growing Memory is finite A capacity and an eviction policy
Evict the oldest put evict 7 (the hot user) FIFO ignores use LRU: move on every get
ArrayList for the order 1,873,324,054 list steps indexOf + shifting is O(n) Doubly linked list + HashMap
accessOrder left false [2, 3, 4]: user 1 evicted Insertion order new LinkedHashMap<>(16, 0.75f, true)
No lock size 203, capacity 100 Race condition One lock for get and put
Read lock on get sometimes size 199, capacity 100 get changes the list Exclusive lock for get too
Capacity 0 or negative (mini project) IllegalArgumentException: capacity must be positive No room for anything Validate in the constructor

Mini project: a thread-safe LRU cache with statistics in front of a slow service

The cache-aside pattern: the service checks the cache first; on a miss it loads from the database and stores the result.

import java.util.*;
import java.util.function.Function;

interface Cache<K, V> {
    Optional<V> get(K key);
    void put(K key, V value);
    int size();
}

// HashMap + doubly linked list with sentinels; synchronized = thread-safe; counts hits and misses.
class LRUCache<K, V> implements Cache<K, V> {
    private final class Node { K key; V val; Node prev, next; Node(K k, V v) { key = k; val = v; } }
    private final int capacity;
    private final Map<K, Node> map = new HashMap<>();
    private final Node head = new Node(null, null), tail = new Node(null, null);
    private long hits, misses, evictions;

    LRUCache(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
        this.capacity = capacity;  head.next = tail;  tail.prev = head;
    }
    private void unlink(Node n) { n.prev.next = n.next;  n.next.prev = n.prev; }
    private void addFront(Node n) { n.next = head.next;  n.prev = head;  head.next.prev = n;  head.next = n; }

    public synchronized Optional<V> get(K key) {
        Node n = map.get(key);
        if (n == null) { misses++;  return Optional.empty(); }
        hits++;  unlink(n);  addFront(n);
        return Optional.of(n.val);
    }
    public synchronized void put(K key, V value) {
        Node n = map.get(key);
        if (n != null) { n.val = value;  unlink(n);  addFront(n);  return; }
        if (map.size() == capacity) { Node lru = tail.prev;  unlink(lru);  map.remove(lru.key);  evictions++; }
        n = new Node(key, value);  map.put(key, n);  addFront(n);
    }
    public synchronized int size() { return map.size(); }
    public synchronized List<K> keysMostRecentFirst() {
        List<K> out = new ArrayList<>();
        for (Node n = head.next; n != tail; n = n.next) out.add(n.key);
        return out;
    }
    public synchronized String stats() {
        return String.format("hits %d, misses %d, evictions %d, hit rate %.1f%%", hits, misses, evictions,
                             100.0 * hits / Math.max(1, hits + misses));
    }
}

// A slow "database" behind the cache: the cache-aside pattern (check the cache, else load and store).
class ProfileService {
    private final Cache<Integer, String> cache;  private final Function<Integer, String> db;
    int dbCalls = 0;
    ProfileService(Cache<Integer, String> cache, Function<Integer, String> db) { this.cache = cache;  this.db = db; }
    String profile(int id) {
        return cache.get(id).orElseGet(() -> { dbCalls++;  String p = db.apply(id);  cache.put(id, p);  return p; });
    }
}

public class Main {
    public static void main(String[] args) throws InterruptedException {
        LRUCache<Integer, String> cache = new LRUCache<>(3);
        ProfileService svc = new ProfileService(cache, id -> "profile of user " + id);
        for (int id : new int[]{7, 1, 7, 2, 7, 3, 7, 4, 7, 5, 7}) svc.profile(id);
        System.out.println("order (most recent first): " + cache.keysMostRecentFirst());
        System.out.println(cache.stats() + ", db calls " + svc.dbCalls);

        LRUCache<Integer, Integer> shared = new LRUCache<>(100);
        List<Thread> ts = new ArrayList<>();
        for (int t = 0; t < 4; t++) ts.add(Thread.ofPlatform().start(() -> {
            Random r = new Random();
            for (int i = 0; i < 200_000; i++) { int k = r.nextInt(200);  if (shared.get(k).isEmpty()) shared.put(k, i); }
        }));
        for (Thread t : ts) t.join();
        System.out.println("4 threads: size " + shared.size() + " (capacity 100)");

        try { new LRUCache<String, String>(0); } catch (IllegalArgumentException e) { System.out.println(e); }
    }
}

Real output:

order (most recent first): [7, 5, 4]
hits 5, misses 6, evictions 3, hit rate 45.5%, db calls 6
4 threads: size 100 (capacity 100)
java.lang.IllegalArgumentException: capacity must be positive

Note: profile() does get then put as two separate locked calls, so two threads that miss the same key at the same moment may both call the database. The cache stays correct; it just does a little extra work (see the last follow-up).

Practice

1. Add a hit-rate counter to LRUCache.

Answer

Count hits and misses in get, and report hits / (hits + misses): see stats() in the mini project. Real output: hits 5, misses 6, evictions 3, hit rate 45.5%, db calls 6.

2. Add a TTL to every entry, with an injected clock, and write get(key) that returns -1 on a miss.

Answer
import java.util.*;
import java.util.function.LongSupplier;

// Practice: LRU with a TTL per entry, an injected clock, and get() returning -1 on a miss.
class TtlLRU {
    private record Entry(int value, long expiresAt) {}
    private final int capacity;  private final long ttl;  private final LongSupplier clock;
    private final LinkedHashMap<Integer, Entry> map;
    TtlLRU(int capacity, long ttl, LongSupplier clock) {
        this.capacity = capacity;  this.ttl = ttl;  this.clock = clock;
        map = new LinkedHashMap<>(16, 0.75f, true) {
            protected boolean removeEldestEntry(Map.Entry<Integer, Entry> e) { return size() > TtlLRU.this.capacity; }
        };
    }
    synchronized int get(int key) {
        Entry e = map.get(key);
        if (e == null) return -1;
        if (clock.getAsLong() >= e.expiresAt()) { map.remove(key);  return -1; }   // expired = a miss
        return e.value();
    }
    synchronized void put(int key, int value) { map.put(key, new Entry(value, clock.getAsLong() + ttl)); }
    synchronized Set<Integer> keys() { return map.keySet(); }
}
public class Main {
    public static void main(String[] args) {
        long[] now = {0};
        TtlLRU c = new TtlLRU(2, 10, () -> now[0]);
        c.put(1, 100);  c.put(2, 200);
        System.out.println("get(1) = " + c.get(1));
        c.put(3, 300);                                   // evicts 2, the least recently used
        System.out.println("get(2) = " + c.get(2) + ", keys " + c.keys());
        now[0] = 10;
        System.out.println("at t=10: get(1) = " + c.get(1) + ", keys " + c.keys());
    }
}

Real output:

get(1) = 100
get(2) = -1, keys [1, 3]
at t=10: get(1) = -1, keys [3]

An expired entry is removed and counted as a miss. The clock is a LongSupplier, so the test moves time by hand instead of sleeping.

3. Make LRUCache thread-safe with synchronized.

Answer

Mark get, put and size synchronized (the mini project does). Real output with 4 threads: 4 threads: size 100 (capacity 100).

4. In the list version, why is order.remove(0) also O(n)?

Answer

An ArrayList keeps its items in one block of memory; removing index 0 shifts every other item one place left. That's why our step counter adds order.size() there.

Quick quiz

LRU cache, capacity 2: put(1) put(2) get(1) put(3) put(4). Which keys are left? (a) [1, 4] (b) [3, 4] (c) [2, 4] (d) [1, 3]

Answer

(b) [3, 4]. After get(1), 2 is the least recent, so put(3) evicts 2; then 1 is the least recent, so put(4) evicts 1. Real LinkedHashMap run:

[3, 4]

Interview questions

  1. Design an LRU cache with O(1) get and put. HashMap from key to node + doubly linked list ordered by recency; get = lookup + move to front; put = insert at front, evicting tail.prev when full.
  2. Why a doubly linked list and not a singly linked one? To unlink a node in O(1) you need its previous node; a singly linked list would have to walk to find it.
  3. Why store the key inside the node? When you evict tail.prev, you must also remove it from the map, and the map needs the key.
  4. What are sentinel nodes for? Dummy head and tail so that every real node has neighbours: no null checks at the ends, and the LRU is always tail.prev.
  5. How does LinkedHashMap give you LRU? accessOrder = true keeps access order; override removeEldestEntry to return size() > capacity.
  6. Is LinkedHashMap thread-safe? No. Wrap it with Collections.synchronizedMap or lock both get and put; a read lock on get is not enough because get reorders.
  7. What is the eviction policy, and name others. The rule for who leaves: LRU, FIFO, LFU, random, TTL-based.
  8. When does LRU do badly? A one-time scan of many items pushes out the hot ones (next episode).
  9. How do you measure a cache? Hit rate, plus evictions and load time saved.
  10. What's the time and space complexity? O(1) per operation, O(capacity) space.

Glossary

Term Meaning, with an example
Cache A small, fast store of copies of slow data: profiles in memory in front of a database
Hit The item is in the cache: get(7) finds it
Miss The item isn't: go to the database, then keep a copy
Hit rate hits ÷ (hits + misses): 5 of 11 = 45.5%
Capacity The most items the cache may hold: 3
Evict Remove an item to make room
Eviction policy The rule that picks who leaves: FIFO, LRU, LFU
FIFO First in, first out: evict the oldest put, even if it's hot
LRU Least recently used: evict the item untouched longest
Most recently used The key touched last: it goes to the front
Big-O How work grows with n: O(n) grows with the size, O(1) doesn't
O(1) get and put Each call costs the same small work at any size
Doubly linked list Nodes that know both their previous and next node
Node One link in a list: key, val, prev, next
HashMap plus doubly linked list The map finds a key's node in O(1); the list keeps recency order
Sentinel nodes Dummy head and tail nodes with no data, so there are no null checks
unlink / addFront Remove a node by joining its neighbours / insert right after head
Generic cache interface interface Cache<K, V>: works for any key and value types
Type parameter A placeholder type like K filled in later: Cache<Integer, String>
LinkedHashMap A HashMap with a linked list inside that remembers an order
Load factor How full the table gets before it grows: 0.75
LinkedHashMap with accessOrder accessOrder = true orders by last access (LRU); false by insertion
removeEldestEntry Called after every put with the eldest entry; return true to remove it
Thread One path of work; servers run many at once
Race condition Two threads change shared data at once and the result is wrong
Thread-safe LRU An LRU that stays correct under many threads: one lock for get and put
synchronized Only one thread at a time may run the method or block
Collections.synchronizedMap Wraps a map so every call is synchronized
ReadWriteLock Many readers or one writer at a time; wrong for LRU's get
Shards Splitting one cache into several, each with its own lock
TTL Time to live: an entry expires after a set time
Cache-aside The caller checks the cache, else loads from the source and stores it

Summary

  • A cache keeps fast copies; a hit is fast, a miss goes to the slow source; capacity limits it.
  • No limit: memory grows forever. FIFO evicted the hot user first.
  • LRU evicts the least recently used; with a list it was correct but O(n) (1.87 billion steps).
  • HashMap + doubly linked list + sentinel nodes: O(1) get and put, behind a generic Cache<K, V>.
  • LinkedHashMap: accessOrder = true + removeEldestEntry is an LRU in a few lines.
  • Thread-safe: one lock around get and put, because get changes the order.

Next episode: Design an LFU cache and a pluggable cache library: frequency counts, swappable eviction policies, write-through, write-back, TTL and statistics.