一、什么是 LRU 缓存

LRU（Least Recently Used）缓存是一种缓存淘汰策略，用于在缓存容量有限的情况下，决定哪些数据需要被移除。其核心思想是：

• 最近最少使用：当缓存满了，需要移除最久未被使用的数据，以给新的数据腾出空间。

二、LRU 缓存的实现原理

为了实现 LRU 缓存，需要满足以下两个要求：

1. 快速访问缓存中的数据：需要在 O(1) 的时间复杂度内查找和更新缓存中的数据。
2. 维护数据的使用顺序：需要按照数据被访问的先后顺序来更新缓存。

为此，通常使用 哈希表（HashMap） 和 双向链表（Doubly Linked List） 的组合来实现：

• 哈希表：用于在 O(1) 时间内快速查找缓存中的数据。
• 双向链表：用于按访问顺序记录数据，从而在 O(1) 时间内完成插入和删除操作。

三、哈希表与双向链表的组合实现

1. 数据结构设计

• 哈希表（Map<K, Node>）：

  • Key：缓存数据的键。
  • Value：链表节点的引用（Node）。

• 双向链表：

  • 头节点（Head）：最近使用的节点。
  • 尾节点（Tail）：最久未使用的节点。

2. 操作流程

• 访问数据（Get 操作）：

  1. 在哈希表中查找数据：
     • 如果存在：
       • 将对应的节点移动到链表的头部（表示最近使用）。
       • 返回节点的值。
     • 如果不存在：
       • 返回 -1 或表示未找到。

• 添加/更新数据（Put 操作）：

  1. 在哈希表中查找数据：
     • 如果存在：
       • 更新节点的值。
       • 将节点移动到链表的头部。
     • 如果不存在：
       • 如果缓存已满：
         • 移除链表尾部的节点（最久未使用的节点）。
         • 从哈希表中删除对应的键。
       • 创建新节点，添加到链表头部。
       • 在哈希表中添加键和节点的映射。

3. 关键点

• 双向链表：

  • 之所以使用双向链表，是因为在删除节点时，需要在 O(1) 时间内完成。单向链表无法在 O(1) 时间内获取前驱节点。

• 哈希表与链表的结合：

  • 哈希表用于快速定位节点。
  • 链表用于维护节点的使用顺序。

四、底层实现原理-相对于源代码

import java.util.HashMap;
import java.util.Map;

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

    private Map<Integer, Node> cache = new HashMap<>();
    private int size;
    private int capacity;
    private Node head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 初始化双向链表的头尾节点
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }

    // 获取数据
    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) {
            return -1; // 未找到
        }
        // 移动节点到头部
        moveToHead(node);
        return node.value;
    }

    // 添加或更新数据
    public void put(int key, int value) {
        Node node = cache.get(key);
        if (node == null) {
            // 创建新节点
            Node newNode = new Node(key, value);
            // 添加到哈希表
            cache.put(key, newNode);
            // 添加到链表头部
            addToHead(newNode);
            size++;
            if (size > capacity) {
                // 移除尾节点
                Node tail = removeTail();
                // 从哈希表中删除
                cache.remove(tail.key);
                size--;
            }
        } else {
            // 更新值
            node.value = value;
            // 移动到头部
            moveToHead(node);
        }
    }

    // 辅助方法：添加节点到头部
    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    // 辅助方法：移除节点
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // 辅助方法：移动节点到头部
    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    // 辅助方法：移除尾节点
    private Node removeTail() {
        Node res = tail.prev;
        removeNode(res);
        return res;
    }
}

五、Demo Code

直接使用

public class Main {
    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2); // 缓存容量为 2
        lruCache.put(1, 1); // 缓存为 {(1,1)}
        lruCache.put(2, 2); // 缓存为 {(2,2),(1,1)}
        System.out.println(lruCache.get(1)); // 返回 1，缓存为 {(1,1),(2,2)}
        lruCache.put(3, 3); // 缓存已满，移除最久未使用的键 2，缓存为 {(3,3),(1,1)}
        System.out.println(lruCache.get(2)); // 返回 -1（未找到）
        lruCache.put(4, 4); // 缓存已满，移除键 1，缓存为 {(4,4),(3,3)}
        System.out.println(lruCache.get(1)); // 返回 -1（未找到）
        System.out.println(lruCache.get(3)); // 返回 3
        System.out.println(lruCache.get(4)); // 返回 4
    }
}

六、常见的 LRU 缓存应用场景

LRU（Least Recently Used，最近最少使用）缓存是一种策略，用于在存储空间有限的情况下，优先保留最近使用过的数据，移除长时间未使用的数据。下面是几个日常生活中常见的应用场景

1. 网页浏览器缓存

   • 场景：当你浏览网页时，浏览器会存储（缓存）你访问过的网页内容，如图片、样式等。
   • 作用：下次访问相同网站时，加载速度更快，因为浏览器可以直接使用缓存的数据。
   • LRU 应用：浏览器的缓存空间有限，当缓存满了，浏览器会删除最久未访问的网站缓存，腾出空间给新的网页。

2. 手机应用的数据缓存

   • 场景：许多手机应用（如新闻、社交媒体）会缓存你浏览过的内容。
   • 作用：提高应用的响应速度，节省流量。
   • LRU 应用：当缓存空间不足时，应用会删除你长时间未查看的内容，优先保留最近浏览的内容。

3. 操作系统的内存管理

   • 场景：计算机的内存（RAM）容量有限，无法同时容纳所有正在运行的程序和数据。
   • 作用：操作系统需要在内存和硬盘之间调度数据，以保证系统的流畅运行。
   • LRU 应用：操作系统会将长时间未使用的数据从内存移到硬盘（称为虚拟内存），当需要腾出空间时，优先保留最近使用的数据。

4. 智能手机的后台应用管理

   • 场景：手机同时运行多个应用，但内存有限，无法全部保留在后台。
   • 作用：保证前台应用的流畅运行。
   • LRU 应用：系统会根据应用的最近使用情况，关闭长时间未使用的后台应用，释放内存资源。

LRU 缓存在各种设备和应用中帮助管理有限的资源，确保系统高效运行，同时提升用户体验。

总结

• LRU 缓存通过哈希表和双向链表的组合，实现了在 O(1) 时间复杂度内完成数据的读取和更新，同时维护了数据的使用顺序。
• 哈希表用于快速定位节点，双向链表用于记录节点的使用顺序，实现快速的插入和删除操作。
• 这种设计在实际工程中非常常见，适用于需要缓存最近使用数据的场景，如数据库缓存、内存管理等。