面试官：请使用JS完成一个LRU缓存？

发布时间：2025-11-03 12:46:31 来源：创站工坊 作者：应用开发

前言

LRU 缓存算法是面试一个非常经典的算法，在很多面试中经常问道，官请个不仅仅包括前端面试。使用

1.什么是完成 LRU？

LRU 英文全称是 Least Recently Used，英译过来就是缓存”最近最少使用“的意思。 它是面试页面置换算法中的一种，我们先来看一段百度百科的官请个解释。

百度百科：

百度百科解释的缓存比较窄，它这里只使用了页面来举例，我们通俗点来说就是：假如我们最近访问了很多个页面，b2b信息网内存把我们最近访问的页面都缓存了起来，但是随着时间推移，我们还在不停的访问新页面，这个时候为了减少内存占用，我们有必要删除一些页面，而删除哪些页面呢？我们可以通过访问页面的时间来决定，或者说是一个标准：在最近时间内，最久未访问的页面把它删掉。

百度百科的解释只是单纯的解释算法，而我们这里可以结合我们的前端和实际应用场景来给大家解释一下。

虽然上面的解释比较好懂了，但是我们还有很多地方没有考虑到，比如如下几点：

最后我们在上一张图，大家应该就更容易理解了，如下图：

上图就很好的解释了 LRU 算法在干嘛了，其实非常简单，无非就是我们往内存里面添加或者删除元素的时候，遵循最近最少使用原则。

2.使用场景

LRU 算法使用的场景非常多，这里简单举几个例子即可：

总之 LRU 算法的运用场景还是源码下载蛮多的，所以我们很有必要掌握它。

3.梳理实现 LRU 思路

我们学习了 LRU 算法的基本概念和使用场景之后，那么我们就应该考虑如何实现它了。要想实现一个算法，我们很有必要梳理一下思路，这样才能让我们更好更快的编写出代码。

首先我们来梳理一下 LRU 算法的特点。

特点分析：

实现需求：

现在我们已经把 LRU 算法的特点以及实现思路列了出来，那么接下来就然我们一起去实现它吧！

4.具体实现

首先我们定义一个 LRUCache 类，封装所有的方法和变量。

代码如下：

class LRUCache {

constructor(lenght) {

this.length = lenght; // 存储长度

this.data = new Map(); // 存储数据

}

// 存储数据，通过键值对的方式

set(key, value) { }

// 获取数据

get(key) { }

}

const lruCache = new LRUCache(5);

上段代码只是我们最简单的一个架子，我们需要去实现具体的 get 和 set 方法。

代码如下：

class LRUCache {

constructor(lenght) {

this.length = lenght; // 存储长度

this.data = new Map(); // 存储数据

}

// 存储数据，通过键值对的方式

set(key, value) {

const data = this.data;

if (data.has(key)) {

data.delete(key)

}

data.set(key, value);

// 如果超出了容量，则需要删除最久的数据

if (data.size > this.length) {

const delKey = data.keys().next().value;

data.delete(delKey);

}

}

// 获取数据

get(key) {

const data = this.data;

// 未找到

if (!data.has(key)) {

return null;

}

const value = data.get(key); // 获取元素

data.delete(key); // 删除元素

data.set(key, value); // 重新插入元素

}

}

const lruCache = new LRUCache(5);

上段代码中实现实现了 get 和 set 方法，下面说一下这两个方法的实现思路：

接下来我们使用一些测试用例来试试行不行。

存储数据 set：lruCache.set(name, 小猪课堂);

lruCache.set(age, 22);

lruCache.set(sex, 男);

lruCache.set(height, 176);

lruCache.set(weight, 100);

输出结果：

继续插入数据，此时会超长，代码如下：

lruCache.set(grade, 10000);

输出结果：

此时我们发现存储时间最久的 name 已经被移除了，新插入的数据变为了最前面的一个。

我们使用 get 获取数据，代码如下：

lruCache.get(sex);

输出结果：

我们发现此时 sex 字段已经跑到最前面去了。

总结

LRU 算法其实逻辑非常的简单，明白了原理之后实现起来非常的简单。最主要的是我们需要使用什么数据结构来存储数据，因为 map 的存取非常快，所以我们采用了它，当然数组其实也可以实现的。还有一些小伙伴使用链表来实现 LRU，这当然也是可以的。

相关文章