cf.completefrontend
ADVANCED DATA STRUCTURES · CORE

LRU cache

A fixed-size cache that, when full, throws out the item that was used least recently, with every operation in O(1).

Time O(1) per get or putSpace O(capacity)4 practice problemsStep-through picture

The idea

A cache keeps a limited number of recent results so they don't have to be computed or fetched again. When it is full and a new item arrives, something must go. A least recently used (LRU) cache removes the item that hasn't been read or written for the longest time, on the bet that it is the least likely to be needed soon.

The cache needs two things at once: find an item by key quickly, and know the order in which items were last used. A hash map gives the first. A list ordered from least to most recently used gives the second: every time an item is used, it moves to the most recent end, and evictions take from the other end.

In JavaScript, a Map already remembers insertion order, so deleting a key and setting it again moves it to the end. That makes a short and correct LRU cache. In other languages, the classic build is a hash map from key to node plus a doubly linked list of nodes.

An everyday example

A small desk with a stack of folders

You can keep only three folders on your desk. Whenever you use a folder, you put it on top of the pile. When you need a fourth folder, there is no room, so you send the folder at the bottom of the pile, the one you haven't touched for the longest time, back to the filing cabinet.

How the example maps to the code
In the exampleIn the code
The folders on the deskthe entries in this.map
How many folders fitthis.capacity
Putting a used folder on topthis.map.delete(key); this.map.set(key, value)
The folder at the bottomthis.map.keys().next().value
Sending it back to the cabinetthis.map.delete(oldest)

From the slow way to lru cache

  1. A first try: keep the cached entries in an array, ordered from least to most recently used. Using an entry means finding it with indexOf, cutting it out with splice, and pushing it on the end. Evicting means shift. It works, but every one of those steps can walk the whole array, so each get and put costs up to capacity steps.
  2. Another try: a hash map from key to value plus a "last used" time for each key. Lookups are now one step, but finding the oldest entry to evict means scanning every time stamp. The cache needs two things at once: find any key in one step, and know which key is oldest in one step, even as keys keep changing places.
  3. The classic answer joins two structures. A doubly linked list, where each node knows the node before and after it, keeps keys in use order: any node can be unlinked in one step and moved to the newest end, and the oldest key is always at the other end. A hash map from key to node finds any node in one step. Together, every operation is O(1).
  4. In JavaScript, a Map already does both jobs. It finds keys in one step, and it remembers the order in which keys were inserted. Deleting a key and setting it again moves it to the end, and keys().next().value reads the first, oldest key. So get moves a key to the end, and put moves or adds it, then evicts the first key if the map is too big. That is an LRU cache.

How it works

  1. Store capacity and an empty Map. The Map's order is the use order: first key is least recent, last key is most recent.
  2. get(key): if the key is missing, return -1.
  3. Otherwise read the value, delete the key, and set it again, which moves it to the most recent end. Return the value.
  4. put(key, value): if the key exists, delete it first, then set it, so it becomes the most recent.
  5. If the map now has more than capacity entries, find the first key, this.map.keys().next().value, and delete it.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. class LRUCache {
  2. constructor(capacity) {
  3. this.capacity = capacity;
  4. this.map = new Map();
  5. }
  7. get(key) {
  8. if (!this.map.has(key)) return -1;
  9. const value = this.map.get(key);
  10. this.map.delete(key);
  11. this.map.set(key, value);
  12. return value;
  13. }
  15. put(key, value) {
  16. if (this.map.has(key)) this.map.delete(key);
  17. this.map.set(key, value);
  18. if (this.map.size > this.capacity) {
  19. const oldest = this.map.keys().next().value;
  20. this.map.delete(oldest);
  21. }
  22. }
  23. }

How fast it is

TimeO(1) per get or put
Extra memoryO(capacity)

Every step is a Map operation, which is constant time on average. The map never holds more than capacity entries after a put.

  • Best caseO(1)

    A get for a missing key: one has call, then return -1.

  • Average caseO(1)

    Any get or put: a few Map operations, each constant time on average because a Map is a hash table.

  • Worst caseO(1)

    A put of a new key into a full cache: has, set, a size check, keys().next(), and delete. That's still a fixed number of steps, whatever the capacity.

Common mistakes

  • Forgetting that get must also move the key to the most recent end, so a frequently read item gets evicted.
  • Updating an existing key with set alone. A Map keeps the old position for an existing key, so the key doesn't become most recent. Delete it first.
  • Evicting before inserting, or evicting when the key already existed, which throws out an item even though the size didn't grow.
  • Using an array and indexOf / splice to track order, which makes every operation O(n).

When to use it

Look for these clues in a problem:

  • The task asks you to design a cache with a capacity and get / put operations.
  • When full, the item to remove is the one used least recently.
  • Both operations must be O(1).
  • Recently used things should be cheap to reach again: open tabs, decoded images, fetched pages.

Check yourself

Answer each one in your head first, then open it.

In the trace, why is cart evicted at put("help", 4) and not home, which was written first?

get("home") moved home to the newest end. Eviction looks at the last use, not the first write, and cart hadn't been used since it was written.

What goes wrong if put("shop", 30) only calls set, without the delete?

A Map keeps an existing key in its old place, so shop stays first in line. The next put("blog", 5) would then evict shop, the key that was just written, instead of home.

How many keys can the map hold during a put?

capacity + 1, for a moment: the new key is set first, then the oldest key is deleted. After the call returns it holds at most capacity.

Why doesn't a get miss change the order?

The key isn't in the cache, so there is nothing to move, and no stored key was used.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 4 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The cache keeps two promises. First, the Map's key order is the order of last use, oldest first. Second, after every put returns, the map holds at most capacity keys. Both are true for an empty cache.

Each operation keeps the first promise. A get hit deletes and re-sets its key, so that key moves to the end, and it is now the most recently used. Every other key keeps its place, and their order of last use didn't change either. A get miss changes nothing, and no key was used. A put deletes the key if it exists and sets it, so it ends up last too.

Eviction keeps the second promise and evicts the right key. A put adds at most one key, so the size can go over by at most one, and deleting one key is enough. By the first promise, the first key in the map is the one whose last use is the oldest, which is exactly the least recently used key. So the cache always holds the capacity most recently used keys.

Going deeper

3 more ideas

Why the first key is always the least recent

A Map iterates in the order keys were inserted. Every use of a key deletes it and inserts it again, so it moves to the end. A key that hasn't been used since long ago never moved, so it stays near the front. The first key is therefore the one whose last use is the oldest.

The classic build: hash map plus doubly linked list

Keep a doubly linked list with placeholder head and tail nodes, and a map from key to node. Using a key unlinks its node in O(1) (it knows both neighbors) and links it just before tail. Evicting removes head.next. This is exactly what the Map version does for you, and it is the version to know for interviews in other languages.

Cost

Map lookups, deletes, and inserts are O(1) on average, and reading the first key from the iterator is O(1). So get and put are O(1). The cache holds at most capacity entries: O(capacity) space.

Work it by hand

Every step in a table, with why

A cache for 3 pages, with a mix of reads, writes, a rewrite of an existing key, and misses. Each row is one call.

capacity = 3

StepCallReturnsmap keys, oldest firstEvictedWhy
1put("home", 1)-home-The first entry. The map has 1 key, well under the capacity.
2put("cart", 2)-home, cart-New keys go on the newest end.
3put("shop", 3)-home, cart, shop-The cache is now full, but not over capacity, so nothing is evicted.
4get("home")1cart, shop, home-A hit. Reading counts as using, so home is deleted and set again, which moves it to the newest end.
5put("help", 4)-shop, home, helpcartThe size becomes 4, over the capacity of 3. The first key is cart, untouched since it was written, so it goes. home survived because of the get.
6get("cart")-1shop, home, help-A miss: cart was evicted. A miss changes nothing.
7put("shop", 30)-home, help, shop-shop already exists, so it is deleted first and set with the new value 30, moving it to the newest end. The size stays 3, so nothing is evicted.
8put("blog", 5)-help, shop, bloghomeOver capacity again. home is now the oldest, since its last use was the get four calls ago.
9get("home")-1help, shop, blog-A miss: home was just evicted.
10get("help")4shop, blog, help-A hit, so help moves to the newest end. shop would be evicted next.

Over 10 calls the cache returned 1, -1, -1, and 4 for its four reads and evicted cart and then home. The map never held more than 3 keys after a put finished, and every call took a fixed number of Map steps.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
LRU cacheO(1)O(capacity)Per get or put. In JavaScript, the Map version is short, fast, and correct.
Hash map plus doubly linked listO(1)O(capacity)Your language's map doesn't keep insertion order, or an interviewer asks you to build the order yourself.
Array kept in use orderO(capacity)O(capacity)Only for a handful of entries, where indexOf and splice are cheap and the code is easiest to read.
Map with time stamps, scan to evictO(capacity)O(capacity)Evictions are rare compared with reads, so the scan almost never runs.

Extra memory: O(capacity): the map holds at most capacity keys between calls, and capacity + 1 for a moment inside put.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for LRU cache and the other approaches, on a scale where each line up is 10 times more steps.
  • LRU cache, Hash map plus doubly linked list O(1)
  • Array kept in use order, Map with time stamps, scan to evict O(capacity)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
LRU cache111
Hash map plus doubly linked list111
Array kept in use order101,0001 million
Map with time stamps, scan to evict101,0001 million

Inputs that need care

5 tricky inputs
capacity = 0
Every put sets the key, sees the size 1 > 0, and evicts it at once, so every get returns -1. Decide whether to reject 0 in the constructor instead.
capacity = 1
Each new key evicts the previous one: after put("a", 1) and put("b", 2), get("a") returns -1 and get("b") returns 2.
A stored value of -1
get returns -1 for both the stored value and a miss, so the caller can't tell them apart. Return undefined for a miss, or offer a separate has method, if values can be -1.
Updating a key that already exists, as with put("shop", 30)
The size doesn't grow, so nothing is evicted, and the key moves to the newest end. Forgetting the delete would leave it in its old, older spot.
Object keys, such as put({ id: 1 }, "x")
A Map compares object keys by identity, so a later get({ id: 1 }) with a new object returns -1. Use a string key, such as the id or a URL.

Variations and follow-ups

Twists interviewers add

Hash map plus doubly linked list

The version for languages whose maps don't keep order. Keep placeholder head and tail nodes so there are no empty-list checks. To use a key, unlink its node from its two neighbors and link it just before tail; to evict, unlink head.next and delete its key from the map.

Expiry by time

Store a time stamp with each value. In get, if the entry is older than the allowed age, delete it and treat it as a miss. Data-fetching caches combine this with LRU, so entries are dropped either for being old or for being least used.

Capacity in bytes, not entries

When entries have different sizes, such as decoded images, keep a running total of their sizes. After a put, evict from the oldest end in a while loop until the total is under the limit, which may evict several entries at once.

Least frequently used

An LFU cache evicts the key with the fewest uses instead of the oldest use. It keeps a use count per key and a list of keys for each count, so it can still find the victim in O(1). It keeps popular keys longer but reacts slower when usage changes.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "design a cache with a capacity", get and put methods, "evict the least recently used", and "both in O(1)".
  • Say the key idea first: one structure finds keys by name, and another keeps them in order of last use. Then show that a JavaScript Map is both, and offer to build the linked-list version if they want it.
  • Test by hand: a get that saves a key from eviction (like home above), a put that updates an existing key, a miss, and capacity = 1.
  • Expect "why not an array?". Answer: moving a key to the end needs indexOf and splice, which walk the array, so each operation becomes O(capacity).
  • Expect "how would you add expiry?". Store a time stamp with each value and treat expired entries as misses in get, deleting them as you find them.

Where frontend code uses it

The same idea in real UI code
  • Browsers keep caches of decoded images, compiled code, and back/forward pages with limited memory and evict the least recently used entries; your own image or tile caches can do the same.
  • Data-fetching libraries and memoization helpers often offer an LRU option so a long session doesn't keep every response in memory forever.
  • Editors and IDEs limit the number of open tabs or cached file models and close the one not touched for the longest time.

Related algorithms