深入理解Java缓存算法（从零开始掌握LRU等主流缓存淘汰策略）

什么是缓存？为什么需要缓存算法？

缓存是一种临时存储机制，用于保存频繁访问的数据副本，避免重复计算或远程调用。然而，内存资源有限，不可能无限存储数据，因此需要缓存淘汰策略来决定哪些数据应该被移除。

常见的缓存淘汰策略

• FIFO（First In First Out）：先进先出，最早加入的数据最先被淘汰。
• LFU（Least Frequently Used）：最少使用，根据访问频率淘汰数据。
• LRU（Least Recently Used）：最近最少使用，淘汰最久未被访问的数据——这是最常用且高效的策略之一。

手把手实现LRU缓存（Java版）

Java标准库中的 LinkedHashMap 天然支持按访问顺序排序，非常适合实现LRU缓存。下面是一个完整的示例：

import java.util.LinkedHashMap;import java.util.Map;public class LRUCache<K, V> extends LinkedHashMap<K, V> {    private final int capacity;    public LRUCache(int capacity) {        // accessOrder = true 表示按访问顺序排序        super(capacity, 0.75f, true);        this.capacity = capacity;    }    @Override    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {        // 当 size 超过容量时，自动移除最老的条目        return size() > capacity;    }    public static void main(String[] args) {        LRUCache<Integer, String> cache = new LRUCache<>(3);        cache.put(1, "A");        cache.put(2, "B");        cache.put(3, "C");        System.out.println(cache); // {1=A, 2=B, 3=C}        cache.get(1); // 访问 key=1        cache.put(4, "D"); // 插入新元素，会淘汰最近最少使用的（即 key=2）        System.out.println(cache); // {3=C, 1=A, 4=D}    }}

上面的代码通过继承 LinkedHashMap 并重写 removeEldestEntry 方法，轻松实现了LRU逻辑。当缓存大小超过设定容量时，自动移除“最老”的条目（即最近最少使用的）。

更高级的实现：手动构建LRU（双向链表 + 哈希表）

如果你希望深入理解LRU底层原理，也可以手动实现。核心思想是：用哈希表实现O(1)查找，用双向链表维护访问顺序。

class Node {    int key;    int value;    Node prev;    Node next;    Node(int key, int value) {        this.key = key;        this.value = value;    }}public class ManualLRUCache {    private Map<Integer, Node> cache;    private Node head, tail;    private int capacity;    private int size;    public ManualLRUCache(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;    }    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;    }}

总结

通过本教程，你已经掌握了Java内存缓存的基本概念和LRU算法的两种实现方式。对于大多数应用场景，使用 LinkedHashMap 的方式足够高效且简洁；若需极致性能或自定义行为，可考虑手动实现。

记住，选择合适的缓存淘汰策略能极大提升系统性能。希望这篇教程能帮助你打下坚实的Java缓存算法基础！