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

,LRU 缓存算法是一个非常经典的算法，在很多面试中经常问道，不仅仅包括前端面试。,LRU 英文全称是 Least Recently Used，英译过来就是”最近最少使用“的意思。 它是页面置换算法中的一种，我们先来看一段百度百科的解释。,百度百科：,百度百科解释的比较窄，它这里只使用了页面来举例，我们通俗点来说就是：假如我们最近访问了很多个页面，内存把我们最近访问的页面都缓存了起来，但是随着时间推移，我们还在不停的访问新页面，这个时候为了减少内存占用，我们有必要删除一些页面，而删除哪些页面呢？我们可以通过访问页面的时间来决定，或者说是一个标准：在最近时间内，最久未访问的页面把它删掉。,百度百科的解释只是单纯的解释算法，而我们这里可以结合我们的前端和实际应用场景来给大家解释一下。,虽然上面的解释比较好懂了，但是我们还有很多地方没有考虑到，比如如下几点：,最后我们在上一张图，大家应该就更容易理解了，如下图：,,上图就很好的解释了 LRU 算法在干嘛了，其实非常简单，无非就是我们往内存里面添加或者删除元素的时候，遵循最近最少使用原则。,LRU 算法使用的场景非常多，这里简单举几个例子即可：,,总之 LRU 算法的运用场景还是蛮多的，所以我们很有必要掌握它。,我们学习了 LRU 算法的基本概念和使用场景之后，那么我们就应该考虑如何实现它了。要想实现一个算法，我们很有必要梳理一下思路，这样才能让我们更好更快的编写出代码。,首先我们来梳理一下 LRU 算法的特点。,特点分析：,实现需求：,现在我们已经把 LRU 算法的特点以及实现思路列了出来，那么接下来就然我们一起去实现它吧！,首先我们定义一个 LRUCache 类，封装所有的方法和变量。,代码如下：,上段代码只是我们最简单的一个架子，我们需要去实现具体的 get 和 set 方法。,代码如下：,上段代码中实现实现了 get 和 set 方法，下面说一下这两个方法的实现思路：,接下来我们使用一些测试用例来试试行不行。,输出结果：,,继续插入数据，此时会超长，代码如下：,输出结果：,,此时我们发现存储时间最久的 name 已经被移除了，新插入的数据变为了最前面的一个。,我们使用 get 获取数据，代码如下：,输出结果：,,我们发现此时 sex 字段已经跑到最前面去了。,LRU 算法其实逻辑非常的简单，明白了原理之后实现起来非常的简单。最主要的是我们需要使用什么数据结构来存储数据，因为 map 的存取非常快，所以我们采用了它，当然数组其实也可以实现的。还有一些小伙伴使用链表来实现 LRU，这当然也是可以的。