Skip to main content

Implementing LRU Cache like Building a Lego

labuladongOriginalAbout 7718 words

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

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

Note

Now all the plugins has supported English. I'm still improving the website...

This article will resolve

LeetCodeDifficulty
146. LRU Cache🟠

Prerequisite Knowledge

Before reading this article, you should first learn:

The LRU algorithm is a cache eviction strategy. Its principle is not difficult, but writing a bug-free algorithm during interviews can be tricky, requiring multiple layers of abstraction and decomposition of data structures. This article will guide you in writing elegant code.

Computer cache has limited capacity, so if the cache is full, some content must be removed to make space for new content. But the question is, what should be removed? We want to remove less useful cache items and keep the useful data in the cache for future use. How do we determine which data is "useful"?

The LRU cache eviction algorithm is a commonly used 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 less useful. When memory is full, we prefer to remove the least recently used data.

For a simple example, Android phones can run applications in the background. If I open "Settings," "Phone Manager," and "Calendar" sequentially, they are arranged in the background in this order:

However, if I then access the "Settings" interface, "Settings" will be moved to the front, like this:

Suppose my phone only allows me to run 3 applications simultaneously, and it is now full. If I open a new application "Clock," I must close one to make space for "Clock." Which one should be closed?

According to the LRU strategy, the one at the bottom, "Phone Manager," should be closed because it is the least recently used. The newly opened application is placed at the top:

Now you should understand the LRU (Least Recently Used) strategy. There are also other cache eviction strategies, such as evicting based on access frequency (LFU strategy), each with its application scenarios. This article explains the LRU algorithm strategy, and I will explain the LFU algorithm in LFU Algorithm Details.

1. Description of the LRU Algorithm

LeetCode Problem 146, "LRU Cache," requires you to design a data structure:

First, it needs to accept a capacity parameter to set the maximum capacity of the cache. Then, you must implement two APIs: a put(key, val) method to store a key-value pair, and a get(key) method to retrieve the val associated with a key. If the key does not exist, it should return -1.

Please note that both get and put methods must have a time complexity of O(1)O(1). 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 (Least Recently Used) cache algorithm is a 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 one by one:

  1. If we always add elements to the end of the list, then obviously, the elements closer to the end 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 node in the linked list using the hash table, and thus obtain the corresponding val.

  3. A linked list clearly supports fast insertion and deletion at any position by simply adjusting pointers. However, a traditional linked list cannot quickly access an element at a specific index. Here, by using a hash table, we can quickly map a key to any linked list node and then insert or delete.

Readers might ask, why use 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 it be enough to store just the val?

Questions arise when we think, but answers come when we act. The reason for this design becomes clear only after implementing the LRU algorithm ourselves, so let's start looking at the code.

3. Code Implementation

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

First, let's write the node class for the doubly linked list. For simplicity, both key and val are considered 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).

Important

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 slightly more complex, so let's first draw a diagram to clarify its logic:

This way, we can easily write the put method code:

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 🟢
// doubly linked list node
class Node {
    public int key, val;
    public Node next, prev;
    public Node(int k, int v) {
        this.key = k;
        this.val = v;
    }
}

// doubly linked list
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; }

}


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();
    }
    
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        // promote this data to the most recently used
        makeRecently(key);
        return map.get(key).val;
    }
    
    public void put(int key, int val) {
        if (map.containsKey(key)) {
            // remove the old data
            deleteKey(key);
            // the newly inserted data is the most recently used
            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);
    }
    
    private void makeRecently(int key) {
        Node x = map.get(key);
        // first remove this node from the list
        cache.remove(x);
        // reinsert it at the end of the list
        cache.addLast(x);
    }

    private void addRecently(int key, int val) {
        Node x = new Node(key, val);
        // the end of the 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);
    }

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

    private void removeLeastRecently() {
        // the first element at the head of the 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);
    }
}

我们最后用 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.

Related Problems

You can install my Chrome extension then open the link.

LeetCodeDifficulty
Last update: 12/6/2024, 11:53:39 AM
© 2019 - 2024 labuladong