LRU 缓存：基于 LinkedHashMap 的 Java 实现

1. LRU 缓存原理

LRU（Least Recently Used） 是一种缓存淘汰策略，当缓存空间不足时，优先移除最近最少使用的数据。核心思想是：

• 访问数据时将其移到访问队列前端
• 淘汰数据时从队列末端移除

数学表达：
设缓存容量为 $C$，当前元素集合为 $S = {e_1, e_2, \dots, e_n}$，访问时间序列为 $T = {t_1 < t_2 < \dots < t_n}$，则淘汰条件为： $$ |S| > C \implies \text{移除 } \arg\min_{e_i \in S} t_i $$

2. LinkedHashMap 实现机制

LinkedHashMap 通过双向链表 + 哈希表天然支持 LRU：

• 哈希表：$O(1)$ 时间快速访问数据
• 双向链表：维护元素访问顺序
• 关键特性：构造器设置 accessOrder=true 时，自动将访问元素移至链表尾部

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

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxCapacity;
    
    public LRUCache(int maxCapacity) {
        // 参数说明: 
        // initialCapacity - 初始容量
        // loadFactor      - 负载因子
        // accessOrder     - true=访问顺序, false=插入顺序
        super(maxCapacity, 0.75f, true);
        this.maxCapacity = maxCapacity;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // 当当前大小超过容量时移除最旧元素
        return size() > maxCapacity;
    }
    
    // 示例用法
    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");
        cache.get(1);    // 访问"1"使其成为最新
        
        cache.put(4, "D"); // 触发淘汰: 移除键2 (最近最少使用)
        System.out.println(cache); // 输出: {3=C, 1=A, 4=D}
    }
}

3. 关键操作分析

4. 实现要点

1. 容量控制：通过 removeEldestEntry 重写触发淘汰逻辑
2. 访问更新：accessOrder=true 确保每次 get/put 自动更新链表顺序
3. 线程安全：需外部同步（示例未展示，生产环境建议加锁）

5. 复杂度对比

注：此实现是标准库最简方案，实际生产可结合 ConcurrentHashMap 实现线程安全版本。