All topics
80 / 101
library
advanced

LinkedHashMap & LRU Cache

Use insertion-order or access-order LinkedHashMap, and build an LRU cache with it.

A LinkedHashMap is a HashMap that also remembers the order of its entries. A plain HashMap gives you no order at all.

Insertion-order LinkedHashMap = a guest book (signatures in order of arrival). Access-order = a recently-used apps list on your phone (most recently opened moves to front).

Key Concepts

1
It does that by threading a linked list through the entries. By default the order is the order you inserted them. Turn on one setting, and it becomes the order you last used them.
2
That setting is what makes it an LRU cache.
3
LRU means "least recently used". When the cache is full, throw out whatever nobody has touched for the longest.
4
LinkedHashMap gives you this in about six lines:
LinkedHashMap
5
    new LinkedHashMap<K,V>(capacity, 0.75f, true) {
        @Override protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
            return size() > capacity;
        }
    };
6
The true is the important part: it says "order by access". Every get moves that entry to the end of the list. removeEldestEntry is asked after each insert whether the oldest should go, and returning true evicts it.
truegetremoveEldestEntry
7
The map does all the reordering. You write no list handling at all.
8
The catch: get changes the map. With access order on, reading is a modification. Two consequences follow.
get
9
The map is not safe for several threads even if they only read. And iterating while another thread reads can throw ConcurrentModificationException.
ConcurrentModificationException
10
Wrapping it in Collections.synchronizedMap makes every operation wait for every other, which for a busy cache defeats the purpose. At that point use a real cache library such as Caffeine, which locks in sections and has better eviction.
Collections.synchronizedMap
11
Interviewers often want the manual version. The structure is a hash map plus a doubly-linked list.
12
The map takes you to a node in one step. The list keeps the order, with most-recent at the head. On a get, you move that node to the head. On a put when full, you remove the node at the tail.
getput
13
Both are constant time, and the reason the list is doubly linked is that removing a node needs its predecessor. With a single-linked list you would have to walk the list to find it, making eviction O(n).
14
LRU is not always right. A job that reads every key once — a scan, a report — pushes out everything genuinely popular, because each scanned key looks "recently used".
15
For that workload you want LFU, which counts how often things are used rather than how recently. Knowing this limit is usually what separates memorising the recipe from understanding it.
16
What the interviewer is probing.1. "Implement an LRU cache." Probing: whether you know the structure. Stalls: scanning a list for the oldest. Moves up: hash map plus doubly-linked list, or LinkedHashMap with access order and removeEldestEntry.
LinkedHashMapremoveEldestEntry
17
2. "Why doubly linked?" Probing: the detail that makes it fast. Stalls: "To keep the order." Moves up: removal needs the previous node; single-linked would mean walking the list.
18
3. "How does it differ from HashMap?" Probing: mechanism and cost. Stalls: "It keeps order." Moves up: a linked list through the entries, two extra references per entry, and optional access ordering.
HashMap
19
4. "Is it thread-safe?" Probing: the access-order trap. Stalls: "Reads are fine." Moves up: with access order a get modifies the map, so concurrent reads are unsafe.
get
20
5. "When is LRU a bad choice?" Probing: beyond the recipe. Stalls: "It is standard." Moves up: a full scan evicts everything popular; LFU handles that.
21
  The JDK LRU, complete
22
    new LinkedHashMap<K,V>(capacity, 0.75f, true) {
        @Override protected boolean removeEldestEntry(
                Map.Entry<K,V> eldest) {
            return size() > capacity;
        }
    };
23
    third argument true  = access order (get moves to the end)
    third argument false = insertion order (the default)
24
  Cost comparison
25
                     HashMap        LinkedHashMap    TreeMap
  ------------------------------------------------------------------
  get / put          O(1) avg       O(1) avg         O(log n)
  Iteration          O(capacity)    O(size)          O(size)
  Order              none           insertion or     sorted by key
                                    access
  Extra memory       -              2 refs/entry     node overhead
                                    (~8 B)
26
  Manual structure, if asked to build it
27
    map:  key -> node          (O(1) lookup)
    list: head <-> ... <-> tail (head = most recent)
28
    get(k):    node = map[k]; move node to head; return node.value
    put(k,v):  if present: update + move to head
               else: insert at head; if size > cap: evict tail,
                     map.remove(tail.key)
29
    Both operations are O(1) because the map hands you the node
    directly, so no traversal is needed to find it.
Use cases:CollectionsCachingInterview Classic