算法讲解神器，用简单语言把复杂算法讲明白。无论你是刚入门的小…

# LRU 缓存实现详解（哈希表 + 双向链表）

一、核心思想

• LRU（Least Recently Used）：容量满时淘汰“最久未使用”的数据。
• 设计目标：get 和 put 都要 O(1) 时间复杂度。
• 组合拳：
• 哈希表：key → 节点，实现 O(1) 定位。
• 双向链表：维护访问顺序，头部最近使用，尾部最久未使用；O(1) 删除/插入任意节点。

二、操作流程

• get(key)：
• 哈希表查不到 → 返回 -1。
• 查到 → 节点移到链表头部，返回 value。
• put(key, value)：
• key 已存在 → 更新 value，节点移到头部。
• 不存在 → 新建节点插到头部，哈希表登记。
• 超容量 → 删尾节点，同时从哈希表删除。

三、Java 代码

```java

class LRUCache {

class Node {

int key, value;

Node prev, next;

Node(int k, int v) { key = k; value = v; }

}

private final int capacity;

private final Map<Integer, Node> map = new HashMap<>();

private final Node head, tail; // 虚拟头尾哨兵节点

public LRUCache(int capacity) {

this.capacity = capacity;

head = new Node(0, 0);

tail = new Node(0, 0);

head.next = tail;

tail.prev = head;

}

public int get(int key) {

Node node = map.get(key);

if (node == null) return -1;

moveToHead(node);

return node.value;

}

public void put(int key, int value) {

Node node = map.get(key);

if (node != null) {

node.value = value;

moveToHead(node);

return;

}

if (map.size() >= capacity) {

Node lru = tail.prev;

removeNode(lru);

map.remove(lru.key); // 别忘了删哈希表！

}

Node fresh = new Node(key, value);

map.put(key, fresh);

addToHead(fresh);

}

// ---- 双向链表工具方法 ----

private void removeNode(Node node) {

node.prev.