Blog. 用 MoonBit 实现 LRU 缓存算法 [blog/lrualgorithm]
Blog. 用 MoonBit 实现 LRU 缓存算法 [blog/lrualgorithm]
大家好！今天我想和大家分享如何用 MoonBit 语言实现一个 LRU（Least Recently Used，最近最少使用）缓存算法。无论你是刚接触 MoonBit，还是想了解 LRU 算法的实现细节，这篇文章都会带你深入了解这个经典而实用的算法。 什么是 LRU 缓存？ LRU 缓存是一种常见的缓存淘汰策略，它基于一个简单的假设：最近访问过的数据在不久的将来很可能再次被访问。因此，当缓存空间不足需要淘汰数据时，应该优先淘汰最长时间未被访问的数据。 一个日常生活的例子 想象你的书桌上只能放 5 本书。每次你需要一本新书，但书桌已满时，你会把哪本书放回书架？最合理的选择是把最久没看的那本书放回去。这就是 LRU 策略的直观体现。 技术应用场景 LRU 缓存在计算机系统中有广泛的应用： LRU 缓存的实际例子 假设我们有一个容量为 3 的 LRU 缓存，初始为空。现在执行以下操作： 通过这个例子，我们可以看到 LRU 缓存如何维护“最近使用“的顺序，以及如何在缓存满时进行淘汰。 LRU 缓存的核心操作 一个标准的 LRU 缓存需要支持以下两个核心操作： get(key): 获取缓存中键对应的值 put(key, value): 向缓存中插入或更新键值对 这两个操作的时间复杂度都应该是 O(1)，这就需要我们精心设计数据结构。 为什么需要特殊的数据结构？ 实现一个高效的 LRU 缓存面临两个主要挑战： 如果只用数组，查找需要 O(n) 时间；如果只用哈希表，无法跟踪使用顺序。因此，我们需要结合两种数据结构。 实现思路：哈希表 + 双向链表 LRU 缓存的经典实现方式是结合使用： 这种组合让我们能够同时满足快速查找和顺序维护的需求。 接下来，我们将用 MoonBit 语言一步步实现这个数据结构，从基础的节点定义，到完整的 LRU 缓存功能。 1. LRU 缓存简介 [blog/lrualgorithm/whats]
put(1, "一") → 缓存现状：[(1, “一”)]put(2, "二") → 缓存现状：[(2, “二”), (1, “一”)]put(3, "三") → 缓存现状：[(3, “三”), (2, “二”), (1, “一”)]get(1) → 返回 “一”，缓存现状：[(1, “一”), (3, “三”), (2, “二”)] (注意 1 被移到了最前面)put(4, "四") → 缓存已满，淘汰最久未使用的 (2, “二”)，缓存现状：[(4, “四”), (1, “一”), (3, “三”)]get(2) → 返回 None (不存在)
在实现 LRU 缓存之前，我们首先需要定义一些基础的数据结构。正如前面所说，我们需要结合哈希表和双向链表来实现高效的 LRU 缓存。 节点结构 我们先定义双向链表的节点结构。每个节点需要存储键值对，并且包含指向前一个和后一个节点的引用： 在这个节点结构中有几个有趣的 MoonBit 特性值得我们关注： 泛型参数 可变字段 可选类型 简单构造函数： LRU 缓存结构 接下来，我们来定义 LRU 缓存的主体结构： 这个结构包含三个关键字段： capacity：定义了缓存可以存储的最大键值对数量。 dummy：一个特殊的哑元节点，不存储实际的键值对，而是用来简化链表操作。使用哑元节点是一个常见的编程技巧，它可以帮助我们避免处理空链表和边界条件的特殊情况。 key_to_node：一个从键到节点的映射表，使我们能够在 O(1) 时间内通过键找到对应的节点。 为什么使用哑元节点？ 哑元节点的使用是一个很巧妙的设计。我们将在链表中使用一个环形结构，其中哑元节点同时充当链表的“头“和“尾“： 这样的设计使得我们在处理节点插入和删除时，不必担心空链表的特殊情况，代码逻辑会更加统一和清晰。 通过这两个基础数据结构，我们已经为实现一个高效的 LRU 缓存打下了基础。在下一部分，我们将开始实现 LRU 缓存的构造函数和核心操作。 2. 定义基础数据结构 [blog/lrualgorithm/define]
// 定义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 }
}
[K, V]：这使得我们的 LRU 缓存可以适用于任何类型的键和值，非常灵活。mut：value、pre 和 next 都被标记为 mut，意味着它们可以在创建后修改。这对于我们需要频繁调整链表结构的 LRU 缓存来说是必须的。?：pre 和 next 是可选类型，表示它们可能为 None。这样处理链表两端的节点会更加自然。new_node 函数帮助我们创建一个新节点，初始状态下前驱和后继都是 None。// LRU缓存结构体
struct LRUCache[K, V] {
capacity : Int // 容量
dummy : Node[K, V] // 哑节点，用于标记双向链表的头尾
key_to_node : Map[K, Node[K, V]] // 键到节点的映射
}
dummy.next 指向链表中最近使用的节点（实际的第一个节点）dummy.pre 指向链表中最久未使用的节点（实际的最后一个节点）
现在我们已经定义好了基础数据结构，接下来需要实现 LRU 缓存的构造函数。构造函数是任何数据结构的起点，它负责正确初始化内部状态。 构造函数的设计 在设计 LRU 缓存的构造函数时，我们需要考虑： 让我们看看如何用 MoonBit 实现这个构造函数： 这段代码做了几件重要的事情： 泛型约束：注意 默认值参数：我们需要 自引用环：我们将哑元节点的 返回结构体实例：使用了 MoonBit 的结构体字面量语法 为什么要形成环形结构？ 你可能注意到了，我们将哑元节点的前驱和后继都指向了自身，形成了一个环。这样做的好处是： 在空链表中，哑元节点既是“头“也是“尾“。当我们添加实际节点时，它们会被插入到这个环中，而哑元节点始终保持在原位，帮助我们定位链表的逻辑起点和终点。 示意图说明 初始状态下，我们的链表结构如下： 添加一个节点 A 后： 添加另一个节点 B（放在最近使用的位置）后： 在这个结构中， 这样的设计为我们后面实现 3. 构造函数实现 [blog/lrualgorithm/construction]
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 都指向自身，形成一个空的环形链表。这是一种巧妙的技巧，确保我们在链表为空时，不会遇到空指针问题。{ capacity, dummy, key_to_node: Map::new() } 创建并返回了 LRUCache 的实例。
dummy ⟷ dummy (自己指向自己)
dummy ⟷ A ⟷ dummy
dummy ⟷ B ⟷ A ⟷ dummy
dummy.next 指向最近使用的节点（B），而 dummy.pre 指向最久未使用的节点（A）。get 和 put 等核心操作奠定了基础。下一步，我们将实现这些核心操作以完成 LRU 缓存的功能。
接下来我们要实现 LRU 缓存的两个核心操作： get 方法实现 这个实现看起来很简单，但它内部调用了 这里我们用到了两个辅助方法 put 方法实现 检查键是否已存在： 创建新节点： 添加到链表和哈希表： 检查容量并可能淘汰： LRU 算法的核心思想 通过这两个方法，我们可以看到 LRU 算法的核心思想： 这种设计确保了我们总是保留最有可能再次被访问的数据，而丢弃最不可能再次被访问的数据，从而最大化缓存的命中率。 在下一部分，我们将详细介绍 4. 核心操作 - get 和 put [blog/lrualgorithm/core]
get 和 put。这两个操作是 LRU 缓存的精髓所在，也是最常用的接口。get 方法用于从缓存中获取某个键对应的值。如果键存在，它还需要将对应的节点移到“最近使用“的位置：fn get[K : Hash + Eq, V](self : LRUCache[K, V], key : K) -> V? {
let node = get_node(self, key)
match node {
Some(n) => Some(n.value)
None => None
}
}
get_node 方法，这个方法不仅查找节点，还负责调整节点位置。下面是 get_node 的实现：fn get_node[K : Hash + Eq, V](self : LRUCache[K, V], key : K) -> Node[K, V]? {
if self.key_to_node.contains(key) {
if self.key_to_node.get(key) is Some(node) {
// 将节点移到链表前端
remove(self, node)
push_front(self, node)
return Some(node)
}
}
None
}
get_node 方法做了几件重要的事：
remove 和 push_front（后面会详细介绍），它们负责链表的具体操作。put 方法用于向缓存中添加或更新键值对：fn put[K : Hash + Eq, V](self : LRUCache[K, V], key : K, value : V) -> Unit {
// 如果键已存在，更新值并移到链表前端
let existing = get_node(self, key)
if existing is Some(node) {
node.value = value
return
}
// 创建新节点
let node = new_node(key, value)
// 将新节点加入链表前端
push_front(self, node)
self.key_to_node.set(key, node)
// 如果超出容量，删除最久未使用的节点
if self.key_to_node.size() > self.capacity {
if self.dummy.pre is Some(last_node) {
self.key_to_node.remove(last_node.key)
remove(self, last_node)
}
}
}
put 方法的逻辑分为几个部分：
get_node 方法）get_node 已经将节点移到了链表前端
dummy.pre）指向的节点
push_front 和 remove 这两个关键的辅助方法，它们是实现 LRU 缓存链表操作的基础。
在上一部分中，我们实现了 LRU 缓存的核心操作 push_front 方法实现 这个方法的逻辑虽然只有几行，但需要仔细理解： 通过这四步，我们完成了在链表头部插入新节点的操作。注意我们使用了 remove 方法实现 这个方法的实现非常直观： 通过这两步，节点就从链表中“断开“了，不再是链表的一部分。 为什么这两个操作如此重要？ 这两个看似简单的操作是整个 LRU 缓存算法的关键： 通过这两个基本操作，我们能够维护一个按照“最近使用“到“最久未使用“排序的双向链表，从而实现 LRU 缓存的核心功能。 双向链表操作的细节 在处理双向链表时，容易出现的错误是指针操作顺序不当导致链表断裂或形成环。我们的实现避免了这些问题： 这种实现方式确保了链表操作的安全性和正确性。 使用哑元节点的优势 回顾一下我们设计中使用的哑元节点（dummy node），它带来了以下优势： 有了这些辅助操作，我们的 LRU 缓存算法就更加完整了。接下来，我们会添加一些额外的实用方法，让我们的 LRU 缓存更加易用。 5. 辅助操作 - push_front 和 remove [blog/lrualgorithm/auxiliary]
get 和 put，但它们都依赖于两个关键的辅助方法：push_front 和 remove。这两个方法负责维护双向链表的结构，是整个 LRU 算法能够正常工作的基础。push_front 方法用于将一个节点插入到链表的最前端（即最近使用的位置）：fn push_front[K, V](self : LRUCache[K, V], node : Node[K, V]) -> Unit {
node.next = self.dummy.next
node.pre = Some(self.dummy)
if node.pre is Some(pre) {
pre.next = Some(node)
}
if node.next is Some(next) {
next.pre = Some(node)
}
}
next 指向原来的第一个节点（即 dummy.next）pre 指向哑元节点next 指向新节点pre 指向新节点is Some 模式匹配来安全地处理可选值，这是 MoonBit 处理空值的一种优雅方式。remove 方法用于从链表中删除一个节点：fn remove[K, V](self : LRUCache[K, V], node : Node[K, V]) -> Unit {
if node.pre is Some(pre) {
pre.next = node.next
}
if node.next is Some(next) {
next.pre = node.pre
}
}
next 指向节点的下一个节点pre 指向节点的前一个节点
push_front 确保最近访问的项总是位于链表的前端remove 用于两个场景：
push_front 中，我们先设置新节点的指针，再更新相邻节点的指针remove 中，我们直接更新相邻节点的指针，跳过要删除的节点
我们已经实现了 LRU 缓存的核心功能，包括基本数据结构、构造函数、核心操作 获取缓存大小 首先，我们实现一个方法来获取当前缓存中的元素数量： 这个方法非常简单，直接返回哈希表的大小，因为哈希表中的每一项都对应缓存中的一个元素。 检查缓存是否为空 接下来，我们添加一个方法来检查缓存是否为空： 这个方法检查哈希表是否为空，从而判断整个缓存是否为空。 检查键是否存在 最后，我们实现一个方法来检查缓存中是否存在某个键： 这个方法直接利用哈希表的 这些辅助方法的意义 虽然这些方法看起来很简单，但它们对于实际使用 LRU 缓存非常有价值： 这些辅助方法体现了良好的 API 设计原则 —— 简单、一致且易于使用。通过提供这些方法，我们的 LRU 缓存实现更加健壮和用户友好。 实际应用示例 这些辅助方法在实际应用中非常有用，例如： 这些方法虽然简单，但它们大大增强了 LRU 缓存的实用性。通过这些辅助方法，我们的 LRU 缓存实现已经相当完整和实用。 6. 实用辅助方法 [blog/lrualgorithm/auxiliary-other]
get/put 以及链表操作的辅助方法。为了让我们的 LRU 缓存更加完整和易用，现在我们来添加一些实用的辅助方法。fn size[K, V](self : LRUCache[K, V]) -> Int {
self.key_to_node.size()
}
fn is_empty[K, V](self : LRUCache[K, V]) -> Bool {
self.key_to_node.size() == 0
}
fn contains[K : Hash + Eq, V](self : LRUCache[K, V], key : K) -> Bool {
self.key_to_node.contains(key)
}
contains 方法，快速判断一个键是否在缓存中。
is_empty() 比 size() == 0 更直观key_to_node 哈希表// 检查键是否存在，而不获取值（避免改变使用顺序）
if contains(cache, "key") {
// 键存在，可以进行一些操作
}
// 缓存为空时执行特定逻辑
if is_empty(cache) {
// 缓存为空，可以执行初始化或其他操作
}
// 获取缓存使用情况
let usage_percentage = size(cache) * 100 / cache.capacity
终于到了我们 LRU 缓存实现之旅的终点。这一路走来，我们从基本概念开始，一步步构建了一个完整的 LRU 缓存。说实话，当我第一次接触 LRU 算法时，就被它简单而优雅的设计所吸引。在实现过程中，我不仅体会到了算法的精妙之处，也感受到了 MoonBit 语言的表达力。 回顾整个实现过程，我最满意的是数据结构的选择。哈希表和双向链表的组合虽然是经典方案，但在 MoonBit 中实现时，语言本身的特性让代码显得格外简洁。特别是哑元节点的使用，解决了链表操作中的边界情况，让代码逻辑更加一致。这种小技巧看似简单，却能大幅简化实现，减少潜在的错误。 在编写过程中，我发现 MoonBit 的类型系统非常适合这类数据结构的实现。泛型让我们的缓存可以适用于各种类型的键值对，而可选类型（Option 类型）则优雅地处理了可能不存在的值的情况。与其他语言相比，不必担心空指针异常是一种解脱，让我可以更专注于算法本身的逻辑。 对我而言，编写 说到实际应用，这种 LRU 缓存在日常开发中其实非常实用。我曾在一个网页应用中使用类似的缓存来存储频繁访问的数据，显著提升了应用响应速度。见过太多项目因为缺乏合理的缓存策略而性能低下，一个好的 LRU 实现往往能起到事半功倍的效果。 当然，这个实现还有改进空间。比如添加线程安全支持，或者引入基于时间的过期策略。在实际项目中，我会考虑根据具体需求扩展这些功能。不过，目前的实现已经涵盖了 LRU 缓存的核心功能，足以应对大多数场景。 我最大的收获可能是深入理解了算法与数据结构如何相互配合。LRU 缓存的优雅之处在于它巧妙地结合了两种数据结构，各取所长，达到了理想的性能。这种思路启发我在面对其他问题时，不要局限于单一的数据结构，而是思考如何组合现有工具来获得最佳解决方案。 最后，希望这个 LRU 缓存的实现过程对你有所帮助。无论你是在学习 MoonBit 语言，还是想深入了解缓存算法，我都希望这篇文章能给你一些启发。编程的乐趣不仅在于解决问题，还在于创造优雅的解决方案。在这个意义上，LRU 缓存是一个小巧而完美的例子。 如果你有任何问题或改进建议，欢迎在 Github 留言讨论。毕竟，代码和思想总是在交流中不断完善的。 7. 总结与思考 [blog/lrualgorithm/summary]
get 和 put 方法是最有趣的部分。这两个方法看似简单，却包含了 LRU 算法的核心思想：每次访问都要更新使用顺序，确保最近使用的项目保留在缓存中。当我看到这些方法能够正确工作时，那种成就感是难以形容的。