Design LRU Cache

A coat check counter at a busy restaurant has 3 hooks on the wall and a line out the door. Every guest who walks in hands over a coat and gets a numbered ticket. The attendant hangs the coat on an open hook. When all 3 hooks are full and the next guest arrives, someone's coat has to come off the wall — but whose? The fair rule, the one the attendant figures out on her own after a slow Friday turns into a packed Saturday, is to bump the coat that has sat untouched the longest. The regulars who keep stopping by the counter to grab their phone out of a pocket get their coats moved to a fresh hook each time, and the coat that nobody has glanced at in an hour goes into a back closet. That counter is an LRU cache. The hooks are the capacity. The act of grabbing your phone is a get. The new guest walking up is a put. And the coat going to the back closet is an eviction.

The trick has a name from operating systems. LRU stands for "least recently used," and the rule it encodes is the laziest possible guess about the future — whatever has been touched recently will probably get touched again soon, and whatever has been ignored will probably stay ignored. Maurice Wilkes, the man who built the first stored-program computer at Cambridge in 1949, also coined the term "cache" in a 1965 paper about adding a small fast memory between the CPU and main memory. He did not invent LRU as a replacement policy — Belady, an IBM researcher, was the one who in 1966 wrote the paper that compared replacement policies and proved that LRU comes within a constant factor of the impossible-to-build optimal one. The reason every operating system, database, and CPU you have ever used relies on LRU is not that it is the smartest algorithm. It is that LRU is the smartest algorithm you can run without knowing the future.

The structure has two halves that work in lockstep. One half is the hashmap — a card catalog that lets the attendant find any coat in a single step given the ticket number. The other half is the recency tracker — a queue with two ends, where the front end is the oldest coat (the next one to get bumped) and the back end is the newest coat (the one just hung up or just touched). Every operation has to keep these two halves in sync. If a coat exists in the map, it exists in the queue, and its position in the queue tells you how recently it was used.

The fields fall out of the picture. A capacity, a hashmap from key to value, and a VecDeque that holds the keys in recency order. The reason for VecDeque instead of a regular Vec is that the attendant needs to pop the front coat in one step when an eviction happens — and Vec::remove(0) shifts every other element down, which is slow. VecDeque is a double-ended queue built on a ring buffer, and both pop_front and push_back are O(1).

struct LruCache {
    cap: usize,
    map: HashMap<char, i32>,
    order: VecDeque<char>,
}

impl LruCache {
    fn new(cap: usize) -> Self {
        Self {
            cap,
            map: HashMap::new(),
            order: VecDeque::with_capacity(cap),
        }
    }

    fn get(&mut self, k: &char) -> Option<&i32> {
        if self.map.contains_key(k) {
            self.touch(k);
            self.map.get(k)
        } else {
            None
        }
    }

    fn put(&mut self, k: char, v: i32) {
        if self.map.contains_key(&k) {
            self.map.insert(k, v);
            self.touch(&k);
            return;
        }
        if self.map.len() == self.cap {
            if let Some(old) = self.order.pop_front() {
                self.map.remove(&old);
                println!("    evict {old}");
            }
        }
        self.map.insert(k, v);
        self.order.push_back(k);
    }

    fn touch(&mut self, k: &char) {
        if let Some(pos) = self.order.iter().position(|x| x == k) {
            self.order.remove(pos);
            self.order.push_back(*k);
        }
    }
}

Read the methods top to bottom. The get method looks up the key in the map. If the key is there, it calls touch to move the key to the back of the recency queue — that key is now the most recently used — then returns the value. If the key is missing, it returns None, which is Rust's way of saying no coat under that ticket. The put method has two cases. If the key already exists, overwrite the value and touch the key so it counts as recently used. If the key is new, check whether the wall is full. If full, pop the front of the queue, remove that key from the map, and print which coat got evicted so the reader can watch the bump happen. Then insert the new pair and push the key to the back of the queue.

The touch helper does the work that gives the cache its name. It walks the queue, finds where the key sits, removes it from that spot, and pushes it to the back. That O(n) scan is the honest cost of building LRU on top of a VecDeque. The textbook O(1) version uses a doubly-linked list of nodes where each map entry stores a raw pointer to its own node, and touch becomes three pointer rewires — unlink the node, link it to the tail. The reason we did not write that here is that doubly-linked lists fight Rust's ownership rules brutally. Every node has two owners (the prev pointer and the next pointer), which forces the entire structure into Rc<RefCell<Node>> or unsafe raw pointers, and both choices make the code unreadable for a lesson. The standard library's LinkedList exists and is implemented with unsafe, and Aria Beingessner — who wrote much of Rust's collections — published a 50-page essay called Learning Rust With Entirely Too Many Linked Lists that walks through every attempt and explains why each one is harder than it looks. For a real production LRU you would either pull the lru crate, which uses unsafe under the hood, or accept the O(n) touch cost for small caches.

A small print helper renders the queue state from front to back so the reader can watch the order change after every operation.

fn show(cache: &LruCache) {
    print!("    state: front=[");
    for (i, key) in cache.order.iter().enumerate() {
        if i > 0 {
            print!(", ");
        }
        let v = cache.map.get(key).copied().unwrap_or(0);
        print!("{key}={v}");
    }
    println!("]=back");
}

The driver builds a 3-hook counter and walks through the trace from the textbook. Three coats arrive in order — a, b, c. Then a regular comes back for their coat (get a). Then a fourth guest arrives with coat d. Something has to come off the wall.

fn main() {
    let mut cache = LruCache::new(3);
    println!("cap=3, evict from front (least recent), insert at back (most recent)");
    println!();

    println!("put a=1");
    cache.put('a', 1);
    show(&cache);

    println!("put b=2");
    cache.put('b', 2);
    show(&cache);

    println!("put c=3");
    cache.put('c', 3);
    show(&cache);

    println!("get a -> {:?}", cache.get(&'a'));
    show(&cache);

    println!("put d=4");
    cache.put('d', 4);
    show(&cache);

    println!("get b -> {:?}", cache.get(&'b'));
    show(&cache);
}

cap=3, evict from front (least recent), insert at back (most recent)

put a=1
    state: front=[a=1]=back
put b=2
    state: front=[a=1, b=2]=back
put c=3
    state: front=[a=1, b=2, c=3]=back
get a -> Some(1)
    state: front=[b=2, c=3, a=1]=back
put d=4
    evict b
    state: front=[c=3, a=1, d=4]=back
get b -> None
    state: front=[c=3, a=1, d=4]=back

Walk the state lines top to bottom. After put a=1, the queue is [a=1]. After put b=2, [a=1, b=2]. After put c=3, [a=1, b=2, c=3] — the wall is full and the front of the queue is a, the oldest coat. Then comes the move that makes LRU different from a plain FIFO. The line get a -> Some(1) returns the value, and the very next state shows the queue as [b=2, c=3, a=1]. The a jumped from the front to the back. It is now the most recently used. The oldest coat is b. So when put d=4 happens on a full wall, the eviction notice prints evict b, and the new state is [c=3, a=1, d=4]. The last line — get b -> None — confirms b is gone from the map, sent to the back closet for good.

A question worth answering from the trace. Why did b get evicted instead of a, when both were put on the wall before c? Because the get on a reset its recency clock. The plain age of a coat does not matter — the LRU rule cares about the last time the attendant touched it. The attendant touched a at step 4 and never touched b after step 2, which made b the oldest by the measure that matters. A FIFO cache would have evicted a instead, and a real workload — say, a database that keeps loading the same hot rows over and over — would have thrown that row off the wall right before the next request asked for it again. LRU saves that round trip. That is the whole reason every database in the world ships LRU as its default page replacement policy.

The coat check counter has one limit. The attendant assumes that recent use predicts future use, and most of the time she is right. But a workload that walks through a giant file once, end to end, never reusing anything — a backup job, a log scan — will fill the wall with coats that will never be asked for again, push every actually-hot coat to the front of the queue, and evict the items that the rest of the system actually needs. The next lesson is about the family of replacement policies that try to fix this — FIFO, clock, working set, and the segmented variants like ARC that Megiddo and Modha invented at IBM in 2003 to keep one scan from poisoning the whole cache.