构造函数实现 [blog/lrualgorithm/construction]

现在我们已经定义好了基础数据结构，接下来需要实现 LRU 缓存的构造函数。构造函数是任何数据结构的起点，它负责正确初始化内部状态。

构造函数的设计

在设计 LRU 缓存的构造函数时，我们需要考虑：

• 初始化缓存的最大容量
• 创建并设置哑元节点
• 初始化空的键值映射表

让我们看看如何用 MoonBit 实现这个构造函数：

fn new[K : Hash + Eq, V](
  capacity : Int,
  default_k : K,
  default_v : V
) -> LRUCache[K, V] {
  // 创建一个哑元节点，使用提供的默认值
  let dummy = new_node(default_k, default_v)

  // 初始化dummy节点，指向自身形成环
  dummy.next = Some(dummy)
  dummy.pre = Some(dummy)
  { capacity, dummy, key_to_node: Map::new() }
}

这段代码做了几件重要的事情：

• 泛型约束：注意 K : Hash + Eq 这个约束，它表明我们的键类型必须支持哈希操作和相等性比较。这是因为我们要用键来创建哈希映射，所以键必须是可哈希和可比较的。

• 默认值参数：我们需要 default_k 和 default_v 来初始化哑元节点。这是 MoonBit 类型系统的要求，即使哑元节点不用于存储实际数据，我们也需要为它提供合法的值。

• 自引用环：我们将哑元节点的 next 和 pre 都指向自身，形成一个空的环形链表。这是一种巧妙的技巧，确保我们在链表为空时，不会遇到空指针问题。

• 返回结构体实例：使用了 MoonBit 的结构体字面量语法 { capacity, dummy, key_to_node: Map::new() } 创建并返回了 LRUCache 的实例。

为什么要形成环形结构？

你可能注意到了，我们将哑元节点的前驱和后继都指向了自身，形成了一个环。这样做的好处是：

• 不需要处理空链表的边界情况
• 插入第一个节点和之后的节点使用相同的逻辑
• 删除最后一个节点和之前的节点使用相同的逻辑

在空链表中，哑元节点既是“头“也是“尾“。当我们添加实际节点时，它们会被插入到这个环中，而哑元节点始终保持在原位，帮助我们定位链表的逻辑起点和终点。

示意图说明

初始状态下，我们的链表结构如下：

dummy ⟷ dummy (自己指向自己)

添加一个节点 A 后：

dummy ⟷ A ⟷ dummy

添加另一个节点 B（放在最近使用的位置）后：

dummy ⟷ B ⟷ A ⟷ dummy

在这个结构中，dummy.next 指向最近使用的节点（B），而 dummy.pre 指向最久未使用的节点（A）。

这样的设计为我们后面实现 get 和 put 等核心操作奠定了基础。下一步，我们将实现这些核心操作以完成 LRU 缓存的功能。