[数据结构] LRU Cache | ListMap 实现

目录

1. 什么是 LRU Cache

2. LRU Cache 的实现

3. 代码

概念理解

题目要求

删除一个节点（抽出一本书）

在链表头添加一个节点（把一本书放在最上面）

如何快速找到要抽出来的书？

答疑

代码实现

复杂度分析

4. 测试

1. 什么是 LRU Cache

定义:

• LRU 是 Least Recently Used（最近最少使用）的缩写，它是一种缓存替换算法。

Cache 的概念:

• 在狭义上，Cache 指的是位于 CPU 和主存之间的快速 RAM，通常使用 SRAM 技术而非 DRAM，以提供更快的数据访问速度。
• 广义上来讲，Cache 是指任何用于协调两种速度差异较大的硬件之间数据传输速度的结构。例如，CPU 与主存、内存与硬盘、甚至硬盘与网络之间的缓存。

• 替换策略:

• • 当缓存容量达到上限而需要加入新内容时，LRU Cache 根据“最久未使用”的原则选择要移除的内容，即移除一段时间内最久没有被访问过的数据项。
  • 这种策略确保了缓存中保留的是最常或最近使用的数据。

2. LRU Cache 的实现

题目背景:

• 我们可以通过解决 OJ 题目 146. LRU 缓存 来学习 LRU Cache 的实现方法。此题要求设计的数据结构必须支持在平均 O(1) 时间复杂度下完成 put 和 get 操作。

初始化:

• LRUCache(int capacity) 使用正整数作为容量来初始化缓存。这里的容量是指可以存储的关键字数量，当插入新的关键字导致总数超过容量时，应删除最近最少使用的关键字。

操作解析:

• Get 操作: 给定一个关键字（实际上是一个地址），检查该关键字是否存在于缓存中。如果存在，则返回对应的数据值，并更新其为最近使用。
• Put 操作: 包含两种情况

• • 一是更新现有关键字的值
  • 二是添加新的关键字-值对。
  • 如果添加新关键字导致缓存超出容量，则需先删除最久未使用的元素。

结构设计:

• 哈希表 (unordered_map): 为了满足查找、新增和更新均为 O(1) 的时间复杂度，我们使用哈希表存储关键字到链表节点迭代器的映射。
• 双向链表 (list): 用来维护元素的使用顺序。每次访问某个关键字后，将对应的节点移到链表头部；当需要移除元素时，总是移除链表尾部的节点（即最近最少使用的元素）。

优化点:

• 使用 unordered_map<int, list< pair<int, int> >::iterator> 将关键字映射到链表中的位置，这样可以保证所有操作的时间复杂度为 O(1)。
• 利用 splice 方法直接在链表中移动节点，避免不必要的创建和销毁节点的操作，提高效率。

3. 代码

概念理解

想象你有一摞书。

• get：把一本书（key）抽出来，放在最上面。
• put：放入一本新书。

• • 如果已经有这本书（key），就把它抽出来放在最上面，并替换它的 value。（例如把一本书的第二版替换成第三版）
  • 如果没有这本书（key），就放在最上面。
  • 如果超过 capacity 本书，就把最下面的书移除。

题目要求

• get 和 put 都是 O(1) 时间复杂度，这可以用双向链表实现，每个节点都表示一本书（key 和 value）。
• 每个节点都有两个指针 prev 和 next 分别指向前一个和下一个节点。
• 此外，链表中还包含一个哨兵节点 dummy，这可以让每个节点的 prev 和 next 都不为空，从而简化代码逻辑。

删除一个节点（抽出一本书）

• 删除节点 x 之前：

• • x.prev.next = x.next
  • x.next.prev = x.prev

在链表头添加一个节点（把一本书放在最上面）

• 插入节点 x 之前：

• • x.prev = dummy
  • x.next = dummy.next
  • x.prev.next = x
  • x.next.prev = x

如何快速找到要抽出来的书？

• 把 key 映射到链表中的对应节点。这可以用哈希表实现。

答疑

• 问：需要几个哨兵节点？

• • 答：一个就够了。一开始哨兵节点 dummy 的 prev 和 next 都指向 dummy。随着节点的插入，dummy 的 next 指向链表的第一个节点（最上面的书），prev 指向链表的最后一个节点（最下面的书）。

• 问：为什么节点要把 key 也存下来？

• • 答：在删除链表末尾节点时，也要删除哈希表中的记录，这需要知道末尾节点的 key。

代码实现

class Node {
public:
    int key;
    int value;
    Node* prev;
    Node* next;

    Node(int k = 0, int v = 0): key(k), value(v), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    int capacity;
    Node* dummy; // 哨兵节点
    unordered_map<int, Node*> key_to_node;

    void remove(Node* x) {
        x->prev->next = x->next;
        x->next->prev = x->prev;
    }

    void push_front(Node* x) {
        x->prev = dummy;·
        x->next = dummy->next;
        x->prev->next = x;
        x->next->prev = x;
    }

    Node* get_node(int key) {
        auto it = key_to_node.find(key);
        if (it == key_to_node.end()) {
            return nullptr;
        }
        Node* node = it->second;
        remove(node);
        push_front(node);
        return node;
    }

public:
    LRUCache(int capacity): capacity(capacity), dummy(new Node()) {
        dummy->prev = dummy;
        dummy->next = dummy;
    }

    int get(int key) {
        Node* node = get_node(key);
        return node ? node->value : -1;
    }

    void put(int key, int value) {
        Node* node = get_node(key);
        if (node) {
            node->value = value;
            return;
        }
        key_to_node[key] = node = new Node(key, value);
        push_front(node);
        if (key_to_node.size() > capacity) {
            Node* back_node = dummy->prev;
            key_to_node.erase(back_node->key);
            remove(back_node);
            delete back_node;
        }
    }
};

复杂度分析

• 时间复杂度：所有操作均为 O(1)。
• 空间复杂度：O(min(p, capacity))，其中 p 为 put 的调用次数。

4. 测试

#include <iostream>
#include <unordered_map>

#include"LRUCache.hpp"

void testLRUCache() {
    LRUCache cache(2);

    cache.put(1, 1);
    cache.put(2, 2);

    std::cout << "Get key 1: " << (cache.get(1) == 1 ? "Pass" : "Fail") << std::endl;

    cache.put(3, 3);

    std::cout << "Get key 2: " << (cache.get(2) == 2 ? "Pass" : "Fail") << std::endl;

    cache.put(4, 4);

    std::cout << "Get key 1: " << (cache.get(1) == 1 ? "Pass" : "Fail") << std::endl;

    std::cout << "Get key 3: " << (cache.get(3) == 3 ? "Pass" : "Fail") << std::endl;

    std::cout << "Get key 4: " << (cache.get(4) == 4 ? "Pass" : "Fail") << std::endl;
}

int main() {
    testLRUCache();
    return 0;
}

运行：

通过上述设计，我们可以有效地实现一个高效且符合 LRU 替换策略的缓存系统，适用于多种应用场景，如数据库查询缓存、网页服务器响应缓存等。

代码设计参考：灵神的题解