如何用linkedHashMap实现LRUCache

对于个人站长和维护VPS虚拟机后端服务的开发者来说，性能优化至关重要。高效的缓存策略可以显著减轻数据库和CPU的压力。其中，LRU（Least Recently Used，最久未使用）缓存是最常用的一种淘汰策略，它保证在缓存空间不足时，优先清除那些最长时间未被访问的数据。

在 Java 生态中，实现 LRU Cache 无需手动构建双向链表和 HashMap，我们可以巧妙地利用标准库中的 LinkedHashMap。

LinkedHashMap 的核心特性

LinkedHashMap 继承自 HashMap，但其内部还维护了一个双向链表，用于记录元素的插入顺序或访问顺序。实现 LRU 缓存的关键就在于启用它的访问顺序 (Access Order) 模式。

当我们将 LinkedHashMap 的 accessOrder 参数设置为 true 时：
1. 访问更新： 每次调用 get() 或 put() 方法时，被操作的键值对都会自动移动到链表的尾部（即最近使用端，MRU）。
2. 淘汰机制： 链表的头部自然而然地就是最久未使用的元素（LRU）。

实践：通过覆盖 removeEldestEntry 实现容量限制

为了限制缓存大小，我们需要继承 LinkedHashMap 并覆盖其核心方法 removeEldestEntry(Map.Entry eldest)。当这个方法返回 true 时，LinkedHashMap 会自动移除链表头部（最旧）的元素。

以下是完整的 Java 实现代码示例：

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * 使用 LinkedHashMap 实现的 LRU 缓存
 * @param <K> 键类型
 * @param <V> 值类型
 */
public class LRUCache<K, V> extends LinkedHashMap<K, V> {

    private final int capacity;

    // 构造函数：设置容量，并启用访问排序 (accessOrder = true)
    public LRUCache(int capacity) {
        // initialCapacity, loadFactor, accessOrder (必须设为 true)
        super(capacity, 0.75f, true); 
        this.capacity = capacity;
    }

    /**
     * 核心方法：覆盖此方法以实现容量限制和自动淘汰策略
     * 当返回 true 时，LinkedHashMap 会自动移除链表头部最老的元素。
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // 当Map的大小超过设定的 capacity 时，执行淘汰
        return size() > capacity; 
    }

    public static void main(String[] args) {
        // 实例化一个容量为 3 的 LRU 缓存
        LRUCache<Integer, String> cache = new LRUCache<>(3);

        System.out.println("--- 初始化缓存 (容量 3) ---");
        cache.put(1, "Data A"); 
        cache.put(2, "Data B"); 
        cache.put(3, "Data C"); 
        System.out.println("当前状态 (LRU->MRU): " + cache);

        System.out.println("\n--- 访问操作，更新顺序 ---");
        // 访问 1，它将移动到 MRU 端 (链表尾部)
        cache.get(1); 
        System.out.println("访问 1 后: " + cache); // 顺序变为 2, 3, 1

        System.out.println("\n--- 插入新元素，触发淘汰 ---");
        // 插入 4，触发淘汰 (最久的 2 被移除)
        cache.put(4, "Data D"); 
        System.out.println("插入 4 后: " + cache); // 顺序变为 3, 1, 4

        // 插入 5，触发淘汰 (最久的 3 被移除)
        cache.put(5, "Data E"); 
        System.out.println("插入 5 后: " + cache); // 顺序变为 1, 4, 5
    }
}

总结

通过继承 LinkedHashMap 并启用访问排序（accessOrder = true）以及重写 removeEldestEntry 方法，我们能够在 O(1) 的时间复杂度内高效地实现一个符合标准的 LRU 缓存。这种方法比手动维护双向链表和 HashMap 组合要简洁得多，是服务端应用开发中实现内存缓存的首选方案之一。