LRU(Least Recently Used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据。核心思想是如果数据最近被访问过,那么将来被访问的几率也会高。
- 新数据插入到表头
- 每当缓存命中(即缓存数据被访问),则将数据移动到表头部
- 当表达到限制长度的时候,将表尾部的数据丢弃
实现代码如下:
class LRUCache { constructor(size){ this.size = size || 10 this.cache = [] } } LRUCache.prototype.get = (key) => { let index = this.cache.findIndex((item) => { item.key === key }) if(index === -1){ return -1 } let value = this.cache[index].value this.cache.splice(index,1) this.cache.unshift({ key,value }) return value } LRUCache.prototype.set = (key,value) => { let index = this.cache.findIndex((item) => { item.key === key }) if(index > -1){ this.cache.splice(index,1) }else if(this.cache.length >= this.size){ this.cache.pop() } this.cache.unshift({ key,value }) }
class LRUCache { constructor(size){ this.cache = new Map() this.size = size || 10 } } LRUCache.prototype.get = function (key) { if (this.cache.has(key)) { // 存在即更新 let value = this.cache.get(key); this.cache.delete(key); this.cache.set(key, value); return value; } return null; }; LRUCache.prototype.set = function (key, value) { if (this.cache.has(key)) { // 存在即更新(删除后加入) this.cache.delete(key); } else if (this.cache.size >= this.size) { // 不存在即加入 // 缓存超过最大值,则移除最近没有使用的 this.cache.delete(this.cache.keys().next().value); } this.cache.set(key, value); };