前端面试中经常提到的LRU缓存策略详解

不叫猫先生 2024-07-13 10:03:01 阅读 55

🐱 个人主页:不叫猫先生

🙋‍♂️ 作者简介:2022年度博客之星前端领域TOP 2,前端领域优质作者、阿里云专家博主,专注于前端各领域技术,共同学习共同进步,一起加油呀!

💫优质专栏:vue3从入门到精通、TypeScript从入门到实践

📢 资料领取:前端进阶资料以及文中源码可以找我免费领取

🔥 前端学习交流:博主建立了一个前端交流群,汇集了各路大神,一起交流学习,期待你的加入!(文末有我wx或者私信)

目录

LRU一、为什么要使用Map是来定义容器二、应用场景三、代码实现

LRU

LRU(Least Recently Used)最近最少使用缓存策略,根据历史数据记录,当数据超过了限定空间的时候对数据清理,清理的原则是对很久没有使用到过的数据进行清除

一、为什么要使用Map是来定义容器

Map在保存数据时会按照记住存储数据时候的顺序,这样存储的数据是有序列的,并且会维护键值对的插入顺序,Map存储数据的键值可以是任意类型(对象或者基本类型都可),Map提供了get、set、delete方法十分方便;而<code>Object的话是无序,当然也可以使用Array。另外Map的算法复杂度是O(1),处理数据更迅速。

二、应用场景

redis浏览器浏览记录vue中内置组件keep-alive

三、代码实现

实现的大概思路如下:

创建一个LRUCache类定义容器以及容器的容量定义set方面,设置容器中的数据定义get方法,获取容器中的数据

class LRUCache {

constructor(length) {

// 定义容器容量

this.length = length;

// 创建数据容器,生成一个空映射

this.map = new Map();

}

// 设置key值

set(key, value) {

}

// 获取key值

get(key) { }

}

接下来就是对set方法和get方法的处理:

set

当容器长度不超过设定的长度:设置key值,但是为了达到缓存策略的效果,需要我们先删除数据,后添加到容器的最后一条当容器长度超过设定的长度:先删除掉容器中的第一条数据

get

先获取数据值,然后删除该条数据,再设置数据到最后

class LRUCache {

constructor(length) {

// 定义容器容量

this.length = length;

// 定义数据容器

this.map = new Map();

}

// 设置key值

set(key, value) {

// 如果容器容量超过设定的容量

if (this.map.size >= this.length) {

// 等价于:let firstKey = this.map.keys()[0]

//map.keys().next()查询容器中第一条数据的key值

//keys()会返回一个迭代器对象,包含了实力对象中的每一个key值

let firstKey = this.map.keys().next().value;

//删除容器中第一条数据

this.map.delete(firstKey);

}

// 容器中存在key就先删除掉

if (this.map.has(key)) {

this.map.delete(key);

}

// 删除后重新加入该条数据

this.map.set(key, value);

}

// 获取key值

get(key) {

// 获取key值不存在返回null

if (!this.map.has(key)) {

return null;

}

// 获取key值

let value = this.map.get(key);

//删除容器中的该条数据

this.map.delete(key);

//重新把该条数据添加到容器中

this.map.set(key, value);

return value

}

}

// 创建实例对象并设置容器大小

const lruCache = new LRUCache(5)

添加6条数据

lruCache.set('name', 'zhangsan')

lruCache.set('class', 'xinguan')

lruCache.set('age', 19)

lruCache.set('sex', '男')

lruCache.set('occupation', '前端工程师')

lruCache.set('year', '2023')

console.log(lruCache, 'lruCache')

对lruCache添加了6条数据并按顺序排列,打印出来只剩5条数据,添加的第一条(‘name’, ‘zhangsan’)被删除了。

在这里插入图片描述

然后获取class的值,发现key为class的这条数据跑最后了。因为在get时候先delete后set了。

<code>console.log(lruCache.get('class'), 'lruCache')//xinguan

在这里插入图片描述



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。