14.09Beginner / Intermediate4 topics17 min4 interactive animations

Cache applications

Hash tables in caches: an LRU cache with LinkedHashMap, the same cache built from a hash map and a doubly linked list, the LFU cache idea, and memoization tables.

Learning goals

Build an LRU cache with LinkedHashMap and from scratch
Explain how an LFU cache tracks frequencies and breaks ties
Use a hash map as a memoization table

Prerequisites

Java mapsDoubly linked lists

14.09.1

LRU cache with LinkedHashMap

A cache keeps recent results so repeated requests are fast, but it has a limited size and must decide what to throw away. The **least recently used (LRU)** policy evicts the entry that has gone unused the longest, betting that recent use predicts future use.

LinkedHashMap in access-order mode is an LRU cache almost for free: every get or put moves the entry to the end of its internal list, and removeEldestEntry evicts the head when the cache is over capacity. All operations are O(1). The “Capacity 3” preset of the animation below shows the same policy step by step; with Java's class, after putting 1, 2, 3, reading 1 and putting 4 the keys are [3, 1, 4].

Java

1class LruCache<K, V> extends LinkedHashMap<K, V> {
2    private final int capacity;
3    LruCache(int capacity) { super(16, 0.75f, true); this.capacity = capacity; }   // true = access order
4    @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > capacity; }
5}

LRU cache: hash map + doubly linked list

Interactive · edit the input

most recent → least recent · 0 nodes

null

Accessed nowHitEvicted

map: key → node

empty

Setup

A cache of capacity 3. The list keeps keys from most to least recently used; the hash map finds a key's node in O(1).

Step 1 / 18

Java

1class LRUCache {
2    private final int capacity;
3    private final Map<Integer, DNode> map = new HashMap<>();      // key -> node: O(1) lookup
4    private final DNode head = new DNode(), tail = new DNode();    // head.next is the most recently used
5    boolean access(int key) {
6        DNode node = map.get(key);
7        if (node != null) { unlink(node); addFirst(node); return true; }       // hit: move to the front
8        node = new DNode(key); map.put(key, node); addFirst(node);              // miss: insert at the front
9        if (map.size() > capacity) { DNode lru = tail.prev; unlink(lru); map.remove(lru.key); }   // evict the oldest
10        return false;
11    }
12}

Live state

capacity

No condition evaluated on this step

Execution trace (dry run table)Show 18 steps

Step	Line	State	What happens
1	L4	capacity=3	A cache of capacity 3. The list keeps keys from most to least recently used; the hash map finds a key's node in O(1).
2	L8	access=1 hits=0 misses=1	Access 1: miss. Insert a new node at the front and record it in the map.
3	L8	access=2 hits=0 misses=2	Access 2: miss. Insert a new node at the front and record it in the map.
4	L8	access=3 hits=0 misses=3	Access 3: miss. Insert a new node at the front and record it in the map.
5	L7	access=1 hits=1 misses=3	Access 1: hit. Unlink its node and re-insert it at the front (O(1) because the node knows both neighbours).
6	L8	access=4 hits=1 misses=4	Access 4: miss. Insert a new node at the front and record it in the map.
7	L9	evict=2	The cache holds 4 > 3 keys: evict the least recently used, 2, from the tail and from the map.
8	L9	size=3	2 is gone.
9	L8	access=2 hits=1 misses=5	Access 2: miss. Insert a new node at the front and record it in the map.
10	L9	evict=3	The cache holds 4 > 3 keys: evict the least recently used, 3, from the tail and from the map.
11	L9	size=3	3 is gone.
12	L8	access=5 hits=1 misses=6	Access 5: miss. Insert a new node at the front and record it in the map.
13	L9	evict=1	The cache holds 4 > 3 keys: evict the least recently used, 1, from the tail and from the map.
14	L9	size=3	1 is gone.
15	L8	access=1 hits=1 misses=7	Access 1: miss. Insert a new node at the front and record it in the map.
16	L9	evict=4	The cache holds 4 > 3 keys: evict the least recently used, 4, from the tail and from the map.
17	L9	size=3	4 is gone.
18	L12	hits=1 misses=7 return=[1, 5, 2]	1 hit and 7 misses out of 8 accesses. Final order, most recent first: [1, 5, 2]. Every operation is O(1).

14.09.2

LRU with hash map + doubly list

LinkedHashMap hides the mechanism. Built by hand, an LRU cache has two parts: a hash map from key to node for O(1) lookup, and a doubly linked list ordering the nodes from most to least recently used. A hit unlinks the node and re-links it at the head; an insertion at capacity removes the tail node and its map entry. The doubly linked list is what makes unlinking an arbitrary node O(1), because it knows its own predecessor.

Use dummy head and tail nodes so no operation has to special-case an empty list. This is a favourite interview problem, and the animation draws the list and the map in step with each access.

Java

1class LRU {
2    private static class Node { int key, val; Node prev, next; }
3    private final Map<Integer, Node> map = new HashMap<>();
4    private final Node head = new Node(), tail = new Node();            // dummy sentinels
5    private final int capacity;
6    LRU(int capacity) { this.capacity = capacity; head.next = tail; tail.prev = head; }
7    private void unlink(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }
8    private void addFirst(Node n) { n.next = head.next; n.prev = head; head.next.prev = n; head.next = n; }
9    int get(int key) {
10        Node n = map.get(key);
11        if (n == null) return -1;
12        unlink(n); addFirst(n);                                          // most recently used goes to the front
13        return n.val;
14    }
15    void put(int key, int val) {
16        Node n = map.get(key);
17        if (n != null) { n.val = val; unlink(n); addFirst(n); return; }
18        if (map.size() == capacity) { Node lru = tail.prev; unlink(lru); map.remove(lru.key); }   // evict the oldest
19        n = new Node(); n.key = key; n.val = val;
20        map.put(key, n); addFirst(n);
21    }
22}

LRU cache: hash map + doubly linked list

Interactive · edit the input

most recent → least recent · 0 nodes

null

Accessed nowHitEvicted

map: key → node

empty

Setup

A cache of capacity 3. The list keeps keys from most to least recently used; the hash map finds a key's node in O(1).

Step 1 / 18

Java

1class LRUCache {
2    private final int capacity;
3    private final Map<Integer, DNode> map = new HashMap<>();      // key -> node: O(1) lookup
4    private final DNode head = new DNode(), tail = new DNode();    // head.next is the most recently used
5    boolean access(int key) {
6        DNode node = map.get(key);
7        if (node != null) { unlink(node); addFirst(node); return true; }       // hit: move to the front
8        node = new DNode(key); map.put(key, node); addFirst(node);              // miss: insert at the front
9        if (map.size() > capacity) { DNode lru = tail.prev; unlink(lru); map.remove(lru.key); }   // evict the oldest
10        return false;
11    }
12}

Live state

capacity

No condition evaluated on this step

Execution trace (dry run table)Show 18 steps

Step	Line	State	What happens
1	L4	capacity=3	A cache of capacity 3. The list keeps keys from most to least recently used; the hash map finds a key's node in O(1).
2	L8	access=1 hits=0 misses=1	Access 1: miss. Insert a new node at the front and record it in the map.
3	L8	access=2 hits=0 misses=2	Access 2: miss. Insert a new node at the front and record it in the map.
4	L8	access=3 hits=0 misses=3	Access 3: miss. Insert a new node at the front and record it in the map.
5	L7	access=1 hits=1 misses=3	Access 1: hit. Unlink its node and re-insert it at the front (O(1) because the node knows both neighbours).
6	L8	access=4 hits=1 misses=4	Access 4: miss. Insert a new node at the front and record it in the map.
7	L9	evict=2	The cache holds 4 > 3 keys: evict the least recently used, 2, from the tail and from the map.
8	L9	size=3	2 is gone.
9	L8	access=2 hits=1 misses=5	Access 2: miss. Insert a new node at the front and record it in the map.
10	L9	evict=3	The cache holds 4 > 3 keys: evict the least recently used, 3, from the tail and from the map.
11	L9	size=3	3 is gone.
12	L8	access=5 hits=1 misses=6	Access 5: miss. Insert a new node at the front and record it in the map.
13	L9	evict=1	The cache holds 4 > 3 keys: evict the least recently used, 1, from the tail and from the map.
14	L9	size=3	1 is gone.
15	L8	access=1 hits=1 misses=7	Access 1: miss. Insert a new node at the front and record it in the map.
16	L9	evict=4	The cache holds 4 > 3 keys: evict the least recently used, 4, from the tail and from the map.
17	L9	size=3	4 is gone.
18	L12	hits=1 misses=7 return=[1, 5, 2]	1 hit and 7 misses out of 8 accesses. Final order, most recent first: [1, 5, 2]. Every operation is O(1).

14.09.3

LFU cache concept

The **least frequently used (LFU)** policy evicts the key that has been used the fewest times, on the bet that popular keys stay popular. LRU forgets a hot key after a burst of one-off requests; LFU keeps it. The price is bookkeeping: counts must be kept, and a once-hot key can stay forever unless counts are aged.

To make every operation O(1), keep a map from key to its count and a map from count to a LinkedHashSet of keys with that count (oldest first), plus the current minimum count. On a hit the key moves from the set of count f to the set of f+1; if the old set was the minimum and is now empty, the minimum rises by one. On a miss with a full cache, evict the first key of the minimum-count set, which breaks ties by age. A new key always has count 1.

Java

1class LfuCache {
2    private final int capacity; private int minFreq;
3    private final Map<Integer, Integer> freq = new HashMap<>();
4    private final Map<Integer, LinkedHashSet<Integer>> byFreq = new HashMap<>();   // oldest key first
5    LfuCache(int capacity) { this.capacity = capacity; }
6    void access(int key) {
7        if (freq.containsKey(key)) { touch(key); return; }                       // hit
8        if (freq.size() == capacity) {                                            // miss on a full cache
9            int victim = byFreq.get(minFreq).iterator().next();                   // lowest frequency, oldest first
10            byFreq.get(minFreq).remove(victim); freq.remove(victim);
11        }
12        freq.put(key, 1); byFreq.computeIfAbsent(1, f -> new LinkedHashSet<>()).add(key); minFreq = 1;
13    }
14    private void touch(int key) {
15        int f = freq.get(key);
16        byFreq.get(f).remove(key);
17        if (byFreq.get(f).isEmpty() && minFreq == f) minFreq++;
18        freq.put(key, f + 1); byFreq.computeIfAbsent(f + 1, x -> new LinkedHashSet<>()).add(key);
19    }
20}

LFU cache: evict the least frequently used key

Interactive · edit the input

accesses

cache · 0 of 3 · minFreq -

∅

Setup

Every key has a use count. When the cache is full, the key with the smallest count is evicted; among equal counts the one used longest ago goes first.

Step 1 / 20

Java

1class LfuCache {
2    private final int capacity; private int minFreq;
3    private final Map<Integer, Integer> freq = new HashMap<>();
4    private final Map<Integer, LinkedHashSet<Integer>> byFreq = new HashMap<>();   // oldest key first
5    void access(int key) {
6        if (freq.containsKey(key)) { touch(key); return; }                       // hit
7        if (freq.size() == capacity) {                                            // miss on a full cache
8            int victim = byFreq.get(minFreq).iterator().next();                   // lowest frequency, oldest first
9            byFreq.get(minFreq).remove(victim); freq.remove(victim);
10        }
11        freq.put(key, 1); byFreq.computeIfAbsent(1, f -> new LinkedHashSet<>()).add(key); minFreq = 1;
12    }
13    private void touch(int key) {
14        int f = freq.get(key);
15        byFreq.get(f).remove(key);
16        if (byFreq.get(f).isEmpty() && minFreq == f) minFreq++;
17        freq.put(key, f + 1); byFreq.computeIfAbsent(f + 1, x -> new LinkedHashSet<>()).add(key);
18    }
19}

Live state

0 hits0 misses

capacity

No condition evaluated on this step

Execution trace (dry run table)Show 20 steps

Step	Line	State	What happens
1	L2	capacity=3	Every key has a use count. When the cache is full, the key with the smallest count is evicted; among equal counts the one used longest ago goes first.
2	L6	key=1 size=0 minFreq=0	Miss on 1: it is not cached.
3	L11	key=1 freq=1 minFreq=1	Insert 1 with count 1; minFreq resets to 1 because the newest key always has the lowest count.
4	L6	key=2 size=1 minFreq=1	Miss on 2: it is not cached.
5	L11	key=2 freq=1 minFreq=1	Insert 2 with count 1; minFreq resets to 1 because the newest key always has the lowest count.
6	L6	key=1 freq=1 minFreq=1	Hit on 1 (used 1 time).
7	L17	key=1 freq=2 minFreq=1	touch(1): its count moves from 1 to 2.
8	L6	key=3 size=2 minFreq=1	Miss on 3: it is not cached.
9	L11	key=3 freq=1 minFreq=1	Insert 3 with count 1; minFreq resets to 1 because the newest key always has the lowest count.
10	L6	key=1 freq=2 minFreq=1	Hit on 1 (used 2 times).
11	L17	key=1 freq=3 minFreq=1	touch(1): its count moves from 2 to 3.
12	L6	key=2 freq=1 minFreq=1	Hit on 2 (used 1 time).
13	L17	key=2 freq=2 minFreq=1	touch(2): its count moves from 1 to 2.
14	L6	key=4 size=3 minFreq=1	Miss on 4: it is not cached.
15	L8	victim=3 its freq=1	The cache is full. The lowest use count is 1; the oldest key with that count is 3, so it is evicted.
16	L11	key=4 freq=1 minFreq=1	Insert 4 with count 1; minFreq resets to 1 because the newest key always has the lowest count.
17	L6	key=3 size=3 minFreq=1	Miss on 3: it is not cached.
18	L8	victim=4 its freq=1	The cache is full. The lowest use count is 1; the oldest key with that count is 4, so it is evicted.
19	L11	key=3 freq=1 minFreq=1	Insert 3 with count 1; minFreq resets to 1 because the newest key always has the lowest count.
20	L19	hits=3 misses=5 return=[1×3, 2×2, 3×1]	3 hits, 5 misses. Cached (key×count): [1×3, 2×2, 3×1].

14.09.4

Memoization table

**Memoization** caches the results of a pure function so each distinct input is computed once. A hash map from the arguments to the answer is the usual table: look up first, and compute and store only on a miss. It turns exponential recursion such as fib(n) = fib(n-1) + fib(n-2) into a linear number of calls, because every fib(k) is computed once and answered from the table afterwards.

Use computeIfAbsent with care for recursive functions: the mapping function must not touch the same map, or Java throws ConcurrentModificationException. Check with get and store with put instead. Chapter 23 (Dynamic Programming: The Core Method) studies this in depth, where the memo table is often an array indexed by the state.

Java

1static final Map<Integer, Long> memo = new HashMap<>();
2
3static long fib(int n) {
4    if (n <= 1) return n;
5    Long cached = memo.get(n);
6    if (cached != null) return cached;                 // answered from the table
7    long result = fib(n - 1) + fib(n - 2);
8    memo.put(n, result);                               // store after the recursive calls (no computeIfAbsent here)
9    return result;
10}

Fibonacci with memoization

Interactive · edit the input

Recursion tree · 1 call

fib(6)…

Running now

Call

Call fib(6).

Step 1 / 52

Java

1static long[] memo = new long[100];
2static long fib(int n) {
3    if (n <= 1) return n;                       // base cases
4    if (memo[n] != 0) return memo[n];           // already solved: reuse it
5    return memo[n] = fib(n - 1) + fib(n - 2);   // solve once, remember
6}

Live state

1 calls

depth

No condition evaluated on this step

Call stack (top first)

fib(6)

Execution trace (dry run table)Show 52 steps

Step	Line	State	What happens
1	L2	n=6 depth=1	Call fib(6).
2	L3	n=6	Not a base case.
3	L4	n=6 memo[n]=0	memo[6] is empty, so compute it.
4	L5	n=6	fib(6) = fib(5) + fib(4). Call fib(5) first.
5	L2	n=5 depth=2	Call fib(5).
6	L3	n=5	Not a base case.
7	L4	n=5 memo[n]=0	memo[5] is empty, so compute it.
8	L5	n=5	fib(5) = fib(4) + fib(3). Call fib(4) first.
9	L2	n=4 depth=3	Call fib(4).
10	L3	n=4	Not a base case.
11	L4	n=4 memo[n]=0	memo[4] is empty, so compute it.
12	L5	n=4	fib(4) = fib(3) + fib(2). Call fib(3) first.
13	L2	n=3 depth=4	Call fib(3).
14	L3	n=3	Not a base case.
15	L4	n=3 memo[n]=0	memo[3] is empty, so compute it.
16	L5	n=3	fib(3) = fib(2) + fib(1). Call fib(2) first.
17	L2	n=2 depth=5	Call fib(2).
18	L3	n=2	Not a base case.
19	L4	n=2 memo[n]=0	memo[2] is empty, so compute it.
20	L5	n=2	fib(2) = fib(1) + fib(0). Call fib(1) first.
21	L2	n=1 depth=6	Call fib(1).
22	L3	n=1	Base case: fib(1) = 1.
23	L3	n=1 return=1	return 1.
24	L5	n=2 left=1	fib(1) = 1. Now call fib(0).
25	L2	n=0 depth=6	Call fib(0).
26	L3	n=0	Base case: fib(0) = 0.
27	L3	n=0 return=0	return 0.
28	L5	n=2 left=1 right=0 return=1	fib(2) = 1 + 0 = 1. Store it in memo[2].
29	L5	n=3 left=1	fib(2) = 1. Now call fib(1).
30	L2	n=1 depth=5	Call fib(1).
31	L3	n=1	Base case: fib(1) = 1.
32	L3	n=1 return=1	return 1.
33	L5	n=3 left=1 right=1 return=2	fib(3) = 1 + 1 = 2. Store it in memo[3].
34	L5	n=4 left=2	fib(3) = 2. Now call fib(2).
35	L2	n=2 depth=4	Call fib(2).
36	L3	n=2	Not a base case.
37	L4	n=2 memo[n]=1	memo[2] is already 1. No need to recurse again.
38	L4	n=2 return=1	Cache hit: return 1 immediately. This whole subtree is skipped.
39	L5	n=4 left=2 right=1 return=3	fib(4) = 2 + 1 = 3. Store it in memo[4].
40	L5	n=5 left=3	fib(4) = 3. Now call fib(3).
41	L2	n=3 depth=3	Call fib(3).
42	L3	n=3	Not a base case.
43	L4	n=3 memo[n]=2	memo[3] is already 2. No need to recurse again.
44	L4	n=3 return=2	Cache hit: return 2 immediately. This whole subtree is skipped.
45	L5	n=5 left=3 right=2 return=5	fib(5) = 3 + 2 = 5. Store it in memo[5].
46	L5	n=6 left=5	fib(5) = 5. Now call fib(4).
47	L2	n=4 depth=2	Call fib(4).
48	L3	n=4	Not a base case.
49	L4	n=4 memo[n]=3	memo[4] is already 3. No need to recurse again.
50	L4	n=4 return=3	Cache hit: return 3 immediately. This whole subtree is skipped.
51	L5	n=6 left=5 right=3 return=8	fib(6) = 5 + 3 = 8. Store it in memo[6].
52	L5	return=8	fib(6) = 8 with 11 calls. Plain recursion would need 25 calls.

Practice ladder

Now try it yourself

Easy

Design HashMap
Climbing Stairs (memoised)

Medium

LRU Cache
Design Browser History

Advanced

LFU Cache
All O`one Data Structure

Key takeaways

LinkedHashMap with accessOrder = true and removeEldestEntry is an LRU cache in a few lines.
A hand-built LRU is a hash map to nodes plus a doubly linked list, all O(1).
LFU adds counts and per-count lists; memoization is a hash map from arguments to results.