LRU被称为最近使用的。它的目的是在有限的内存空间中只缓存最近使用过的数据(即get和set的数据)。本文介绍了用JavaScript实现LRU缓存的三种方式，有需要的可以参考一下。

目录

分析用Map实现LRU缓存用对象数组实现LRU缓存用双链表实现LRU汇总LRU叫最近用，就是最近用。目的是在有限的内存空间中只缓存最近使用的数据(即get和set的数据)，超过有限内存空间的数据将被删除。这个面试问题也是经常被问到的，那就看看怎么实现吧。

分析

根据定义，LRU至少有两个特征：通过键值对读写和排序。为了读写键值对，我们通常使用哈希表来表示它们。注意哈希表是一种逻辑结构。事实上，我们需要使用对象、地图等。有序数据，即最近使用的数据在前，过时的数据回来或被删除，数据可以排序。我们可以想到数组、链表、map等数据格式。因此，我们可以通过三种方式实现LRU缓存：

MapObject ArrayLinkedList

使用Map实现LRU缓存

Map对象存储键-值对，并且可以记住键的原始插入顺序。

const Map=new Map()；

map.set(2，2)；

map.set(1，2)；

console.log(地图)；//Map(2) {2=2，1=2}，按原始插入顺序

const obj=new Object()；

obj[2]=2；

obj[1]=1

console . log(obj)；//{1: 1，2: 2}，不是按原始插入顺序

然后我们可以根据地图的特点实现LRU。这是示意图：

实施代码：

LRUCache类{

data=new Map()；//数据映射

构造器(长度){

If(长度1)抛出新错误(“长度不能小于1”)

长度=长度

}

set(键，值){

const data=this.data

//如果对象存在，直接删除

if (data.has(key)) {

data.delete(键)；

}

//将数据对象添加到映射中

data.set(键，值)；

if (data.size this.length) {

//如果映射长度超过最大值，则取出映射中的第一个元素并删除。

const delKey=data.keys()。下一个()。价值

data . delete(delKey)；

}

}

获取(密钥){

const data=this.data

//如果数据映射中没有key对应的数据，则返回null。

如果(！data.has(key))返回null

const value=data . get(key)；

//在返回数据之前，先删除原始数据，然后再添加，以便保持最新。

data.delete(键)；

data.set(键，值)；

返回值；

}

}

测试它：

const lruCache=new lruCache(2)；

lruCache.set('1 '，1)；//Map(1) {1=1}

lruCache.set('2 '，2)；//Map(2) {1=1，2=2}

console . log(LRU cache . get(' 1 '))；//Map(2) {2=2，1=1}

lruCache.set('3 '，3)；//Map(2) {1=1，3=3}

console . log(LRU cache . get(' 2 '))；//null

lruCache.set('4 '，4)；//Map(2) {3=3，4=4}

console . log(LRU cache . get(' 1 '))；//null

console . log(LRU cache . get(' 3 '))；//Map(2) {4=4，3=3}

console . log(LRU cache . get(' 4 '))；//Map(2) {3=3，4=4}

运行结果：

基本上用Map就能实现LRU缓存，兼容性也还可以，除了IE兼容性：

如果不使用地图，还能如何实现LRU缓存？

使用Object + Array实现LRU缓存

刚才我们也分析了LRU需要满足两个要求：键值对和可排序性，可以分别对应对象和数组。那么，用这种思路能实现吗？答案是肯定的，实现代码：

LRUCacheObjArr级{

长度=0；//定义列表的最大长度

data obj={ }；//使用对象临时存储数据，get时间复杂度可以保证为O(1)

data arr=[]；//使用数组解决排序问题

构造器(长度){

If(长度1)抛出新错误(“非法参数”)

this.length=长度；

}

获取(密钥){

如果(！this.dataObj[key] ||！this.dataArr.length)返回null

//你需要把被访问的值放回数组的末尾来表示最新的数据。

const index=this . data arr . find index(item=item . key===key)；

//先删除原始数据，然后推到数组末尾

this.dataArr.splice(index，1)；

this . data arr . push(this . data obj[key])；

//返回值，对象是乱序的，我们只需要保证里面的数据是最新的。

返回this.dataObj[key]。价值；

}

set(键，值){

//定义对象数据

const obj={key，value }；

const index=this . data arr . find index(item=item . key===key)；

//确定它是新的还是修改过的。

如果(索引！==-1) {

//如果数据已经存在，先删除，再推到最后

this.dataArr.splice(index，1)；

this . data arr . push(obj)；

}否则{

//如果没有数据，直接推送数组

this . data arr . push(obj)；

}

//Object添加或修改同一对象

this . data obj[key]=obj；

//确定新数据是否超过最大长度。

if(this . data arr . length this . length){

//数组是有序的。如果太长，就直接从表头删除，得到删除的数据。

const tmp=this . data arr . shift()；

//当前删除的对象也应该在数据对象中删除，以免再次被检索。

删除this . data obj[tmp . key]；

}

}

}

让我们用同样的测试用例来测试它：

const lruCache=new LRUCacheObjArr(2)；

lruCache.set('1 '，1)；//dataArr(1) [obj1]，dataObj(1) {'1': obj1}

lruCache.set('2 '，2)；//dataArr(2) [obj1，obj2]，dataObj(2) {'1': obj1，' 2': obj2}

console . log(LRU cache . get(' 1 '))；//dataArr(2) [obj2，obj1]，dataObj(2) {'1': obj1，' 2': obj2}

lruCache.set('3 '，3)；//dataArr(2) [obj1，obj3]，dataObj(2) {'1': obj1，' 3': obj3}

console . log(LRU cache . get(' 2 '))；//null

lruCache.set('4 '，4)；//dataArr(2) [obj3，obj4]，dataObj(2) {'3': obj3，' 4': obj4}

console . log(LRU cache . get(' 1 '))；//null

console . log(LRU cache . get(' 3 '))；//dataArr(2) [obj4，obj3]，dataObj(2) {'3': obj3，' 4': obj4}

console . log(LRU cache . get(' 4 '))；//dataArr(2) [obj3，obj4]，dataObj(2) {'3': obj3，' 4': obj4}

运行结果：

使用对象数组的方法虽然可以达到效果，但是会因为数组的频繁操作而牺牲一些性能，而且不如Map方便。除了使用数组对象，其实我们还可以通过使用双向链表来实现LRU。

使用双向链表实现LRU

双向链表，顾名思义，是一个双向的链表，与单向链表不同。直接看图可能更直观：

移动元素时，双向链表比单向链表复杂一点。比如我们想交换节点B和节点C的位置，过程如下：

这对LRU意味着什么？双向链表是有序的，每个节点都知道它的上一个或下一个节点；它存储值的方式也是使用键-值对的方式，所以完全可以实现LRU。

实施代码：

LRUCacheLinked类{

data={ }；//链表数据

dataLength=0；//链表的长度，用变量保存，可以更快的访问

listHead=null//链接列表头

listTail=null//链接列表的结尾

长度=0；//链表的最大长度

//构造函数

构造器(长度){

If(长度1)抛出新错误(“非法参数”)

this.length=长度；

}

set(键，值){

const curNode=this . data[key]；

if (curNode==null) {

//添加新数据

const nodeNew={key，value }；

//移动到末尾

this . movetotail(node new)；

//将新添加的节点保存到一个数据对象中，其pre或next将在moveToTail中设置。

this . data[key]=node new；

//链表长度在增加。

this.dataLength

//初始化链表头

if(this . datalength===1)this . list head=node new；

}否则{

//修改现有数据

curNode.value=value

//移动到末尾

this . movetotail(curNode)；

}

//添加数据后可能会超过长度，所以尽量删除数据。

this . try clean()；

}

获取(密钥){

//根据键值取出对应的节点

const curNode=this . data[key]；

if (curNode==null)返回null；

if (this.listTail===curNode) {

//如果被访问的元素在链表的末尾，不修改链表，直接返回值。

返回curNode.value

}

//如果是中间元素或者头元素，需要在获取之前将其移动到链表的末尾，表示最新的。

this . movetotail(curNode)；

返回curNode.value

}

//将节点移动到链表的末尾

moveToTail(curNode) {

//获取链表的尾部

const tail=this.listTail

//如果当前节点是链表的末尾，则不做处理返回。

if (tail===curNode)返回；

//1.preNode和nextNode断绝了与curNode的关系。

const preNode=curNode.pre

const next node=cur node . next；

if(前节点){

if (nextNode) {

//当前元素的上一个节点指向下一个节点

preNode.next=nextNode

}否则{

//断开当前元素与前一个节点的连接

删除preNode.next

}

}

if (nextNode) {

if(前节点){

//当前元素的下一个节点指向前一个节点

next node . pre=pre node；

}否则{

//断开当前元素和下一个节点之间的关系

删除nextNode.pre

}

//如果当前节点是链表的头，需要重新分配。

if(this . list head===curNode)this . list head=next node；

}

//2.curNode打破了与preNode和nextNode的关系。

删除curNode.pre

删除curNode.next

//3.在列表的最后，重新建立curNode的新关系。

if (tail) {

tail.next=curNode

curNode.pre=tail

}

//重新分配链表的末尾，使其保持最新。

this.listTail=curNode

}

tryClean() {

while(this . datalength this . length){

const head=this.listHead

If (head==null)抛出新的错误('链表丢失了头')；

const headNext=head.next

If (headnext==null)抛出新错误(“链表头缺少下一个节点”)；

//1.切断头与头的关系Next

删除head.next

删除headNext.pre

//2.重新分配列表头

this . list head=head next；

//3.清理数据

删除this . data[head . key]；

//4.重新计数

this . datalength=this . datalength-1；

}

}

}

在这种方式中，双向链表是三种方式中最复杂的。让我们用同一个案例来测试一下：

const lruCache=new LRUCacheLinked(2)；

lruCache.set('1 '，1)；

lruCache.set('2 '，2)；

console . log(LRU cache . get(' 1 '))；

lruCache.set('3 '，3)；

console . log(LRU cache . get(' 2 '))；

lruCache.set('4 '，4)；

console . log(LRU cache . get(' 1 '))；

console . log(LRU cache . get(' 3 '))；

console . log(LRU cache . get(' 4 '))；

取得的成果：

总结

本文总结了三种实现LRU缓存的方法，其中Map是最好的方法。使用另外两种方法，虽然也能达到效果，但从效率和可读性来说，Map更好。三种方法都学会了吗？

关于用JavaScript实现LRU缓存的三种方法，本文到此结束。更多相关的JavaScript LRU缓存内容，请搜索我们以前的文章或继续浏览下面的相关文章。希望大家以后能多多支持我们！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。