JS如何实现LRU缓存？LRU的淘汰策略

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

JS实现LRU缓存，核心在于利用JavaScript

Map

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

Object

首先，

Object

Map

更关键的区别在于，

Map

Map

Map.keys()

Map.values()

Map.entries()

Map

反观

Object

Object

Map

Object

Map

delete

set

get

put

所以，综合来看，

Map

Object

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

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

GPTKit

一个AI文本生成检测工具

108

查看详情

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

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缓存？LRU的淘汰策略的详细内容，更多请关注php中文网其它相关文章！