Java实现LRU缓存案例

wen java案例 2026-08-04 2

Java实现LRU缓存案例：从面试题到生产级实战（附源码与性能调优）

目录导读

LRU缓存核心原理与适用场景
Java实现LRU的三种主流方案对比
手写案例：基于LinkedHashMap的优雅实现
手写案例：基于双向链表+HashMap的工业级实现
高频面试问答：LRU算法避坑指南
性能优化与线程安全策略
总结与扩展思考

LRU缓存核心原理与适用场景

LRU（Least Recently Used，最近最少使用）是一种经典的缓存淘汰策略：当缓存容量满时，优先淘汰最久未被访问的数据，其核心假设是“未来被访问的数据大概率是刚刚被访问过的数据”，因此通过记录访问时间顺序来提升命中率。

Java实现LRU缓存案例

典型适用场景：

本地热点数据缓存（如用户会话、商品详情）
数据库查询结果缓存（减少重复IO）
浏览器页面回退机制（最近浏览优先保留）

不适用场景：

数据访问模式呈随机分布（命中率收益低）
缓存数据体积巨大且内存敏感（需考虑序列化成本）

Java实现LRU的三种主流方案对比

方案	核心实现	时间复杂度	内存开销	适用场景
LinkedHashMap	重写`removeEldestEntry()`	O(1)	低	快速原型/简单业务
双向链表+HashMap	手动维护节点指针	O(1)	中	需要精细控制淘汰策略
Caffeine/Guava	外部缓存库（基于Window-TinyLFU）	O(1)	较高	高并发生产环境

重点提示：前两种是面试高频考点，第三种则是生产环境的“银弹”，本文重点剖析前两种手写实现。

手写案例：基于LinkedHashMap的优雅实现

代码实现（核心逻辑）：

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) {
        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");
        cache.get(1); // 访问key=1，使其变为最新
        cache.put(4, "D"); // 此时容量超限，淘汰最久未用的key=2
        System.out.println(cache.keySet()); // 输出 [3, 1, 4]
    }
}

关键点解析：

构造器第三个参数accessOrder=true表示按访问顺序排序（默认false为插入顺序）。
removeEldestEntry在每次put后自动调用，返回true即触发淘汰最老节点。

优点：代码量极少，易于维护。
缺点：无法定制淘汰策略（如基于权重），且未同步（线程不安全）。

手写案例：基于双向链表+HashMap的工业级实现

为什么需要手写？
当需要控制淘汰粒度（如按字节数）、添加数据淘汰回调、或者避免继承带来的耦合时，手动实现更灵活。

完整代码（含注释）：

import java.util.HashMap;
import java.util.Map;
public class LRUCacheManual<K, V> {
    // 双向链表节点
    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V> prev, next;
        Node(K key, V value) { this.key = key; this.value = value; }
    }
    private final Map<K, Node<K, V>> map = new HashMap<>();
    private final int capacity;
    // 虚拟头尾节点，避免空指针判断
    private final Node<K, V> head = new Node<>(null, null);
    private final Node<K, V> tail = new Node<>(null, null);
    public LRUCacheManual(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }
    public V get(K key) {
        Node<K, V> node = map.get(key);
        if (node == null) return null;
        removeNode(node);
        addToHead(node);
        return node.value;
    }
    public void put(K key, V value) {
        Node<K, V> node = map.get(key);
        if (node != null) {
            node.value = value; // 更新值
            removeNode(node);
            addToHead(node);
        } else {
            if (map.size() >= capacity) {
                // 淘汰尾部节点（最久未使用）
                Node<K, V> last = tail.prev;
                removeNode(last);
                map.remove(last.key);
            }
            Node<K, V> newNode = new Node<>(key, value);
            map.put(key, newNode);
            addToHead(newNode);
        }
    }
    // 链表操作（O(1)）
    private void addToHead(Node<K, V> node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
    private void removeNode(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    // 测试
    public static void main(String[] args) {
        LRUCacheManual<Integer, String> cache = new LRUCacheManual<>(2);
        cache.put(1, "X");
        cache.put(2, "Y");
        System.out.println(cache.get(1)); // X
        cache.put(3, "Z"); // 淘汰key=2
        System.out.println(cache.get(2)); // null
    }
}

设计亮点：

虚拟头尾节点简化边界条件。
所有操作均摊时间复杂度O(1)。
可扩展：在put方法中增加evictCallback回调，便于监控淘汰数据。

高频面试问答：LRU算法避坑指南

Q1：为什么LinkedHashMap的removeEldestEntry默认返回false？
答：默认不淘汰任何元素，确保它是一个普通Map，开发者通过重写此方法实现“容量满时淘汰最老节点”的策略。

Q2：手写实现中，为什么使用双向链表而非单向？
答：单向链表删除节点时需要遍历找到前驱节点（O(n)），而双向链表可以直接通过node.prev定位前驱，实现O(1)删除。

Q3：如何保证LRU缓存的线程安全？
答：可选用Collections.synchronizedMap包装（粒度粗），或使用ConcurrentHashMap+锁分段（如ConcurrentLinkedHashMap），更推荐使用Caffeine等成熟库（内部采用无锁算法）。

Q4：如果缓存命中率极低，如何优化？
答：先检查数据访问模式是否为“突发性”（如热点新闻），可改用LFU（Least Frequently Used）算法；或增加预加载机制，将即将访问的数据提前加入缓存。

性能优化与线程安全策略

小容量优化：当容量≤100时，直接使用LinkedHashMap配合synchronized即可，避免复杂锁的开销。
高并发场景：采用ConcurrentHashMap的compute方法结合自定义节点锁，或直接引入Caffeine（其内部使用环形缓冲区与读写锁）。
内存泄漏防护：在put时判断value是否可引用大对象，必要时使用WeakReference包装值。
监控与统计：记录命中次数、淘汰次数、平均访问耗时，便于动态调整容量。

调优案例：某电商系统使用手写LRU缓存商品详情，容量设为10万，优化后：

将HashMap初始容量设为capacity/0.75f，避免扩容损耗。
使用volatile修饰count变量，实现近似命中率统计而不加锁。
通过JMH基准测试,吞吐量提升35%。

总结与扩展思考

本文从原理到实战,剖析了Java实现LRU缓存的两种必会方案。掌握LinkedHashMap的快速实现是基础，而手写双向链表+HashMap则能体现扎实的数据结构功底，在真实项目中，建议优先评估Caffeine（性能强于Guava），但在面试或学习阶段，手写实现能帮你深入理解“空间换时间”的缓存哲学。

扩展方向：

如何实现“过期时间”淘汰？（参考LoadingCache的expireAfterWrite）
如何将LRU扩展为LRU-K（解决批量扫描带来的频繁淘汰）？
如何结合持久化存储（如Redis）实现多级缓存？

如果你正在准备Java架构师面试,建议在纸上默写双向链表的增删逻辑，并解释为什么HashMap的rehash会影响链表顺序——这才是考察深度的关键。