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
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操作。
我个人接触过的几个典型应用场景：
数据库查询结果缓存： 想象一个电商网站，热门商品的详情页被频繁访问。每次都去数据库查询会给数据库带来巨大压力。这时候，就可以把商品详情查询结果缓存起来，下次再有请求，直接从缓存里拿，大大减少数据库负载和响应时间。LRU策略能确保那些最不热门、不常被访问的商品数据被淘汰，为热门数据腾出空间。API响应缓存： 很多微服务架构中，前端或中间层会频繁调用后端API。如果某些API的响应内容在短时间内不会变化，或者变化频率很低，就可以对这些API的响应进行LRU缓存。这能显著降低网络延迟，提升用户体验，并减轻后端服务的压力。图片或静态资源缓存： 浏览器在加载网页时，会缓存图片、CSS、JS等资源。虽然浏览器有自己的缓存机制，但在一些单页应用（SPA）或桌面应用中，开发者可能需要更精细地控制资源缓存。LRU可以用来管理本地图片资源的内存缓存，确保最近被查看的图片能快速显示。函数结果记忆（Memoization）： 某些计算成本高昂但输入参数有限且结果稳定的函数，可以使用LRU缓存其结果。例如，一个复杂的数学计算函数，或者一个需要进行大量字符串处理的函数。当函数再次被调用时，如果参数相同，直接返回缓存的结果，避免重复计算。
本质上，LRU缓存就像一个“临时仓库”，它只保留那些“最有可能被再次使用”的物品。当仓库满了，它就毫不犹豫地扔掉那些“最长时间没人碰过”的物品。这种策略在很多场景下都非常符合实际需求，因为它假设“最近被访问过的数据，在未来也很有可能再次被访问”。
除了LRU，还有哪些常见的缓存淘汰策略？它们各自的适用场景是什么？
除了LRU，缓存世界里还有不少其他的淘汰策略，每种都有其特定的适用场景，就像不同的工具箱，解决不同的问题。
FIFO (First-In, First-Out，先进先出)：
策略： 最简单粗暴的一种。缓存满了，就淘汰最早进入缓存的那个数据。它完全不考虑数据的访问频率或最近性。适用场景： 简单实现，对数据访问模式没有特定假设时。比如日志队列、消息队列，或者某些一次性读取的数据流。但缺点也很明显，如果一个数据虽然很老，但被频繁访问，它也可能被无情淘汰。
LFU (Least Frequently Used，最不常用)：
策略： 淘汰访问次数最少的数据。它会为每个缓存项维护一个访问计数器，每次访问就加1。缓存满了时，淘汰计数器最小的那个。适用场景： 数据访问频率分布极不均匀，少数数据被极度频繁访问，而大多数数据很少被访问。比如，统计报表数据、热门新闻文章等。挑战： 实现起来比LRU复杂，因为不仅要追踪顺序，还要追踪频率。而且，一个在初期被大量访问但后来不再被访问的数据，其计数器可能仍然很高，导致它长时间不被淘汰，这被称为“缓存污染”问题。
ARC (Adaptive Replacement Cache，自适应替换缓存)：
策略： 这是IBM研究员发明的一种结合了LRU和LFU优点的策略。它维护两个LRU列表，一个用于最近访问的，一个用于最近被淘汰但后来又被访问的（幽灵列表）。ARC会根据缓存命中率动态调整两个列表的大小，从而自适应地在LRU和LFU之间进行平衡。适用场景： 对缓存命中率要求极高，且数据访问模式复杂多变，难以预测的场景。比如数据库系统、文件系统等。挑战： 实现非常复杂，通常只在大型系统中使用。
MRU (Most Recently Used，最近最常使用)：
策略： 淘汰最近被访问过的那个数据。这听起来有点反直觉，和LRU完全相反。适用场景： 极少数特定场景。例如，当数据被访问后，其再次被访问的概率反而很低时（比如一次性读取的数据流），或者处理扫描型工作负载时，你希望把那些已经处理过的数据尽快清除掉。
选择哪种策略，说到底，就是根据你的数据访问模式和对性能、内存的权衡来决定的。LRU之所以流行，是因为它在大多数通用场景下都表现良好，并且实现相对简单高效。
以上就是JS如何实现LRU缓存？LRU的淘汰策略的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1515287.html
微信扫一扫 
支付宝扫一扫 
