问题

27. 如何基于 LinkedHashMap 实现 LRU 缓存？相比 Guava Cache 有哪些优劣？

标准答案

LinkedHashMap 通过 维护访问顺序的双向链表 可以实现 LRU（Least Recently Used）缓存。只需在构造时 开启 accessOrder = true，并重写 removeEldestEntry() 方法，在缓存超出限制时自动删除最久未使用的元素。

Guava Cache 提供更丰富的功能，如 自动刷新、异步加载、权重驱逐，适用于复杂缓存场景。而 LinkedHashMap 适用于 小型、低开销 LRU 缓存，可控性更强，但不支持异步失效策略。

答案解析

1. 通过 LinkedHashMap 实现 LRU

LinkedHashMap 继承自 HashMap，但内部维护了 按访问顺序排列的双向链表。JDK 通过 afterNodeAccess() 方法，在 get()、put() 时 将最近访问的节点移动到尾部，从而实现 LRU 机制。

(1) 代码实现

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true); // accessOrder = true 启用 LRU 机制
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity; // 超出容量时移除最久未使用的元素
    }
}

使用示例

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.keySet()); // 输出: [3, 1, 4]

底层原理：

1. accessOrder = true 时，每次 get() 或 put() 都会调用 afterNodeAccess()，把访问的 key 移到链表尾部。
2. removeEldestEntry() 负责移除最久未使用的 key（即链表头部）。

(2) LRU 访问顺序维护

操作	访问顺序
put(1, "A")	[1]
put(2, "B")	[1, 2]
put(3, "C")	[1, 2, 3]
get(1)	[2, 3, 1]
put(4, "D")	[3, 1, 4]（淘汰 2）

2. Guava Cache 的 LRU 机制

Guava Cache（com.google.common.cache.Cache）提供了更高级的缓存控制，例如：

• 自动过期 (expireAfterAccess / expireAfterWrite)
• 权重驱逐 (maximumWeight)
• 异步加载 (refreshAfterWrite)

(1) Guava Cache 实现 LRU

Cache<Integer, String> cache = CacheBuilder.newBuilder()
    .maximumSize(3)  // LRU 容量限制
    .expireAfterAccess(10, TimeUnit.MINUTES)  // 10 分钟未访问则移除
    .build();

cache.put(1, "A");
cache.put(2, "B");
cache.put(3, "C");
cache.getIfPresent(1); // 访问 1
cache.put(4, "D"); // 淘汰 2

Guava 使用 基于哈希表 + 双向链表 实现 分段式 LRU，并支持异步清理，适合大规模缓存。

3. LinkedHashMap 与 Guava Cache 对比

对比项	LinkedHashMap	Guava Cache
淘汰策略	LRU（最近最少使用）	LRU + 过期 + 权重控制
并发控制	线程不安全	支持多线程访问
存储结构	哈希表 + 双向链表	分段式 LRU 哈希表
过期策略	仅支持 size() 限制	expireAfterWrite() expireAfterAccess()
异步加载	不支持	refreshAfterWrite() 支持异步刷新
适用场景	小规模 LRU 缓存	高并发、复杂缓存场景

4. LRU 设计中的常见问题

(1) LinkedHashMap 线程不安全

LinkedHashMap 非线程安全，并发场景可能导致 数据不一致。解决方案：

Map<Integer, String> cache = Collections.synchronizedMap(new LRUCache<>(3));

或者使用 ConcurrentLinkedHashMap（Guava 提供）。

(2) LRU 淘汰可能影响性能

在高并发情况下，频繁的 put() 和 get() 可能导致 链表频繁移动，影响性能。Guava 通过 分段式 LRU 解决这个问题。

(3) LRU 可能导致热点数据淘汰

如果某个 key 突然被大量访问，其他 key 可能过早被淘汰。例如，LinkedHashMap LRU 不能动态调整淘汰策略，而 Guava Cache 允许 设置权重策略，更灵活。

深入追问

🔹 1. LinkedHashMap 如何保证访问顺序？

• 维护 双向链表，每次访问 key 时 移动到链表尾部，保证 get() 操作影响访问顺序。

🔹 2. 为什么 removeEldestEntry() 不能手动调用？

• 这个方法 只在 put() 时触发，不会在 get() 时触发，因此 get() 访问不会主动删除元素。

🔹 3. Guava Cache 的 LRU 如何避免全局锁？

• Guava 采用 分段式 LRU（Segmented LRU），不同 key 映射到不同的 LRU 区，减少锁竞争。

相关面试题

• 如何在多线程环境下实现 LRU 缓存？
• 为什么 LinkedHashMap 适合作为 LRU？它与 TreeMap 的区别是什么？
• Guava Cache 如何支持异步刷新？
• Redis LRU 机制如何工作？与 JVM LRU 不同点？