460. LFU 缓存
题目描述
请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。它应该支持以下操作：get 和 put。
- get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
- put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近 最少使用的键。
「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。
示例
LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 去除 key 2
cache.get(2); // 返回 -1 (未找到key 2)
cache.get(3); // 返回 3
cache.put(4, 4); // 去除 key 1
cache.get(1); // 返回 -1 (未找到 key 1)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
解题思路
LRU (Least recently used) 最近最少使用，如果数据最近被访问过，那么将来被访问的几率也更高。 LFU (Least frequently used) 最不经常使用，如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小。 FIFO (Fist in first out) 先进先出， 如果一个数据最先进入缓存中，则应该最早淘汰掉。
用双 hash 实现：
一个存储数据，给定的 key 作为键，给定的 value、freq 组成对象作为值；一个存储使用频率 freq 作为键，符合该频率的 key 组成数组作为值。
put 操作时，我们检测该值是否存在于 cache 中，若不存在则插入，并更新 freq，若存在，则直接更新 cache 、freq 。
get 操作获取值的同时，将该 freq 中该 key 频率数组+1 即可。
代码
/**
* @param {number} capacity
*/
var LFUCache = function (capacity) {
this.limit = capacity;
// cache数据结构：{key:obj{value,freq}}
this.cache = new Map();
// freqMap数据结构：{freq:符合该频率的keys}
this.freqMap = new Map();
};
/**
* @param {number} key
* @return {number}
*/
LFUCache.prototype.get = function (key) {
let cache = this.cache;
let r = -1;
if (typeof cache[key] != "undefined") {
let o = cache[key];
r = o.value;
//更新频率记录
this.updateL(key, o);
}
return r;
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LFUCache.prototype.put = function (key, value) {
let { cache, limit, freqMap: fmap } = this;
if (limit <= 0) return;
if (typeof key == "undefined" || typeof value == "undefined")
throw new Error("key or value is undefined");
// 存在则直接更新
// cache数据结构：{key:obj{value,freq}}
// freqMap数据结构：{freq:符合该频率的keys}
if (typeof cache[key] == "undefined") {
// 获取频率 key
// 判断容量是否满
if (Object.keys(cache).length == limit) {
// 容量满了
let fkeys = Object.keys(fmap);
let freq = fkeys[0];
// 获取key集合
let keys = fmap[freq];
// 淘汰首位
delete cache[keys.shift()];
// 清理
if (fmap[freq].length == 0) delete fmap[freq];
}
// 频率记录是否存在
if (!fmap[1]) fmap[1] = [];
// 插入新值
fmap[1].push(key);
cache[key] = {
value: value,
freq: 1, // 默认的频率
};
} else {
// 如果存在，直接更新
cache[key].value = value;
//更新频率记录
this.updateL(key, cache[key]);
}
};
// 更新cache存储的频率记录，不是freqMap
LFUCache.prototype.updateL = function (key, obj) {
let { freq } = obj;
// 获取频率为freq的相应的key
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;
// 在判断符合更新之后的频率的key是否为空
if (!this.freqMap[freq]) this.freqMap[freq] = [];
this.freqMap[freq].push(key);
};
/**
* Your LFUCache object will be instantiated and called as such:
* var obj = new LFUCache(capacity)
* var param_1 = obj.get(key)
* obj.put(key,value)
*/
