小朋友都能看懂的题解 | #设计LRU缓存结构#

LRU 缓存是什么？

想象一下，你有一个小书架，能放很多书，但空间有限。每次你读一本书时，你会把这本书放到书架的最上面。如果书架满了，你就需要把最下面的书拿走，腾出空间放新书。这就是 LRU（最近最少使用）缓存的工作方式：把最近用过的东西放在前面，不常用的放在后面。

如何实现 LRU 缓存？

1. 使用一个小书架：我们用一个叫做 HashMap 的东西来快速找到书（也就是数据）。这个书架是有限的，容量由你决定。

2. 书的排列：我们用一个双向链表来表示书架上的书。链表的头部是最近使用的书，尾部是最久未使用的书。

代码分解

1. Node 类：每本书（节点）都有一个 key（书的标识）和一个 value（书的内容），还有两个指针指向前后的书。

class Node {
    int key; // 书的标识
    int value; // 书的内容
    Node prev; // 指向前一本书
    Node next; // 指向后一本书
    
    Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

2. LRUCache 类：
   • 构造函数：初始化书架的大小和书的位置（头和尾）。

public class LRUCache {
    private final int capacity; // 书架的容量
    private final HashMap<Integer, Node> cache; // 书架，用来快速查找书
    private Node head; // 最近使用的书
    private Node tail; // 最久未使用的书

3. 添加和移除书：
   • remove：从书架上拿走一本书。
   • addToFront：把一本书放到书架的最上面。

private void remove(Node node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
}

private void addToFront(Node node) {
    node.next = head.next;
    node.prev = head;
    head.next.prev = node;
    head.next = node;
}

4. 获取书：
   • get：如果书在书架上，就把它移到最上面，并返回书的内容；如果不在，就返回 -1（表示找不到书）。

public String get(int key) {
    if (cache.containsKey(key)) {
        Node node = cache.get(key);
        remove(node);
        addToFront(node);
        return String.valueOf(node.value);
    }
    return "-1"; // 找不到书
}

5. 放书：
   • set：放一本新书。如果书已经在书架上，更新它的内容并把它移到最上面。如果书架满了，就把最下面的书拿走，再放新书。

public void set(int key, int value) {
    if (cache.containsKey(key)) {
        Node node = cache.get(key);
        node.value = value; // 更新内容
        remove(node);
        addToFront(node);
    } else {
        if (cache.size() >= capacity) {
            Node lru = tail.prev; // 最久未使用的书
            remove(lru);
            cache.remove(lru.key); // 从书架上拿走
        }
        Node newNode = new Node(key, value);
        cache.put(key, newNode); // 放新书
        addToFront(newNode);
    }
    System.out.println("null"); // 放书时的输出
}

完整代码

import java.util.HashMap;

class Node {
    int key;
    int value;
    Node prev;
    Node next;
    
    Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

public class LRUCache {
    private final int capacity;
    private final HashMap<Integer, Node> cache;
    private Node head;
    private Node tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addToFront(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    public String get(int key) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            remove(node);
            addToFront(node);
            return String.valueOf(node.value);
        }
        return "-1";
    }

    public void set(int key, int value) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            node.value = value;
            remove(node);
            addToFront(node);
        } else {
            if (cache.size() >= capacity) {
                Node lru = tail.prev;
                remove(lru);
                cache.remove(lru.key);
            }
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addToFront(newNode);
        }
        System.out.println("null");
    }
}

希望这篇文章对你有帮助👍。