LRU 缓存数据结构设计与实现：LinkedHashMap 与手写方案

题目内容

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。 实现 LRUCache 类：

• LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value；如果不存在，则向缓存中插入该组 key-value。如果插入操作导致关键字数量超过 capacity，则应该逐出最久未使用的关键字。 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

思路

基于 LinkedHashMap 实现

这是最推荐在实际工程中使用的方案，因为它代码量极少，且性能非常稳定。

核心原理

LinkedHashMap 已经为我们维护了一个双向链表。它不仅支持普通的哈希映射，还能通过一个布尔参数 accessOrder 来控制链表的排序方式：

• accessOrder = true：每次 get 或 put 某个元素，该元素都会被自动移动到链表的末尾。
• 淘汰机制：LinkedHashMap 预留了 removeEldestEntry 方法。当插入新元素后，该方法若返回 true，则会自动删除链表头部的'最老'节点。

操作步骤

1. 继承：让类继承 LinkedHashMap。
2. 构造：调用父类构造器，传入 (capacity, 0.75f, true)，开启按访问顺序排序。
3. 重写：重写 removeEldestEntry 方法，逻辑设为 return size() > capacity。

代码

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

/**
 * 这种解法的精髓在于：利用 JDK 已经写好的数据结构，
 * 我们只需要定义'何时删除老数据'的规则即可。
 */
class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        /**
         * 参数说明：
         * initialCapacity: 初始容量
         * loadFactor: 负载因子（默认 0.75f）
         * accessOrder: true 表示按'访问顺序'排序（LRU 核心），false 按'插入顺序'
         */
        (capacity, , );
        .capacity = capacity;
    }

    
    
       {
        
         size() > capacity;
    }

    
     V  {
         .get(key);
    }
}