前言LRU缓存算法是一个非常经典的算法，很多面试都会经常被问到，不仅仅是前端面试。小伙伴们，如果你看过Leetcode算法题，相信你一定遇到过LRU算法题，那么LRU算法是一种什么样的算法呢？今天就给大家好好讲讲，顺便用JS实现一下！1.什么是LRU？LRU的英文全称是LeastRecentlyUsed，英文翻译就是“最近最少使用”的意思。它是页面替换算法之一。我们先来看百度百科的一段解释。百度百科：LRU是一种常用的页面置换算法，选择最近未使用的页面进行淘汰。该算法为每个页面提供一个访问字段，用于记录自上次访问页面以来经过的时间。当需要淘汰一个页面时，选择现有页面中t值最大的那个，也就是最近最少使用的那个。该页面被删除。百度百科的解释比较狭隘。这里仅以页面为例。通俗地说就是：如果我们最近访问了很多页面，那么内存会缓存我们最近访问过的所有页面，但是随着时间的推移，我们还在不停地访问新的页面。这时候为了减少内存占用，我们需要删除一些页面，到底应该删除哪些页面呢？我们可以通过访问页面的时间来决定，或者一个标准：在最近的时间里，最长时间没有访问的页面将被删除。百度百科的解释只是对算法的简单解释，我们可以结合我们前端和实际应用场景给大家解释。通俗解释：如果我们有一块内存专门用来缓存我们最近访问过的网页，当我们访问一个新的网页时，我们会在内存中添加一个网页地址。随着网页数量的不断增加，内存已经满了，这时就需要考虑删除一些网页了。这时候我们在内存中找到最先访问的网页地址，然后删除。这整个过程可以称为LRU算法。上面的解释虽然比较通俗易懂，但是还是有很多地方我们没有考虑到，比如以下几点：当我们访问一个已经存在于内存中的URL时，这个URL是否需要按照在内存中的存储顺序进行更新记忆。当我们内存中没有数据的时候，是否需要进行删除操作。最后我们上一张图，大家应该更容易理解，如下图所示：上图很好的解释了LRU算法是干什么的。其实很简单。无非就是我们在内存中添加或者删除元素的时候，遵循最近最少使用原则。2.场景使用LRU算法的场景有很多。下面举几个简单的例子：我们操作系统底层的内存管理，包括我们常见的缓存服务，采用LRU算法，比如redis等，比如最近的浏览器。浏览记录存储，如下图所示：总之，LRU算法的应用场景还是挺多的，所以我们有必要去掌握它。3.梳理LRU的实现思路我们了解了LRU算法的基本概念和使用场景之后，接下来就要考虑如何实现了。实现一个算法，需要我们理清思路，这样才能更好更快的写出代码。首先我们来梳理一下LRU算法的特点。特征分析：我们需要一个有限的存储空间，因为存储空间是无限的，所以不需要使用LRU去计算和删除数据。我们的存储空间存储的数据需要是有序的，因为我们必须按顺序删除数据，所以可以考虑使用Array和Map数据结构进行存储，而不能使用Object，因为它是无序的。我们可以在这个存储空间中删除或者添加和获取指定的数据。存储空间满后，添加数据时，会自动删除最旧的数据。实现需求：实现一个LRUCache类型作为存储空间，使用Map数据结构存储数据，因为它的访问时间复杂度是O(1)，数组是O(n)。实现get和set方法获取和添加数据我们的存储空间是有长度限制的，所以不需要提供delete方法。存储满后，最旧的数据会自动删除。使用get获取数据后，需要将这块数据更新到最前面。现在我们已经把LRU算法的特点和实现思路都列出来了，下面我们一起来实现吧！4.具体实现首先，我们定义一个LRUCache类来封装所有的方法和变量。代码如下：上面的代码只是我们最简单的架子，需要具体实现get和set方法。代码如下：上面代码中实现了get和set方法，下面说说这两个方法的实现思路：set方法：添加新数据到地图上，如果添加的数据存在，先删除数据，再添加。如果添加数据后时间过长，则需要删除最旧的一条数据。data.keys().next().value表示获取最后一条数据。get方法：先从map对象中取出该条数据，然后删除该条数据，最后重新插入该条数据，保证该条数据移到最前面。接下来，让我们使用一些测试用例看看它是否有效。存储数据集：lruCache.set('name','小猪课堂');lruCache.set('年龄',22);lruCache.set('性别','男性');lruCache.set('height',176);lruCache.set('weight','100');console.log(lruCache);输出结果：继续插入数据，此时会过长，代码如下：lruCache.set('grade','10000');console.log(lruCache);输出结果：此时我们发现保存时间最长的名字已经被移除，新插入的数据已经成为第一个。我们使用get来获取数据，代码如下：lruCache.get('sex');控制台日志（lruCache）；输出结果：我们发现此时sex字段已经到前面了。总结LRU算法的逻辑其实很简单，理解原理后实现起来也很简单。最重要的是我们需要用什么数据结构来存储数据，因为map访问速度很快，所以我们就用它，当然数组也可以实现。还有一些小伙伴用链表来实现LRU，当然是可以的。
