C++ 手撕 LRU 缓存算法

2025-03-31 #C++

在计算机科学中，缓存是提高性能的关键技术之一。而当缓存空间有限时，我们就需要一种策略来决定哪些数据应该保留，哪些应该被淘汰。LRU（Least Recently Used，最近最少使用）就是其中一种非常经典且广泛使用的缓存淘汰算法。它的核心思想是：如果数据最近被访问过，那么将来被访问的几率也更高。 因此，当缓存满了需要淘汰数据时，应该优先淘汰那些最长时间未被访问过的数据。

LRU 算法的核心需求

一个合格的 LRU 缓存需要高效地支持以下操作：

get(key)：通过键 key 获取对应的值 value。如果键存在，则返回其值，并将该数据标记为“最近使用”；如果键不存在，则返回一个表示未命中的值（如 -1 或 null）。
put(key, value)：插入或更新一个键值对。
- 如果 key 已存在，更新其 value，并将该数据标记为“最近使用”。
- 如果 key 不存在：
  - 检查缓存是否已满。
  - 如果未满，直接插入新的键值对，并将其标记为“最近使用”。
  - 如果已满，则先淘汰掉“最久未使用”的数据，然后再插入新的键值对，并将其标记为“最近使用”。
高效性要求： 上述 get 和 put 操作的时间复杂度最好能达到 O(1)。

数据结构的选择：哈希表 + 双向链表

为了同时满足 O(1) 的查找、插入、删除和移动（标记为最近使用）要求，单一的数据结构很难胜任。LRU 的经典实现巧妙地结合了两种数据结构：

哈希表（std::unordered_map）： 用于存储 key 到链表节点的映射。这使得我们能够以 O(1) 的平均时间复杂度快速查找一个 key 是否存在于缓存中，并直接定位到它在链表中的位置。
双向链表（std::list）： 用于维护数据的“最近使用”顺序。
- 链表的头部（Head）存放最近使用的数据。
- 链表的尾部（Tail）存放最久未使用的数据。
- 当一个数据被访问（get 或 put），我们就将其对应的链表节点移动到链表头部。这需要 O(1) 时间。
- 当需要淘汰数据时，我们直接删除链表尾部的节点。这需要 O(1) 时间。
- 插入新数据时，将其插入到链表头部。这需要 O(1) 时间。

实现细节

让我们用 C++ 来勾勒一下实现框架：

#include <iostream>
#include <unordered_map>
#include <list> // 使用 STL list 简化节点管理，也可以手动实现双向链表

class LRUCache {
private:
    // 内部节点结构，存储键值对
    struct CacheNode {
      int key;
      int value;
    };

    int capacity; // 缓存容量
    std::list<CacheNode> cacheList; // 双向链表，存储实际数据和顺序
    // 哈希表，存储 key 到链表迭代器(或节点指针)的映射
    std::unordered_map<int, std::list<CacheNode>::iterator> cacheMap;

    // 辅助函数：将节点移动到链表头部（表示最近使用）
    void moveToFront(int key, std::list<CacheNode>::iterator it) {
      // 从当前位置提取节点信息
      CacheNode node = *it;
      // 从链表中删除旧位置的节点
      cacheList.erase(it);
      // 将节点插入到链表头部
      cacheList.push_front(node);
      // 更新哈希表中 key 对应的迭代器
      cacheMap[key] = cacheList.begin();
    }

public:
  LRUCache(int cap) : capacity(cap) {}

  int get(int key) {
    // 检查 key 是否在哈希表中
    auto map_it = cacheMap.find(key);
    if (map_it == cacheMap.end()) {
      // 未命中
      return -1;
    }

    // 命中，获取链表迭代器
    std::list<CacheNode>::iterator list_it = map_it->second;

    // 将访问的节点移动到链表头部
    // 注意：这里直接传入 key 和 迭代器给 moveToFront 更清晰
    // (或者，moveToFront 只接受迭代器，内部通过 *it 获取 key)
    int value = list_it->value; // 先保存值
    moveToFront(key, list_it); // 将节点移到前面

    // 返回找到的值
    return value;
  }

  void put(int key, int value) {
    // 检查 key 是否已存在
    auto map_it = cacheMap.find(key);
    if (map_it != cacheMap.end()) {
      // Key 已存在，更新值并移到头部
      std::list<CacheNode>::iterator list_it = map_it->second;
      list_it->value = value; // 更新值
      moveToFront(key, list_it); // 移到头部
    } else {
      // Key 不存在，需要插入新节点

      // 检查容量是否已满
      if (cacheMap.size() >= capacity) {
        // 缓存已满，需要淘汰最久未使用的节点（链表尾部）
        // 获取尾部节点的 key
        int keyToRemove = cacheList.back().key;
        // 从哈希表中删除
        cacheMap.erase(keyToRemove);
        // 从链表中删除尾部节点
        cacheList.pop_back();
      }

      // 创建新节点并插入到链表头部
      cacheList.push_front({key, value});
      // 在哈希表中建立 key 到新节点的映射
      cacheMap[key] = cacheList.begin();
    }
  }

  // (可选) 打印缓存内容，用于调试
  void printCache() {
    std::cout << "Cache Content (Front=Recent, Back=Old): ";
    for (const auto& node : cacheList) {
      std::cout << "[" << node.key << ":" << node.value << "] ";
    }
    std::cout << std::endl;
    std::cout << "Map Size: " << cacheMap.size() << ", List Size: " << cacheList.size() << std::endl;
  }
};

int main() {
  // 示例用法
  LRUCache cache(2); // 创建容量为 2 的 LRU 缓存

  cache.put(1, 1);    // 缓存是 {1=1}
  cache.printCache();
  cache.put(2, 2);    // 缓存是 {2=2, 1=1}
  cache.printCache();
  std::cout << "Get(1): " << cache.get(1) << std::endl; // 返回 1, 缓存是 {1=1, 2=2}
  cache.printCache();
  cache.put(3, 3);    // 容量已满，淘汰最久未使用的 2，缓存是 {3=3, 1=1}
  cache.printCache();
  std::cout << "Get(2): " << cache.get(2) << std::endl; // 返回 -1 (未命中)
  cache.printCache();
  cache.put(4, 4);    // 容量已满，淘汰最久未使用的 1，缓存是 {4=4, 3=3}
  cache.printCache();
  std::cout << "Get(1): " << cache.get(1) << std::endl; // 返回 -1 (未命中)
  std::cout << "Get(3): " << cache.get(3) << std::endl; // 返回 3, 缓存是 {3=3, 4=4}
  cache.printCache();
  std::cout << "Get(4): " << cache.get(4) << std::endl; // 返回 4, 缓存是 {4=4, 3=3}
  cache.printCache();

  return 0;
}

复杂度分析

时间复杂度：
- get(key)：哈希表查找是 O(1) 平均，链表移动是 O(1)。总平均时间复杂度 O(1)。
- put(key, value)：哈希表查找/插入是 O(1) 平均，链表插入/删除/移动是 O(1)。总平均时间复杂度 O(1)。
空间复杂度： 哈希表和双向链表都需要存储最多 capacity 个元素（键和值，以及链表指针/迭代器）。所以空间复杂度是 O(capacity)。

总结

LRU 缓存算法通过结合哈希表（快速查找）和双向链表（快速排序和淘汰）的优点，实现了高效的缓存管理。

LeetCode 参考题目 146. LRU 缓存

2025-03-31 #C++