定义基础数据结构 [blog/lrualgorithm/define]

在实现 LRU 缓存之前，我们首先需要定义一些基础的数据结构。正如前面所说，我们需要结合哈希表和双向链表来实现高效的 LRU 缓存。

节点结构

我们先定义双向链表的节点结构。每个节点需要存储键值对，并且包含指向前一个和后一个节点的引用：

// 定义Node结构体，用于双向链表
struct Node[K, V] {
  key : K
  mut value : V
  mut pre : Node[K, V]?  // 前驱节点
  mut next : Node[K, V]? // 后继节点
}

// Node构造函数
fn new_node[K, V](k : K, v : V) -> Node[K, V] {
  { key: k, value: v, pre: None, next: None }
}

在这个节点结构中有几个有趣的 MoonBit 特性值得我们关注：

• 泛型参数 [K, V]：这使得我们的 LRU 缓存可以适用于任何类型的键和值，非常灵活。

• 可变字段 mut：value、pre 和 next 都被标记为 mut，意味着它们可以在创建后修改。这对于我们需要频繁调整链表结构的 LRU 缓存来说是必须的。

• 可选类型 ?：pre 和 next 是可选类型，表示它们可能为 None。这样处理链表两端的节点会更加自然。

• 简单构造函数：new_node 函数帮助我们创建一个新节点，初始状态下前驱和后继都是 None。

LRU 缓存结构

接下来，我们来定义 LRU 缓存的主体结构：

// LRU缓存结构体
struct LRUCache[K, V] {
  capacity : Int // 容量
  dummy : Node[K, V] // 哑节点，用于标记双向链表的头尾
  key_to_node : Map[K, Node[K, V]] // 键到节点的映射
}

这个结构包含三个关键字段：

• capacity：定义了缓存可以存储的最大键值对数量。

• dummy：一个特殊的哑元节点，不存储实际的键值对，而是用来简化链表操作。使用哑元节点是一个常见的编程技巧，它可以帮助我们避免处理空链表和边界条件的特殊情况。

• key_to_node：一个从键到节点的映射表，使我们能够在 O(1) 时间内通过键找到对应的节点。

为什么使用哑元节点？

哑元节点的使用是一个很巧妙的设计。我们将在链表中使用一个环形结构，其中哑元节点同时充当链表的“头“和“尾“：

• dummy.next 指向链表中最近使用的节点（实际的第一个节点）
• dummy.pre 指向链表中最久未使用的节点（实际的最后一个节点）

这样的设计使得我们在处理节点插入和删除时，不必担心空链表的特殊情况，代码逻辑会更加统一和清晰。

通过这两个基础数据结构，我们已经为实现一个高效的 LRU 缓存打下了基础。在下一部分，我们将开始实现 LRU 缓存的构造函数和核心操作。