Open CwRv07 opened 1 year ago
// Vue3的keepalive组件就用了这个LRU管理组件的缓存
var LRUCache = function (capacity) {
this.map = new Map()
this.capacity = capacity
}
LRUCache.prototype.get = function (key) {
if (this.map.has(key)) {
let value = this.map.get(key)
// 重新set,相当于更新到 map最后
this.map.delete(key)
this.map.set(key, value)
return value
}
return -1
}
LRUCache.prototype.put = function (key, value) {
// 如果有,就删了再赋值
if (this.map.has(key)) {
this.map.delete(key)
}
this.map.set(key, value)
// 判断是不是容量超了,淘汰机制
if (this.map.size > this.capacity) {
this.map.delete(this.map.keys().next().value)
}
}
思考:有没有考虑过LRU算法实现中为什么使用map,它的好处是什么?对于LRU算法,是get使用频率更高还是put使用频率更高?为什么?LRU算法的使用场景? —— 莉莉丝日常实习面试
记得之前面试的时候,就是用Map的方式来求解这道题的。但是面试官对答案并不是很满意,说还有提升空间。
使用Map来求解确实是一个好的解决方案,这得益于map的get和put操作的时间复杂度都是O(1)。
但是对于delete操作,只有通过遍历整个Map,才能获取要删除的元素。
因此delete方法的时间复杂度并不是O(1)。这里就是我们可以优化的点。
使用Map来求解的示例代码如下:
// ES5写法
const LRUCache5 = function (capacity) {
this.capacity = capacity;
this.cache = new Map();
}
LRUCache5.prototype.get = function (key) {
if (!this.cache.has(key)) {
return -1;
}
let value = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, value);
return value;
}
LRUCache5.prototype.put = function (key, value) {
if (this.cache.size >= this.capacity) {
let key = this.cache.keys().next().value;
this.cache.delete(key);
}
if (this.cache.has(key)) {
this.cache.delete(key);
}
this.cache.set(key, value);
}
LRUCache5.prototype.toString = function () {
console.log('capacity', this.capacity);
console.table(this.cache);
}
const lruCache = new LRUCache5(2);
lruCache.put(1, 'first');
lruCache.put(2, 'second');
lruCache.get(1);
lruCache.toString()
lruCache.put(3, 'third');
lruCache.toString();
// ES6写法
class LRUCache6 {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map();
}
get(key) {
if (!this.cache.has(key)) {
return -1;
}
let value = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, value);
}
put(key, value) {
if (this.cache.has(key)) {
this.cache.delete(key);
}
if (this.cache.size >= this.capacity) {
let key = this.cache.keys().next().value;
this.cache.delete(key);
}
this.cache.set(key, value);
}
toString() {
console.log('capacity', this.capacity);
console.table(this.cache);
}
}
const lruCache6 = new LRUCache6(2);
lruCache6.put(1, 'first');
lruCache6.put(2, 'second');
lruCache6.get(1);
lruCache6.toString()
lruCache6.put(3, 'third');
lruCache6.toString();
最佳方案应该是用Map+双向链表的方式来求解:
为什么链表
删除一个元素只需要O(1)的时间复杂度呢?
假设cache中的元素为1,2,3,4,5。我们想要删除3号元素,使用链表来删除的过程如下图所示:
只需要修改2号节点的next指向为4号节点即可删除3号节点。
(不得不说,链表这种数据结构真的太神奇了!!!)
因此,LRU缓存算法
的满分解法应该是Map+链表
。
考虑到在链表中执行 put
操作和delete
操作需要知道待插入节点的前驱节点和后继节点,如果使用单向链表的话,需要进行一次遍历,才能找到前驱和后继,这样就违背了O(1)时间复杂度的初衷,因此,我们应采用双向链表
的方式来标记每个节点的信息,这样就可以通过prev
指针很方便的找到前驱节点,通过next
指针很方便的找到后继节点啦:
整理一下使用Map
和链表
来实现LRU缓存
的思路:
1.使用Map
作为Cache缓存区
,Map
的key
为传入的key
,value
为双向链表
中的节点。
2.双向链表
中的节点包含四个属性:
key
(节点的键)value
(节点的值) next
(指向下一个节点) prev
(指向前一个节点) 3.当执行get
操作时,需要先判断Map
中是否存在对应的key
:
return -1
;Map
和链表
里删除当前节点,然后把当前节点添加至头节点后边&Map的尾部(Map里越往后优先级越高),然后返回节点的value值; 4.当执行put
操作时,需要先判断Map
中是否存在要put
的key
:
key
,为了保证优先级,需要在Map
和链表
中都先删除当前节点,然后添加当前节点至链表头节点之后&Map的尾部;key
,则需要根据Map
的size
和容量capacity
的大小关系分别处理:
Map
的size
大于等于capacity
,则需要删除链表除尾结点的最后一个节点&Map的第一个元素,然后添加新节点至头节点之后&Map的尾部; Map
的size
小于capacity
,直接添加新节点至头节点之后&Map的尾部;整体逻辑和只采用Map
的版本差不多。
但是对于value
的赋值,引入了双向链表
来优化处理速度。
至此,我们可以总结一下,在双向链表上,需要进行哪些操作:
1.首先需要定义一下双向链表中每个节点所拥有的属性:
const linkListNode = function (key = "", val = "") {
this.key = key;
this.val = val;
this.pre = null;
this.next = null;
}
2.设置链表初始状态下的节点及它们之间的指向(生成头节点和尾节点):
初始情况下,头节点head
的next
直接指向tail
;尾结点tail
的pre
直接指向head
。链表中只存在这两个节点。
const linkList = function () {
let head = new linkListNode("head", "head");
let tail = new linkListNode("tail", "tail");
head.next = tail;
tail.pre = head;
this.head = head;
this.tail = tail;
}
3.定义链表的添加操作
当我们需要向链表中添加元素时,会直接添加到头节点的下一个位置处。 步骤为:
node
的pre
和next
属性赋值;pre
为当前node
;next
为当前node
; tips: 为了保证前一步的操作不会影响后一步,操作链表的顺序应该是从后往前。因此先修改pre,再修改next。
// 链表头节点添加,每次有新元素的时候就添加在头节点处,因此链表元素越靠前,说明元素等级越高
linkList.prototype.append = function (node) {
node.next = this.head.next;
node.pre = this.head;
this.head.next.pre = node;
this.head.next = node;
}
4.删除指定链表元素
删除指定链表元素只需要如下两步:
next
指向pre
指向
linkList.prototype.delete = function (node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
5.删除链表中除尾节点之外的最后一个节点:(优先级最低的节点,容量不足时使用)
头节点的作用是便于插入新元素,尾节点的作用是便于删除优先级最低的元素。
具体步骤是:
next
指向为尾节点(tail
)tail
)的pre
指向为待删除节点的前一个节点删除优先级最低的节点就体现出双向链表的好处啦!
linkList.prototype.pop = function () {
let node = this.tail.pre;
node.pre.next = this.tail;
this.tail.pre = node.pre;
return node;
}
6.重写console方法来打印链表,查看链表的实时状态:
linkList.prototype.linkConsole = function (key = '1') {
let h = this.head;
let res = "";
while (h) {
if (res != "") {
res += "-->";
res += h[key];
h = h.next;
}
}
console.log(res);
}
定义好链表的相关操作方法后,我们就可以使用Map
+linkList
来完成LRU缓存算法
啦:
1.定义LRUCache数据结构
// LRUCache数据结构
// capacity保存最大容量,kvMap保存节点信息,linkList为节点的顺序链表
const LRUCache = function (capacity) {
this.capacity = capacity;
this.kvMap = new Map();
this.linkList = new linkList();
}
2.编写get方法
// 如果关键字key存在于缓存中,则返回关键字的值,并重置节点链表顺序,将该节点移到头结点之后,否则,返回-1
LRUCache.prototype.get = function (key) {
if (!this.kvMap.has(key)) {
return -1;
}
let node = this.kvMap.get(key);
this.linkList.delete(node);
this.linkList.append(node);
return node.val;
}
3.编写put方法
LRUCache.prototype.put = function (key, value) {
if (this.kvMap.has(key)) {
let node = this.kvMap.get(key);
node.val = value;
this.linkList.delete(node);
this.linkList.append(node);
} else {
let node = new linkListNode(key, value);
if (this.capacity === this.kvMap.size) {
let nodeP = this.linkList.pop();
this.kvMap.delete(nodeP.key);
}
this.kvMap.set(key, node);
this.linkList.append(node);
}
}
完整代码如下:
const linkListNode = function (key = "", val = "") {
this.val = val;
this.key = key;
this.pre = null;
this.next = null;
}
// 设置链表初始状态下节点及它们之间的指向,(生成头节点和尾结点)
const linkList = function () {
let head = new linkListNode("head", "head");
let tail = new linkListNode("tail", "tail");
head.next = tail;
tail.pre = head;
this.head = head;
this.tail = tail;
}
// 链表头节点添加,每次有新元素的时候就添加在头节点处,因此链表元素越靠前,说明元素等级越高
linkList.prototype.append = function (node) {
node.next = this.head.next;
node.pre = this.head;
this.head.next.pre = node;
this.head.next = node;
}
// 链表删除指定节点
linkList.prototype.delete = function (node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
// 删除并返回链表的最后一个节点(非tail)
// 取到链表的最后一个节点(非tail节点),删除该节点并返回节点信息
linkList.prototype.pop = function () {
let node = this.tail.pre;
node.pre.next = this.tail;
this.tail.pre = node.pre;
return node;
}
// 打印链表信息
// 将链表的信息按顺序打印出来,入参为需要打印的属性
linkList.prototype.linkConsole = function (key = 'val') {
let h = this.head;
let res = "";
while (h) {
if (res != "") {
res += "-->";
res += h[key];
h = h.next;
}
}
console.log(res);
}
// LRUCache数据结构
// capacity保存最大容量,kvMap保存节点信息,linkList为节点的顺序链表
const LRUCache = function (capacity) {
this.capacity = capacity;
this.kvMap = new Map();
this.linkList = new linkList();
}
// put方法
// 如果关键字key已经存在,则变更其数据值value,并重置节点链表顺序,将该节点移到头节点之后;如果不存在,则向缓存中插入该组key-value。
// 如果插入操作导致关键字数量超过capacity,则应该踢掉最久未使用的关键字。
LRUCache.prototype.put = function (key, value) {
if (this.kvMap.has(key)) {
let node = this.kvMap.get(key);
node.val = value;
this.linkList.delete(node);
this.linkList.append(node);
} else {
let node = new linkListNode(key, value);
if (this.capacity === this.kvMap.size) {
let nodeP = this.linkList.pop();
this.kvMap.delete(nodeP.key);
}
this.kvMap.set(key, node);
this.linkList.append(node);
}
}
// get方法
// 如果关键字key存在于缓存中,则返回关键字的值,并重置节点链表顺序,将该节点移到头结点之后,否则,返回-1
LRUCache.prototype.get = function (key) {
if (!this.kvMap.has(key)) {
return -1;
}
let node = this.kvMap.get(key);
this.linkList.delete(node);
this.linkList.append(node);
return node.val;
}
测试:
const obj = new LRUCache(2);
obj.put(1, 1);// 1
obj.put(2, 2);// 2 -> 1
console.log(obj.get(1)); // 1 -> 2
obj.put(3, 3);// 3 -> 1
console.log(obj.get(2));// 此时缓存里没有2的位置了,因此会返回-1
obj.put(4, 4);// 4 -> 3
console.log(obj.get(1));// 此时缓存里没有1的位置了,因此会返回-1
console.log(obj.get(3));// 3 -> 4
console.log(obj.get(4));// 4 -> 3
//Least Recently Used(最近最少使用) 缓存淘汰算法
//此算法是简单版,如果要进一步优化时间复杂度,需要使用到双向链表
//使用map的原因:利用map的有序性,因为map.keys()返回的是一个迭代器,
//每次调用next()都是按照顺序获取map集合的键
class LRUCache {
constructor(capacity) {
this.cache = new Map()
this.capacity = capacity
}
get(key) {
if (!this.cache.has(key)) return -1
const value = this.cache.get(key)
//删除之前的记录,重新set到map集合最后
this.cache.delete(key)
this.cache.set(key, value)
return value
}
set(key, value) {
if (this.cache.has(key)) {
this.cache.delete(key)
}
if (this.cache.size >= this.capacity) {
//淘汰最久没使用的记录,iterator.next().value就是map集合的第一个键,也就是对应最久没使用的缓存
const iterator = this.cache.keys()
this.cache.delete(iterator.next().value)
}
this.cache.set(key, value)
}
}
const lruCache = new LRUCache(2)
lruCache.set('a', 'ysy')
lruCache.set('b', 'dzq')
lruCache.get('a')
lruCache.set('c', 'zbc')
console.log(lruCache.get('a')) //ysy
lruCache.set('a', 'ysy')
lruCache.set('b', 'dzq')
lruCache.set('c', 'zbc')
console.log(lruCache.get('a')) //-1
思考:有没有考虑过LRU算法实现中为什么使用map,它的好处是什么?对于LRU算法,是get使用频率更高还是put使用频率更高?为什么?LRU算法的使用场景? —— 莉莉丝日常实习面试
map存储的时候有顺序,实现了Iterator接口
设计LRU(最近最少使用)缓存结构,可参考如下模板