哈希表+双向链表是实现LRU缓存O(1)时间复杂度的核心组合，HashMap负责键到节点的快速查找，双向链表维护访问顺序；Java中可直接继承LinkedHashMap并重写removeEldestEntry方法，或手写Node与链表操作以深入理解原理。
哈希表 + 双向链表是核心组合
单纯用 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() 方法即可自动淘汰最老项：
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;
}
}
这个实现天然满足 get/put 均为 O(1)，且代码简洁、线程不安全但符合典型 LRU 场景需求。
Alibabacloud Sdk Client Initialization For Java
下载
在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。
立即学习“Java免费学习笔记（深入）”；
手写双向链表 + HashMap 更利于理解原理
如果面试或学习需要体现底层逻辑，可以自定义 Node 类和双向链表操作：
- 定义
Node<K,V>，含 key、value、prev、next - 维护 head（虚拟头）和 tail（虚拟尾），避免空指针判断
- 封装
moveToHead(node)、removeTail()等辅助方法，确保每次操作只改几处指针 - HashMap 存
key → Node，所有查找、删除都靠它跳转，不遍历链表
只要链表插入、删除、移动都是固定步骤（改 4~6 个引用），就严格保持 O(1)。
