LRU 缓存
简介
- LRU 是 Least Recently Used 的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间 t,当须淘汰一个页面时,选择现有页面中其 t 值最大的,即最近最少使用的页面予以淘汰。
框架使用场景
- 我们可以使用该方案来对某些可能频繁使用的内容进行缓存。在 Vue 的 Keep_alive 组件即采用了该缓存手段。
工作使用场景
- 我们平时的工作中也有使用的场景,笔者曾经有个需求是一个列表页的查看证书并可以保存,在再采用 LRU 缓存之前证书平均打开时间在 1s 左右,经过 LRU 算法缓存优化后,证书打开时间真正做到了秒开,省略了证书创建的过程大大优化了用户体验。 #接下来我们看下怎么实现 LRU 缓存
算法实现
class LRUCache {
/**
* 初始化一个cache
*/
private cache = new Map();
constructor(private capacity: number) {}
/**
* 缓存的取
*/
get(key: number): number {
// 当取的key不存在时返回 -1
if (!this.cache.has(key)) return -1;
// 如果取的key存在那么就删除原来key的位置,
// 在最新的位置重新存一下
const val = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, val);
return val;
}
/**
* 缓存的存
*/
put(key: number, value: number): void {
// 如果缓存中存在当前key那么就删除这个key 然后再存
if (this.cache.has(key)) {
this.cache.delete(key);
} else if (this.cache.size >= this.capacity) {
// 这里是缓存中不存在当前key 并且超出最大缓存条数那么就删除第一个key
// map的keys方法有序的返回存进去的所有的key,是一个迭代器
const firstKey = this.cache.keys().next().value;
this.cache.delete(firstKey);
}
// 上述两个都未命中时则表示是新的key且没有超过最大缓存条数直接存即可
this.cache.set(key, value);
}
}