一、缓存淘汰算法：从 LRU 到 LFU

缓存这东西，说白了就是用空间换时间。你想想看，CPU 要读数据，如果每次都去磁盘翻，那速度慢得让人抓狂。所以我们在内存里划一块区域，把常用的数据先存着。但内存也不是无限的，满了怎么办？就得把一些「不太重要」的数据踢出去。

那问题来了：怎么定义「不太重要」？这就引出了两种经典策略——LRU 和 LFU。

1.1 LRU：最近最少使用

LRU 的全称是 Least Recently Used。它的核心思想很简单：如果数据最近被访问过，那么将来被访问的概率也更高。说白了，就是淘汰那些「很久没人碰」的数据。

我刚开始做缓存系统时，觉得 LRU 不就是个队列嘛，先进先出不就完了？后来才发现，这玩意儿比我想象的复杂。因为 LRU 不仅要记录「谁先来」，还要记录「谁被访问了」——每次访问都要把数据挪到最前面。

1.2 LFU：最不经常使用

LFU 的全称是 Least Frequently Used。它看的是「使用频率」——淘汰那些被访问次数最少的数据。你可能会问：那 LRU 和 LFU 到底选哪个？

嗯，这里有个坑。我记得有一次在项目中做热点数据缓存，用了 LRU。结果有个定时任务每隔几分钟扫一次全表，把缓存里的热点数据全给挤出去了。换成 LFU 之后，情况就好多了——因为热点数据访问次数高，不会被低频的扫描任务冲掉。

但 LFU 也有自己的问题：频率衰减。如果一个数据曾经很热，后来凉了，它的访问次数还很高，就会一直占着位置不走。所以实际工程中，往往会给 LFU 加一个时间窗口，或者定期衰减计数。

二、经典例题：实现 LRUCache

这道题在面试里出现的频率，高得离谱。我面过的大厂，几乎每家都考过。说白了，就是让你手写一个 LRU 缓存。

2.1 数据结构选型

要实现 O(1) 的 get 和 put，你需要两个东西：

• 哈希表：用于 O(1) 查找 key 对应的节点。
• 双向链表：用于 O(1) 插入和删除节点。

为什么是双向链表？因为你要删除一个节点时，需要知道它的前驱和后继。单向链表做不到 O(1) 删除。

2.2 代码实现

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

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

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 如果 key 存在，先通过哈希表定位，再移到头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            // 如果 key 不存在，创建一个新的节点
            DLinkedNode newNode = new DLinkedNode(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
            size++;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                DLinkedNode tail = removeTail();
                cache.remove(tail.key);
                size--;
            }
        } else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}

2.3 复杂度分析

三、LRU 与 LFU 的核心逻辑对比

下面这张图，帮你快速理清两种算法的核心逻辑：

四、面试中的常见追问

面试官不会只满足于你写出 LRU。他们通常会追问：

1. 为什么用双向链表不用单向？——因为删除节点需要 O(1) 找到前驱。
2. 能不能用 LinkedHashMap 实现？——可以，但面试官一般希望你手写，考察基本功。
3. LRU 在 Redis 里是怎么实现的？——Redis 用的是近似 LRU，不是精确 LRU。它随机采样几个 key，淘汰其中最久没用的那个。这样省内存。
4. LFU 怎么实现 O(1)？——需要维护一个频率到双向链表的映射，以及一个最小频率变量。每次访问时，把节点从当前频率链表移到下一个频率链表。

五、总结

LRU 和 LFU 是缓存淘汰算法里最基础的两个。LRU 关注「时间局部性」，LFU 关注「频率局部性」。实际工程中，往往需要根据业务场景来选——甚至把两者结合起来用。

嗯，LRU 的实现其实不难，关键是把哈希表和双向链表配合好。写代码的时候，记得画图辅助思考。我当年第一次写 LRU，就是靠画图才把指针绕清楚的。

公众号:蓝海资料掘金营，微信deep3321