面试官：实现一个 LRU 缓存。巧用 Map 【JavaScript】

前言

大家好，我是 PakJeon.

这是一道比较常见的面试算法题。其实原理上并不难理解，但是实现细节却有很多注意的地方，特别是常规的哈希表+双向链表的实现。这次介绍一个巧妙的方法，巧用 JavaScript 内置的 Map。

什么是 LRU

LRU 缓存淘汰算法就是一种常用策略。LRU 的全称是 Least Recently Used，是一种常见的缓存算法，用于管理缓存中的数据。LRU算法的核心思想是保留最近被访问过的数据，而淘汰最久未被访问的数据。

它的工作原理如下：

初始化： 缓存被初始化为一定的容量，当缓存达到容量上限时，需要淘汰数据。
访问数据： 每次访问（读取或写入）缓存中的数据时，将该数据移动到数据结构的头部或更新其位置，表示这个数据是最近被使用的。
淘汰数据： 当缓存达到容量上限时，需要淘汰最久未被访问的数据，通常是数据结构的尾部的数据。

 1// 题目需要实现一个 LRUCache，实现以下效果，且 put、get 操作要求是时间复杂度 O(1)
 2
 3const cache = new LRUCache(2); // 创建一个容量为2的 LRU 实例
 4console.log(cache.put(1, 1)); // 返回 null   此时cache为【1】
 5console.log(cache.put(2, 2)); // 返回 null   此时cache为【2,1】
 6console.log(cache.get(1)); // 返回 1         此时cache为【1,2】，因为使用了1,1变成“新鲜的”
 7console.log(cache.put(3, 3)); // 返回 null   此时cache为【3,1】，超过容量了，把“老油条”2淘汰
 8console.log(cache.get(2)); // 返回 -1        此时cache为【3,1】
 9console.log(cache.put(4, 4)); // 返回 null   此时cache为【4,3】，超过容量了，把“老油条”1淘汰
10console.log(cache.get(1)); // 返回 -1        此时cache为【4,3】
11console.log(cache.get(3)); // 返回 3         此时cache为【3,4】
12console.log(cache.get(4)); // 返回 4         此时cache为【4,3】
13

JavaScript 中的 Map

JavaScript 中的 Map 是一种数据结构，用于存储键值对，并且不同于普通的对象， Map 的键可以是任意数据类型。前端同学对这个都不陌生，平常用到的 set、 get、 delete、 size 等 Api 相信不用再多介绍。

这次，我们利用的是 Map.prototype.keys，来解决这道算法题。

Map.prototype.keys

我们看看这个 Api 运行的结果是什么。

Jansiel_Essay_1704197194230

首先创建一个名为 cache 的 Map 实例，并设置了三个键值对，分别是 first、 second、 third。

然后调用 chache.keys()，我们得到了一个 MapIterator。顾名思义，“Map 迭代器”，它是一个迭代器，也是本次介绍解法的重点。

关于迭代器，不熟悉的同学可以参考阮一峰的 ECMAScript6 入门中关于 iterator 的介绍

MapIterator

我们知道，迭代器 iterator 有 next 方法，每次调用都会返回一个包含 value 和 done 属性的对象。 value 指的是这次迭代得到的值（在 MapIterator 这里, value 具体指的就是每个键值对的 key），而 done 是个布尔值，指的是元素是否全部迭代完毕。

Jansiel_Essay_1704197227447

不难发现， next 方法返回的顺序，正是我们往 cache 中设置键值对的顺序，这就是解决问题的关键。

利用 MapIterator

既然 MapIterator.next() 会返回第一个设置的键值对，那刚好就是我们 LRU 缓存中的 老油条。再加上 Map 的 get、 set 也都是时间复杂度O(1)，完美符合我们的需求。

LRU 框架

 1var LRUCache = function(capacity) {
 2    this.cap = capacity;
 3    this.cache = new Map();
 4};
 5
 6LRUCache.prototype.get = function(key) {
 7    // 待实现
 8    // 分两种情况：
 9    // ①：cache中不存在key，返回-1
10    // ②：cache中已存在key，返回对应的值，并把它变成“新鲜的”
11
12};
13
14LRUCache.prototype.put = function(key, val) {
15    // 待实现
16    // 分两种情况：
17    // ①：cache中已存在key，把key的值用val覆盖，并把它变成“新鲜的”；
18    // ②：cache中不存在key，再分两种情况：
19    // ②-①：cache的缓存区未满，则直接设置键值对；
20    // ②-②：cache的缓冲区已满，把“老油条”干掉，再设置键值对。
21};
22
23// 辅助方法，把参数 key 的值变成“新鲜的”
24LRUCache.prototype.makeRecently = function(key) {
25    // 待实现
26};
27

LRU 实现

有了上面的 框架 + MapIterator 的知识，剩下的就是往框架里填代码了。

 1var LRUCache = function(capacity) {
 2    this.cap = capacity;
 3    this.cache = new Map();
 4};
 5
 6LRUCache.prototype.get = function(key) {
 7    // ①：cache中不存在key，返回-1
 8    if (!this.cache.has(key)) {
 9        return -1;
10    }
11    // ②：cache中已存在key，返回对应的值，并把它变成“新鲜的”
12    this.makeRecently(key);
13    return this.cache.get(key);
14};
15
16LRUCache.prototype.put = function(key, val) {
17    // ①：cache中已存在key，把key的值用val覆盖，并把它变成“新鲜的”；
18    if (this.cache.has(key)) {
19        this.cache.set(key, value);
20        this.makeRecently(key);
21        return;
22    }
23    // ②：cache中不存在key，再分两种情况：
24    // ②-①：cache的缓存区未满，则直接设置键值对；
25    // ②-②：cache的缓冲区已满，把“老油条”干掉，再设置键值对。
26    if (this.cache.size >= this.cap) {
27        const oldestKey = this.cache.keys().next().value; // 利用MapIterator获取“老油条”
28        this.cache.delete(oldestKey);
29    }
30    this.cache.set(key, value);
31};
32
33// 辅助方法，把参数 key 的值变成“新鲜的”
34LRUCache.prototype.makeRecently = function(key) {
35    const val = this.cache.get(key); // 用变量缓存新鲜值
36    this.cache.delete(key); // 删除后再set，就会变成MapIterator的最后一项，也就是“最新鲜的”
37    this.cache.set(key, val);
38};
39

结语

希望这篇文章为你提供了对 Map 和 LRU缓存算法 的深入了解，同时也能够激发你在实际项目中灵活运用这些知识的创造力。如果你有任何问题或想要深入探讨相关主题，欢迎在评论区留言，让我们共同进步！