Open xianzao opened 1 year ago
FIFO (First Input First Output)可以说是最简单的一种缓存算法,通过设置缓存上限,当达到了缓存上限的时候,按照先进先出的策略进行淘汰,再增加进新的 key-value。
实现的可以创建一个map对象来保存键值信息
然后创建keys的数组用来进行淘汰判断:
var FIFOCache = function (limit) {
this.limit = limit || 10;
this.map = {};
this.keys = [];
};
实现get函数通过map返回对应值即可
FIFOCache.prototype.get = function (key) {
return this.map[key];
};
在set函数中,先keys长度是否达到限制,没达到限制直接追加,如果达到限制判断key是否已经存在,存在将key删除,否则默认删除keys的第一个数据与对应map中的值:
FIFOCache.prototype.set = function (key,value) {
if (this.keys.length >= this.limit) {
let i = this.keys.indexOf(key);
if (i >= 0)
this.keys.splice(i, 1);
else
delete this.map[this.keys.shift()];
}
this.keys.push(key);
this.map[key] = value;
};
LRU(Least recently used)的核心思想是如果数据最近被访问过,那么将来被访问的几率也更高。此处以淘汰首位的数据来举例。
var LRUCache = function (capacity) {
this.limit = limit || 2;
this.map = {};
this.keys = [];
};
实现get函数一样是通过map返回对应值,需要加了一个update函数,用来切换key位置,将最新访问的数据置到最后。
LRUCache.prototype.get = function (key) {
let r = -1;
if (typeof this.map[key] != "undefined") {
r = this.map[key];
this.update(key);
}
return r;
};
LRUCache.prototype.update = function (key) {
let idx = this.keys.indexOf(key);
if (idx != this.keys.length - 1) {
// 删除之前位置
this.keys.splice(idx, 1);
// 重新插入到最后
this.keys.push(key);
}
};
set函数判断map中key是否存在,存在直接修改值并更新key在keys中的位置
如果不存在,判断keys是否已满,满则删除首位数据,然后将最新数据追加到末位
LRUCache.prototype.set = function (key, value) {
if(typeof key=="undefined"||typeof value=="undefined") throw new Error('key or value is undefined');
if (typeof this.map[key] != "undefined") {
this.update(key);
this.map[key] = value;
} else {
// 判断容量是否满
if (this.keys.length == this.limit) {
// 淘汰首位
delete this.map[this.keys[0]];
this.keys.splice(0, 1);
}
// 插入新值
this.keys.push(key);
this.map[key] = value;
}
};
简化使用Map
var LRUCache = function (capacity) {
this.cache = new Map();
this.capacity = capacity;
};
LRUCache.prototype.get = function (key) {
let cache = this.cache;
if (cache.has(key)) {
let temp = cache.get(key);
cache.delete(key);
cache.set(key, temp);
return temp;
} else {
return -1;
}
};
LRUCache.prototype.put = function (key, value) {
let cache = this.cache;
if (cache.has(key)) {
cache.delete(key);
} else if (cache.size >= this.capacity) {
cache.delete(cache.keys().next().value);
}
cache.set(key, value);
};
LFU(Least Frequently Used )也是一种常见的缓存算法。当空间满时,通过访问次数,淘汰问次数最小的数据。
如果访问次数全部一样则默认淘汰最初添加的数据,这里定义一个freqMap用来保存访问频率数据
var LFUCache = function (capacity) {
this.limit = capacity;
this.map = {};
this.freqMap = {};
};
get函数跟LRU的差不多,不过这里this.map里所保存的对象格式为:
{
value:"value", // 存值
freq:1//<== 频率
}
LFUCache.prototype.get = function (key) {
let r = -1;
if (typeof this.map[key] != "undefined") {
let o = this.map[key];
r = o.value;
//更新频率记录
this.updateL(key, o);
}
return r;
};
更新频率的时候通过对象保存的freq字段从频率记录this.freqMap中寻找,删除原始记录后重新追加到新的记录:
LFUCache.prototype.updateL = function (key, obj) {
let freq = obj.freq;
let arr = this.freqMap[freq];
// 删除原频率记录
this.freqMap[freq].splice(arr.indexOf(key), 1);
// 清理
if (this.freqMap[freq].length == 0) delete this.freqMap[freq];
// 跟新频率
freq = obj.freq = obj.freq + 1;
if (!this.freqMap[freq]) this.freqMap[freq] = [];
this.freqMap[freq].push(key);
};
set函数判断逻辑跟LRU类似,区别在容量满的时候,默认取freqMap中第一个索引对应的keys数组中第一个key,删除key对应的数据:
LFUCache.prototype.set = function (key, value) {
if (this.limit <= 0) return;
if(typeof key=="undefined"||typeof value=="undefined") throw new Error('key or value is undefined');
// 存在则直接更新
if (typeof this.map[key] == "undefined") {
// 获取频率 key
// 判断容量是否满
if (Object.keys(this.map).length == this.limit) {
let fkeys = Object.keys(this.freqMap);
let freq = fkeys[0];
// 获取key集合
let keys = this.freqMap[freq];
// 淘汰首位
delete this.map[keys.shift()];
// delete this.map[keys[0]];
// keys.splice(0, 1);
// 清理
if (this.freqMap[freq].length == 0) delete this.freqMap[freq];
}
// 频率记录是否存在
if (!this.freqMap[1]) this.freqMap[1] = [];
// 插入新值
this.freqMap[1].push(key);
this.map[key] = {
value: value,
freq: 1 // 默认的频率
};
} else {
this.map[key].value = value;
//更新频率记录
this.updateL(key, this.map[key]);
}
};
实现
FIFO
、LRU
、LFU
三种缓存淘汰算法