Java 数据结构中怎么用哈希表在 O(1) 时间复杂度内实现 LRU 缓存-java教程-PHP中文网

哈希表+双向链表是实现lru缓存o(1)时间复杂度的核心组合，hashmap负责键到节点的快速查找，双向链表维护访问顺序；java中可直接继承linkedhashmap并重写removeeldestentry方法，或手写node与链表操作以深入理解原理。

java 数据结构中怎么用哈希表在 o(1) 时间复杂度内实现 lru 缓存

哈希表 + 双向链表是核心组合

单纯用 Java 的 HashMap 无法直接实现 LRU（Least Recently Used）缓存的 O(1) 时间复杂度，因为 HashMap 本身不维护访问顺序。真正高效的做法是：用 HashMap 存键到节点的映射，同时用一个**手动维护的双向链表**记录访问顺序——最新访问的放头部，最久未用的在尾部。这样，get 和 put 都能通过哈希定位 + 链表常数时间调整完成。

关键操作必须满足 O(1)

要保证整体 O(1)，每个基础操作都不能有遍历：

get(key)：查 HashMap → 拿到对应链表节点 → 把该节点移到链表头 → 返回值
put(key, value)： • 若 key 已存在：更新值 + 移到链表头 • 若 key 不存在：新建节点插到头；若缓存超限，删掉尾节点 + 清除 HashMap 中对应 entry

Java 实现时推荐复用 LinkedHashMap

Java 标准库的 LinkedHashMap 内部就是哈希表 + 双向链表，且支持按访问顺序排序（构造时传入 true）。只需继承并重写 removeEldestEntry() 方法即可自动淘汰最老项：

Alibabacloud Sdk Client Initialization For Java

在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。

下载

class LRUCache extends LinkedHashMap<integer integer> {
    private final int capacity;
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true); // accessOrder = true
        this.capacity = capacity;
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<integer integer> eldest) {
        return size() > capacity;
    }
}</integer></integer>

这个实现天然满足 get/put 均为 O(1)，且代码简洁、线程不安全但符合典型 LRU 场景需求。