LRU 缓存（哈希表与双向链表）

算法思路

• 数据结构设计
  为了保证 get 和 put 操作的平均时间复杂度为 O(1)，我们采用以下两种数据结构：

  • 哈希表：用于存储键与节点之间的映射（key -> node），方便在 O(1) 时间内查找节点。
  • 双向链表：用于维护缓存中各节点的访问顺序。链表头部表示最近使用的元素，而链表尾部表示最久未使用的元素。采用虚拟头节点和虚拟尾节点可以使插入与删除操作更加简洁。

• 操作说明

  • get(key)
    如果 key 存在于缓存中，则通过哈希表快速定位到对应的节点，并将该节点移动到链表头部（表示最近访问），最后返回节点的值；如果 key 不存在，则返回 -1。

  • put(key, value)

    1. 如果 key 存在，则更新节点的值，并将该节点移动到链表头部。
    2. 如果 key 不存在，则创建新节点，并插入到链表头部，同时在哈希表中添加该节点映射。
    3. 如果插入新节点后缓存数量超过了设定的容量，则删除链表尾部的节点（即最久未使用的节点），同时在哈希表中删除相应的映射。

复杂度分析

• 时间复杂度

  • get 操作：通过哈希表查找节点，再将节点移至链表头部，均为 O(1) 操作。
  • put 操作：插入、更新、删除节点均为 O(1) 操作。

• 空间复杂度

  • 使用的空间主要由哈希表与双向链表共同构成，最多存储 capacity 个节点，故空间复杂度为 O(capacity)。

代码实现

Python 代码

# 定义双向链表的节点类
class Node:
    def __init__(self, key=0, value=0):
        self.key = key       # 键
        self.value = value   # 值
        self.prev = None     # 前驱节点
        self.next = None     # 后继节点

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # 哈希表，存储 key -> Node 的映射
        # 初始化虚拟头尾节点，简化边界条件的处理
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    # 从双向链表中删除指定节点
    def _remove(self, node: Node):
        prev = node.prev
        nxt = node.next
        prev.next = nxt
        nxt.prev = prev

    # 将节点添加到链表头部
    def _add_to_head(self, node: Node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            # 访问后将节点移动到链表头部，表示最近使用
            self._remove(node)
            self._add_to_head(node)
            return node.value
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # 如果节点存在，更新其值并移动到头部
            node = self.cache[key]
            node.value = value
            self._remove(node)
            self._add_to_head(node)
        else:
            # 如果节点不存在，创建新节点并添加到头部
            new_node = Node(key, value)
            self.cache[key] = new_node
            self._add_to_head(new_node)
            # 若超过容量限制，则移除尾部节点（最久未使用）
            if len(self.cache) > self.capacity:
                tail_node = self.tail.prev
                self._remove(tail_node)
                del self.cache[tail_node.key]

if __name__ == '__main__':
    import sys
    # 读取所有输入行
    lines = sys.stdin.read().splitlines()
    if not lines:
        exit(0)
    # 第一行为缓存容量
    capacity = int(lines[0].strip())
    lru_cache = LRUCache(capacity)
    # 处理后续每一行操作
    for line in lines[1:]:
        tokens = line.strip().split()
        if not tokens:
            continue
        if tokens[0] == "get":
            key = int(tokens[1])
            print(lru_cache.get(key))
        elif tokens[0] == "put":
            key = int(tokens[1])
            value = int(tokens[2])
            lru_cache.put(key, value)

Java 代码

import java.util.HashMap;
import java.util.Scanner;

// 独立定义的 LRU 缓存实现类
class LRUCache {
    // 定义双向链表节点内部类
    private class Node {
        int key;
        int value;
        Node prev;
        Node next;
        
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    private int capacity;                     // 缓存容量
    private HashMap<Integer, Node> cache;     // 哈希表存储 key -> Node 的映射
    private Node head, tail;                  // 使用虚拟头尾节点，简化操作
    
    // 构造方法，初始化容量和虚拟链表节点
    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>();
        head = new Node(0, 0);   // 虚拟头节点
        tail = new Node(0, 0);   // 虚拟尾节点
        head.next = tail;
        tail.prev = head;
    }
    
    // 从链表中移除指定节点
    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    // 将节点添加到链表头部（表示最近使用）
    private void addToHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
    
    // 获取 key 对应的值，如果存在则移动节点到头部，否则返回 -1
    public int get(int key) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            remove(node);
            addToHead(node);
            return node.value;
        }
        return -1;
    }
    
    // 插入或更新 key-value 数据，如果超出容量则移除尾部节点
    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            node.value = value;
            remove(node);
            addToHead(node);
        } else {
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
            if (cache.size() > capacity) {
                Node tailNode = tail.prev;
                remove(tailNode);
                cache.remove(tailNode.key);
            }
        }
    }
}

// 主类 Main，负责输入输出
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 第一行输入缓存容量
        int capacity = scanner.nextInt();
        scanner.nextLine(); // 消耗换行符
        LRUCache lruCache = new LRUCache(capacity);
        // 处理每一行操作
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (line.equals("")) continue;
            String[] parts = line.split(" ");
            if (parts[0].equals("get")) {
                int key = Integer.parseInt(parts[1]);
                System.out.println(lruCache.get(key));
            } else if (parts[0].equals("put")) {
                int key = Integer.parseInt(parts[1]);
                int value = Integer.parseInt(parts[2]);
                lruCache.put(key, value);
            }
        }
        scanner.close();
    }
}

C++ 代码

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

// LRUCache 类实现
class LRUCache {
private:
    // 定义双向链表节点结构体
    struct Node {
        int key, value;
        Node* prev;
        Node* next;
        Node(int k, int v): key(k), value(v), prev(nullptr), next(nullptr) {}
    };
    
    int capacity;   // 缓存容量
    unordered_map<int, Node*> cache;  // 哈希表：key -> Node*
    Node* head;     // 虚拟头节点
    Node* tail;     // 虚拟尾节点
    
    // 从链表中移除指定节点
    void remove(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    
    // 将节点添加到链表头部
    void addToHead(Node* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }
    
public:
    // 构造函数，初始化容量和虚拟节点
    LRUCache(int capacity) : capacity(capacity) {
        head = new Node(0, 0);  // 虚拟头节点
        tail = new Node(0, 0);  // 虚拟尾节点
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if (cache.find(key) != cache.end()){
            Node* node = cache[key];
            // 移动节点到头部，标记为最近使用
            remove(node);
            addToHead(node);
            return node->value;
        }
        return -1;
    }
    
    void put(int key, int value) {
        if (cache.find(key) != cache.end()){
            // 如果节点存在，更新值并移动到头部
            Node* node = cache[key];
            node->value = value;
            remove(node);
            addToHead(node);
        } else {
            // 如果节点不存在，创建新节点并添加到头部
            Node* newNode = new Node(key, value);
            cache[key] = newNode;
            addToHead(newNode);
            // 当缓存容量超限，删除尾部节点（最久未使用）
            if (cache.size() > capacity) {
                Node* tailNode = tail->prev;
                remove(tailNode);
                cache.erase(tailNode->key);
                delete tailNode;  // 释放内存
            }
        }
    }
    
    // 析构函数，释放所有节点的内存
    ~LRUCache(){
        Node* current = head;
        while(current != nullptr){
            Node* temp = current;
            current = current->next;
            delete temp;
        }
    }
};

int main() {
    int capacity;
    cin >> capacity;
    LRUCache lruCache(capacity);
    string op;
    // 循环处理输入的每个操作
    while(cin >> op) {
        if(op == "get") {
            int key;
            cin >> key;
            cout << lruCache.get(key) << endl;
        } else if(op == "put") {
            int key, value;
            cin >> key >> value;
            lruCache.put(key, value);
        }
    }
    return 0;
}

Leetcode 35.LRU缓存-原题链接

题目内容

请你设计并实现一个满足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)的平均时间复杂度运行。

输入描述

输入包括若干操作，按照以下格式给出：

第一行一个正整数 capacity，表示缓存的容量。 接下来的若干行每行包含一个操作：

• "get key"：调用 get 方法，查询 key 的值。
• "put key value"：调用 put 方法，插入或更新 key 和 value 的键值对。

输出描述

对于每个 get 操作，输出查询结果。如果关键字存在于缓存中，则输出该值；否则输出 -1。对于 put 操作，无需输出任何内容。

样例1

输入

2
put 1 1
put 2 2
get 1
put 3 3
get 2
put 4 4
get 1
get 3
get 4

输出

1
-1
-1
3
4

说明

LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 10^5
• 最多调用 2 * 10^5 次 get和 put