跳至主要內容

算法就像搭乐高：带你手撸 LRU 算法

labuladong原创链表设计约 7800 字

146. LRU 缓存 https://leetcode.cn/problems/lru-cache

146. LRU Cache https://leetcode.com/problems/lru-cache

剑指 Offer II 031. 最近最少使用缓存 https://leetcode.cn/problems/OrIXps

剑指 Offer II 031. 最近最少使用缓存 https://leetcode.com/problems/OrIXps

Info

已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCodeDifficulty
146. LRU Cache🟠

Prerequisites

Before reading this article, you need to learn:

The LRU algorithm is a cache eviction strategy. While its principle is not difficult, writing bug-free code in an interview requires some技巧. It involves layering and breaking down data structures. This article will guide you to write elegant code.

Computer caches have limited capacity. When the cache is full, some content must be deleted to make room for new data. But which content should be deleted? We want to remove less useful cache data and keep useful data for future use. So, what data do we consider "useful"?

The LRU cache eviction algorithm is a common strategy. LRU stands for Least Recently Used, meaning we consider recently used data as "useful" and data that hasn't been used for a long time as "useless." When memory is full, we prioritize deleting the least recently used data.

For a simple example, Android phones can run apps in the background. Suppose I open "Settings," "Phone Manager," and "Calendar" in sequence. Their order in the background would be:

But if I access the "Settings" screen, "Settings" will move to the front, like this:

Assume my phone only allows three apps to run simultaneously, and it's already full. If I open a new app, "Clock," I must close one app to make room. Which one should I close?

According to the LRU strategy, I would close "Phone Manager" at the bottom because it's the least recently used, and then place the new app at the top:

Now you should understand the LRU (Least Recently Used) strategy. There are other cache eviction strategies, such as evicting based on access frequency (LFU strategy) rather than access order, each with its own use cases. This article explains the LRU algorithm strategy. I will cover the LFU algorithm in LFU Algorithm Explained.

I. LRU Algorithm Description

LeetCode problem 146, "LRU Cache," asks you to design a data structure:

First, you need to accept a capacity parameter as the maximum size of the cache. Then, implement two APIs: the put(key, val) method to store key-value pairs, and the get(key) method to retrieve the val corresponding to key. If the key does not exist, return -1.

Note that both the get and put methods must have an O(1) time complexity. Let's look at a specific example to see how the LRU algorithm works.

java 🟢
// the cache capacity is 2
LRUCache cache = new LRUCache(2);
// you can understand the cache as a queue
// assume the left side is the head of the queue and the right side is the tail
// the most recently used is at the head of the queue, and the least recently used is at the tail
// parentheses represent the key-value pair (key, val)

cache.put(1, 1);
// cache = [(1, 1)]

cache.put(2, 2);
// cache = [(2, 2), (1, 1)]

// return 1
cache.get(1);
// cache = [(1, 1), (2, 2)]
// explanation: because key 1 was recently accessed, it is moved to the head of the queue
// return the value corresponding to key 1, which is 1

cache.put(3, 3);
// cache = [(3, 3), (1, 1)]
// explanation: the cache is full, need to delete content to make space
// prefer to delete the least recently used data, which is the data at the tail
// then insert the new data at the head of the queue

// return -1 (not found)
cache.get(2);
// cache = [(3, 3), (1, 1)]
// explanation: there is no data with key 2 in the cache

cache.put(1, 4);    
// cache = [(1, 4), (3, 3)]
// explanation: key 1 already exists, overwrite the original value 1 with 4
// don't forget to also move the key-value pair to the head of the queue

II. LRU Algorithm Design

Analyzing the above operation process, to ensure that the put and get methods have a time complexity of O(1), we can summarize the necessary conditions for the cache data structure:

  1. Obviously, the elements in the cache must have an order to distinguish between recently used and least recently used data. When the capacity is full, the least recently used element must be removed to make space.

  2. We need to quickly find if a key already exists in the cache and get the corresponding val.

  3. Each time a key in the cache is accessed, this element needs to be marked as the most recently used. This means the cache must support quick insertion and deletion of elements at any position.

So, what data structure meets all these conditions? A hash table has fast lookup but no fixed order; a linked list has order and fast insertion/deletion but slow lookup. Combining these, we form a new data structure: a hash-linked list, LinkedHashMap.

The core data structure of the LRU cache algorithm is the hash-linked list, a combination of a doubly linked list and a hash table. This data structure looks like this:

With this structure, let's analyze the three conditions mentioned above one by one:

  1. If we always add elements to the end of the list by default, then obviously, the elements closer to the tail are the most recently used, and those closer to the head are the least recently used.

  2. For a specific key, we can quickly locate the corresponding node in the list through the hash table, thus obtaining the corresponding val.

  3. Linked lists inherently support quick insertion and deletion at any position by simply adjusting pointers. However, traditional linked lists cannot quickly access an element at a specific index. Here, with the help of the hash table, we can quickly map a key to any node in the linked list and then perform insertion or deletion.

Readers might wonder, why do we need a doubly linked list? Wouldn't a singly linked list suffice? Also, since the hash table already stores the key, why do we need to store both key and val in the linked list? Wouldn't storing just val be enough?

Questions arise in thought, but answers come through action. The reasons for this design will only become clear once we implement the LRU algorithm ourselves. So, let's dive into the code~

III. Code Implementation

Many programming languages have built-in hash-linked lists or library functions similar to LRU functionality. However, to help everyone understand the details of the algorithm, we will first implement the LRU algorithm from scratch and then use Java's built-in LinkedHashMap for another implementation.

First, let's define the node class for the doubly linked list. For simplicity, we'll consider both key and val as int types:

java 🟢
class Node {
    public int key, val;
    public Node next, prev;
    public Node(int k, int v) {
        this.key = k;
        this.val = v;
    }
}

Next, we use our Node type to build a doubly linked list and implement several essential APIs for the LRU algorithm:

java 🟢
class DoubleList {  
    // virtual head and tail nodes
    private Node head, tail;  
    // number of elements in the linked list
    private int size;
    
    public DoubleList() {
        // initialize the data of the doubly linked list
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
        size = 0;
    }

    // add node x to the end of the list, time O(1)
    public void addLast(Node x) {
        x.prev = tail.prev;
        x.next = tail;
        tail.prev.next = x;
        tail.prev = x;
        size++;
    }

    // remove node x from the list (x is guaranteed to exist)
    // since it's a doubly linked list and the target Node is given, time O(1)
    public void remove(Node x) {
        x.prev.next = x.next;
        x.next.prev = x.prev;
        size--;
    }
    
    // remove the first node from the list and return it, time O(1)
    public Node removeFirst() {
        if (head.next == tail)
            return null;
        Node first = head.next;
        remove(first);
        return first;
    }

    // return the length of the list, time O(1)
    public int size() { return size; }

}

If you are not familiar with linked list operations, you can refer to the previous article Step-by-Step Guide to Implementing a Doubly Linked List.

Now we can answer the earlier question, "Why must we use a doubly linked list?" It's because we need deletion operations. To delete a node, we not only need a pointer to the node itself but also need to manipulate the pointer of its predecessor node. Only a doubly linked list allows direct access to the predecessor, ensuring the operation has a time complexity of O(1).

重要

Note that the doubly linked list API we implemented only allows insertion from the tail. This means the data near the tail is the most recently used, and the data near the head is the least recently used.

With the implementation of the doubly linked list, we just need to combine it with a hash table in the LRU algorithm. Let's start by setting up the code framework:

java 🟢
class LRUCache {
    // key -> Node(key, val)
    private HashMap<Integer, Node> map;
    // Node(k1, v1) <-> Node(k2, v2)...
    private DoubleList cache;
    // maximum capacity
    private int cap;
    
    public LRUCache(int capacity) {
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }
}

Let's not rush into implementing the get and put methods for the LRU algorithm. Since we need to maintain both a doubly linked list cache and a hash table map, it's easy to miss some operations. For example, when deleting a key, you might remove the corresponding Node in cache but forget to delete the key in map.

An effective way to solve this problem is to provide an abstract API layer on top of these two data structures.

This might sound a bit mystical, but it's actually quite simple. The goal is to make the main LRU methods get and put avoid directly handling the details of map and cache. We can start by implementing the following functions:

java 🟢
class LRUCache {
    // To save space, the previous code part is omitted...

    // promote a key to the most recently used
    private void makeRecently(int key) {
        Node x = map.get(key);
        // first remove this node from the linked list
        cache.remove(x);
        // reinsert it at the end of the queue
        cache.addLast(x);
    }

    // add the most recently used element
    private void addRecently(int key, int val) {
        Node x = new Node(key, val);
        // the tail of the linked list is the most recently used element
        cache.addLast(x);
        // don't forget to add the key mapping in the map
        map.put(key, x);
    }

    // delete a certain key
    private void deleteKey(int key) {
        Node x = map.get(key);
        // remove from the linked list
        cache.remove(x);
        // delete from the map
        map.remove(key);
    }

    // remove the least recently used element
    private void removeLeastRecently() {
        // the first element in the linked list is the least recently used
        Node deletedNode = cache.removeFirst();
        // also, don't forget to remove its key from the map
        int deletedKey = deletedNode.key;
        map.remove(deletedKey);
    }
}

Here we can answer the previous question: "Why do we need to store both key and val in a linked list instead of just val?" Note in the removeLeastRecently function, we need to use deletedNode to get deletedKey.

In other words, when the cache capacity is full, we not only need to delete the last Node in the list, but also need to remove the corresponding key from the map. This key can only be obtained from the Node. If the Node structure only stores val, we would not know what the key is, and we would not be able to remove the key from the map, leading to errors.

The above method is a simple operation encapsulation. Calling these functions avoids direct manipulation of the cache linked list and map hash table. Next, I will implement the get method for the LRU algorithm:

java 🟢
class LRUCache {
    // To save space, the previous code is omitted...

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        // promote the data to the most recently used
        makeRecently(key);
        return map.get(key).val;
    }
}

The put method is a bit more complex, so let's start by drawing a diagram to clarify its logic:

With this, we can easily write the code for the put method:

java 🟢
class LRUCache {
    // To save space, the previous given code part is omitted...
    
    public void put(int key, int val) {
        if (map.containsKey(key)) {
            // delete the old data
            deleteKey(key);
            // the newly inserted data is the most recently used data
            addRecently(key, val);
            return;
        }
        
        if (cap == cache.size()) {
            // remove the least recently used element
            removeLeastRecently();
        }
        // add as the most recently used element
        addRecently(key, val);
    }
}

至此，你应该已经完全掌握 LRU 算法的原理和实现了。看下完整的实现：

我们最后用 Java 的内置类型 LinkedHashMap 来实现 LRU 算法，逻辑和之前完全一致：

class LRUCache {
    int cap;
    LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
    public LRUCache(int capacity) { 
        this.cap = capacity;
    }
    
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        // make the key recently used
        makeRecently(key);
        return cache.get(key);
    }
    
    public void put(int key, int val) {
        if (cache.containsKey(key)) {
            // modify the value of the key
            cache.put(key, val);
            // make the key recently used
            makeRecently(key);
            return;
        }
        
        if (cache.size() >= this.cap) {
            // the head of the list is the least recently used key
            int oldestKey = cache.keySet().iterator().next();
            cache.remove(oldestKey);
        }
        // add the new key to the end of the list
        cache.put(key, val);
    }
    
    private void makeRecently(int key) {
        int val = cache.get(key);
        // remove the key and re-insert it at the end
        cache.remove(key);
        cache.put(key, val);
    }
}

For other languages, you can search to see if there is a data structure like LinkedHashMap. Generally, in interviews, you don't need to write a doubly linked list from scratch; you can directly use built-in data structures to implement the LRU algorithm.

With this, the LRU algorithm is no longer mysterious. For more problems related to data structure design, see Classic Exercises on Data Structure Design.

引用本文的题目

安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路：

LeetCode力扣
-剑指 Offer II 031. 最近最少使用缓存
上次编辑于: