Java集合框架如何利用LinkedHashMap实现LRU缓存_Java集合框架特殊映射的应用技巧

LinkedHashMap通过双向链表维护访问顺序，使链表头部为最近最少使用元素，结合重写removeEldestEntry方法实现容量控制，从而高效支持LRU缓存机制。

Java集合框架中的

LinkedHashMap

LinkedHashMap

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

/**
 * 一个基于LinkedHashMap实现的简单LRU缓存。
 * 当缓存大小超过预设的最大值时，会自动移除最近最少使用的条目。
 *
 * @param  键的类型
 * @param  值的类型
 */
public class LRUCache extends LinkedHashMap {

    private final int capacity;

    /**
     * 构造一个新的LRU缓存实例。
     *
     * @param capacity 缓存的最大容量。当缓存大小达到此值时，会触发LRU淘汰。
     */
    public LRUCache(int capacity) {
        // initialCapacity: 初始容量，可以根据预期大小调整
        // loadFactor: 负载因子，默认0.75
        // accessOrder: true表示按访问顺序排序，false表示按插入顺序排序。
        // LRU缓存需要按访问顺序，所以这里必须是true。
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    /**
     * 重写此方法以实现LRU淘汰策略。
     * 当此方法返回true时，LinkedHashMap会移除最老的条目。
     *
     * @param eldest 最近最少使用的条目。
     * @return 如果返回true，则移除eldest条目；否则不移除。
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        // 当当前缓存大小超过容量时，返回true，LinkedHashMap会自动移除最老的条目。
        return size() > capacity;
    }

    // 示例用法
    public static void main(String[] args) {
        LRUCache cache = new LRUCache<>(3);

        System.out.println("--- 首次添加元素 ---");
        cache.put("apple", 1); // {apple=1}
        cache.put("banana", 2); // {apple=1, banana=2}
        cache.put("cherry", 3); // {apple=1, banana=2, cherry=3}
        System.out.println("当前缓存: " + cache); // 预期输出：{apple=1, banana=2, cherry=3}

        System.out.println("\n--- 访问元素，改变顺序 ---");
        cache.get("apple"); // 访问apple，apple会移动到链表末尾，成为最近访问的
        System.out.println("访问apple后: " + cache); // 预期输出：{banana=2, cherry=3, apple=1}

        System.out.println("\n--- 添加新元素，触发淘汰 ---");
        cache.put("date", 4); // 添加date，容量超限，banana被淘汰
        System.out.println("添加date后: " + cache); // 预期输出：{cherry=3, apple=1, date=4} (banana被淘汰)

        System.out.println("\n--- 再次访问，再次改变顺序 ---");
        cache.get("cherry"); // 访问cherry，cherry移动到末尾
        System.out.println("访问cherry后: " + cache); // 预期输出：{apple=1, date=4, cherry=3}

        System.out.println("\n--- 添加新元素，再次触发淘汰 ---");
        cache.put("elderberry", 5); // 添加elderberry，容量超限，apple被淘汰
        System.out.println("添加elderberry后: " + cache); // 预期输出：{date=4, cherry=3, elderberry=5} (apple被淘汰)
    }
}

LinkedHashMap

在LRU缓存实现中扮演了怎样的核心角色？

LinkedHashMap

HashMap

accessOrder=false

accessOrder=true

当我第一次接触到

LinkedHashMap

accessOrder

true

get

put

LinkedHashMap

这种机制完美契合了LRU的“最近最少使用”原则：链表头部的元素就是我们希望在缓存满时最先淘汰的对象。

LinkedHashMap

removeEldestEntry

true

LinkedHashMap

LinkedHashMap

立即学习“Java免费学习笔记（深入）”；

构建基于

LinkedHashMap

的LRU缓存时，有哪些常见的陷阱与性能考量？

虽然

LinkedHashMap

首先，最常见的错误就是忘记在

LinkedHashMap

accessOrder

true

false

LinkedHashMap

其次，

LinkedHashMap

LRUCache

ConcurrentModificationException

百度智能云·曦灵

百度旗下的AI数字人平台

下载

1. 外部同步：最简单粗暴的方法是在所有对缓存的读写操作外部加上

   synchronized

   关键字，或者使用

   ReentrantLock

   。但这会带来性能瓶颈，因为所有操作都变成了串行执行。
2. 并发LRU实现：更健壮的方案是使用

   java.util.concurrent

   包中的工具，例如将

   LinkedHashMap

   包装在

   Collections.synchronizedMap

   中，或者更复杂地，自己实现一个基于

   ConcurrentHashMap

   和

   ConcurrentLinkedDeque

   的并发LRU缓存。不过，后者会比直接扩展

   LinkedHashMap

   复杂得多，因为你需要自己管理哈希表和双向链表之间的同步逻辑。对于大多数非高并发场景，外部同步或

   Collections.synchronizedMap

   可能就足够了。

性能方面，虽然

LinkedHashMap

get

put

HashMap

removeEldestEntry

capacity

LRU缓存机制在哪些实际场景中能发挥其独特优势？

LRU缓存机制的价值，在于它能够智能地保留“热点”数据，同时淘汰那些长时间不被使用的“冷”数据，从而在有限的内存空间内最大化缓存命中率。这在很多资源受限或性能敏感的场景下显得尤为重要。

在我看来，最典型的应用场景莫过于数据库查询结果缓存。想象一下，一个电商网站，商品详情页的访问量可能非常高。如果每次用户请求都直接查询数据库，数据库的压力会非常大。通过将热门商品的详情信息缓存起来，并采用LRU策略，可以确保那些被频繁访问的商品数据始终在内存中，大幅减少数据库I/O，提升响应速度。当有新的商品被访问，而缓存已满时，LRU会自动淘汰掉那些最近一段时间内没人看的老旧商品数据。

另一个常见的场景是Web服务器的静态资源或API响应缓存。例如，用户头像、缩略图、或者一些不经常变化的API接口数据。这些数据在首次请求时可能需要从存储或计算服务中获取，但后续的请求就可以直接从LRU缓存中快速返回。这不仅能减轻后端服务的压力，还能显著提升用户体验，因为数据加载速度更快了。

此外，LRU缓存也广泛应用于：

• 操作系统中的内存页缓存：CPU访问内存时，会将最近使用的内存页保留在高速缓存中，以减少对主内存的访问。
• 文件系统中的磁盘块缓存：操作系统会将最近访问的磁盘数据块缓存到内存中，减少磁盘I/O。
• 计算密集型应用的中间结果缓存：如果某个计算过程的中间结果可能会被多次用到，但总的数据量又很大，LRU缓存可以用来存储最近计算出的结果，避免重复计算。

LRU的优势在于其动态适应性：它不需要你预先知道哪些数据是“热点”，它会根据实际的访问模式自动调整缓存内容。当然，它的缺点是需要额外的内存来存储缓存数据，而且对于某些访问模式（如全量扫描、顺序访问），LRU可能不如其他策略（如FIFO）有效。但总体而言，在大部分“局部性原理”适用的场景中，LRU都是一个非常高效且实用的缓存策略。