JS实现LRU缓存算法及淘汰机制解析

一分耕耘，一分收获！既然打开了这篇文章《JS实现LRU缓存及淘汰策略解析》，就坚持看下去吧！文中内容包含等等知识点...希望你能在阅读本文后，能真真实实学到知识或者帮你解决心中的疑惑，也欢迎大佬或者新人朋友们多留言评论，多给建议！谢谢！

JS实现LRU缓存的核心是利用Map对象的插入顺序特性，通过在每次访问或更新时将键值对重新插入Map末尾，使Map头部始终为最近最少使用的数据，当缓存满时删除头部元素即可实现LRU策略，该方案具有O(1)的时间复杂度，优于使用Object的实现，广泛应用于数据库查询缓存、API响应缓存、静态资源管理和函数结果记忆等场景，以提升性能并减少重复开销。

JS实现LRU缓存，核心在于利用JavaScript Map对象的特性来维护键值对的存储和访问顺序。LRU（Least Recently Used）的淘汰策略，顾名思义，就是当缓存达到容量上限时，优先淘汰最近最少使用的那个数据项。Map天然保留了插入顺序，这让我们在操作时能非常方便地追踪“新旧”状态，每次访问或更新一个键，我们就把它“移动”到Map的末尾，这样Map的头部就始终是最近最少使用的那个。

解决方案

要构建一个高效的LRU缓存，我们通常会封装一个类。这个类需要一个Map来存储数据，并记录缓存的最大容量。

class LRUCache {
    constructor(capacity) {
        this.cache = new Map();
        this.capacity = capacity;
    }

    get(key) {
        if (!this.cache.has(key)) {
            return -1; // 或者 null/undefined，表示未找到
        }

        // 获取值并更新其在Map中的位置，使其成为最近使用的
        const value = this.cache.get(key);
        this.cache.delete(key);
        this.cache.set(key, value);
        return value;
    }

    put(key, value) {
        // 如果key已存在，先删除旧的，再插入新的，确保其在Map末尾（最近使用）
        if (this.cache.has(key)) {
            this.cache.delete(key);
        } else if (this.cache.size >= this.capacity) {
            // 如果缓存已满，且key不存在，则淘汰最近最少使用的（Map的第一个元素）
            // Map的keys()迭代器会按照插入顺序返回键
            const oldestKey = this.cache.keys().next().value;
            this.cache.delete(oldestKey);
        }
        // 插入或更新新值，使其成为最近使用的
        this.cache.set(key, value);
    }

    // 辅助方法，用于查看缓存内容，非LRU核心功能
    peek() {
        return Array.from(this.cache.entries());
    }
}

// 示例用法：
// const lruCache = new LRUCache(3);
// lruCache.put('a', 1); // cache: {a: 1}
// lruCache.put('b', 2); // cache: {a: 1, b: 2}
// lruCache.put('c', 3); // cache: {a: 1, b: 2, c: 3}
// console.log(lruCache.get('b')); // 2; cache: {a: 1, c: 3, b: 2} - b被访问，移到末尾
// lruCache.put('d', 4); // cache: {c: 3, b: 2, d: 4} - a被淘汰，因为它是最近最少使用的
// console.log(lruCache.peek()); // [[c, 3], [b, 2], [d, 4]]

这段代码的核心思想是：无论是get还是put操作，只要一个键被访问或更新，我们就把它从Map中删除，然后重新插入。由于Map会保持元素的插入顺序，重新插入就意味着它现在是“最新”的，被放在了Map的末尾。当缓存满了需要淘汰时，我们只需要删除Map中的第一个元素，因为它就是最老的、最近最少使用的。

Map与Object在实现LRU缓存时有何不同？为何推荐使用Map？

在我看来，选择Map来构建LRU缓存几乎是JS里最自然、最高效的方案，尤其是在现代JavaScript环境中。如果你尝试用普通的Object来做，会发现那简直是自找麻烦。

首先，Object的键默认都是字符串类型，即使你传入数字，它也会被隐式转换为字符串。而Map则允许你使用任意类型作为键，包括对象、函数等，这在某些场景下提供了更大的灵活性。

更关键的区别在于，Map能够可靠地保持元素的插入顺序。这一点对于LRU缓存至关重要！我们正是利用了Map的这个特性来追踪“最近使用”的状态。当你通过Map.keys()、Map.values()或Map.entries()进行迭代时，它们会按照元素被插入的顺序返回。这意味着Map的第一个元素总是最老的（最近最少使用的），而最后一个元素总是最新的（最近使用的）。

反观Object，虽然ES2015之后，Object的属性迭代顺序也有了规范（整数键按升序，其他键按插入顺序），但它的操作远不如Map灵活。要实现LRU的“移动到末尾”操作，你可能需要手动维护一个额外的数组或链表来跟踪顺序，这会大大增加代码的复杂度和维护成本。比如，你需要遍历Object的键来找到最老的那个，然后删除它，这可不是O(1)的操作。而Map的delete和set操作都是接近O(1)的，这使得LRU缓存的get和put操作都能保持高效的O(1)时间复杂度。

所以，综合来看，Map在键类型、顺序保持和操作效率上都完胜Object，是实现LRU缓存的理想选择。

LRU缓存的实际应用场景有哪些？它能解决什么问题？

LRU缓存的用处非常广泛，简直是性能优化和资源管理的好帮手。它主要解决的问题是：如何在有限的内存空间内，尽可能地提升数据访问速度，减少重复计算或IO操作。

我个人接触过的几个典型应用场景：

1. 数据库查询结果缓存： 想象一个电商网站，热门商品的详情页被频繁访问。每次都去数据库查询会给数据库带来巨大压力。这时候，就可以把商品详情查询结果缓存起来，下次再有请求，直接从缓存里拿，大大减少数据库负载和响应时间。LRU策略能确保那些最不热门、不常被访问的商品数据被淘汰，为热门数据腾出空间。
2. API响应缓存： 很多微服务架构中，前端或中间层会频繁调用后端API。如果某些API的响应内容在短时间内不会变化，或者变化频率很低，就可以对这些API的响应进行LRU缓存。这能显著降低网络延迟，提升用户体验，并减轻后端服务的压力。
3. 图片或静态资源缓存： 浏览器在加载网页时，会缓存图片、CSS、JS等资源。虽然浏览器有自己的缓存机制，但在一些单页应用（SPA）或桌面应用中，开发者可能需要更精细地控制资源缓存。LRU可以用来管理本地图片资源的内存缓存，确保最近被查看的图片能快速显示。
4. 函数结果记忆（Memoization）： 某些计算成本高昂但输入参数有限且结果稳定的函数，可以使用LRU缓存其结果。例如，一个复杂的数学计算函数，或者一个需要进行大量字符串处理的函数。当函数再次被调用时，如果参数相同，直接返回缓存的结果，避免重复计算。

本质上，LRU缓存就像一个“临时仓库”，它只保留那些“最有可能被再次使用”的物品。当仓库满了，它就毫不犹豫地扔掉那些“最长时间没人碰过”的物品。这种策略在很多场景下都非常符合实际需求，因为它假设“最近被访问过的数据，在未来也很有可能再次被访问”。

除了LRU，还有哪些常见的缓存淘汰策略？它们各自的适用场景是什么？

除了LRU，缓存世界里还有不少其他的淘汰策略，每种都有其特定的适用场景，就像不同的工具箱，解决不同的问题。

1. FIFO (First-In, First-Out，先进先出)：

   • 策略： 最简单粗暴的一种。缓存满了，就淘汰最早进入缓存的那个数据。它完全不考虑数据的访问频率或最近性。
   • 适用场景： 简单实现，对数据访问模式没有特定假设时。比如日志队列、消息队列，或者某些一次性读取的数据流。但缺点也很明显，如果一个数据虽然很老，但被频繁访问，它也可能被无情淘汰。

2. LFU (Least Frequently Used，最不常用)：

   • 策略： 淘汰访问次数最少的数据。它会为每个缓存项维护一个访问计数器，每次访问就加1。缓存满了时，淘汰计数器最小的那个。
   • 适用场景： 数据访问频率分布极不均匀，少数数据被极度频繁访问，而大多数数据很少被访问。比如，统计报表数据、热门新闻文章等。
   • 挑战： 实现起来比LRU复杂，因为不仅要追踪顺序，还要追踪频率。而且，一个在初期被大量访问但后来不再被访问的数据，其计数器可能仍然很高，导致它长时间不被淘汰，这被称为“缓存污染”问题。

3. ARC (Adaptive Replacement Cache，自适应替换缓存)：

   • 策略： 这是IBM研究员发明的一种结合了LRU和LFU优点的策略。它维护两个LRU列表，一个用于最近访问的，一个用于最近被淘汰但后来又被访问的（幽灵列表）。ARC会根据缓存命中率动态调整两个列表的大小，从而自适应地在LRU和LFU之间进行平衡。
   • 适用场景： 对缓存命中率要求极高，且数据访问模式复杂多变，难以预测的场景。比如数据库系统、文件系统等。
   • 挑战： 实现非常复杂，通常只在大型系统中使用。

4. MRU (Most Recently Used，最近最常使用)：

   • 策略： 淘汰最近被访问过的那个数据。这听起来有点反直觉，和LRU完全相反。
   • 适用场景： 极少数特定场景。例如，当数据被访问后，其再次被访问的概率反而很低时（比如一次性读取的数据流），或者处理扫描型工作负载时，你希望把那些已经处理过的数据尽快清除掉。

选择哪种策略，说到底，就是根据你的数据访问模式和对性能、内存的权衡来决定的。LRU之所以流行，是因为它在大多数通用场景下都表现良好，并且实现相对简单高效。

到这里，我们也就讲完了《JS实现LRU缓存算法及淘汰机制解析》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于的知识点！