Open pfan123 opened 4 years ago
FIFO 、LRU、LFU缓存算法算是比较简单的,它们的区别是当缓存空间满的时候,其对数据淘汰策略不同而已,这里的话我就选择了JavaScript来进行演示FIFO 、LRU、LFU的实现。希望能帮助大家更好的理解。
FIFO (First Input First Output)可以说是最简单的一种缓存算法,通过设置缓存上限,当达到了缓存上限的时候,按照先进先出的策略进行淘汰,再增加进新的 key-value。
实现的可以创建一个map对象来保存键值信息
map
然后创建keys的数组用来进行淘汰判断
keys
代码示例:
const FIFOCache = function (limit = 10) { this.limit = limit this.map = {} this.keys = [] }
实现get函数其实很简单,通过map返回对应值就行
get
FIFOCache.prototype.get = function (key) { return this.map[key] }
在set函数中,先keys长度是否达到限制
set
没达到限制直接追加
如果达到限制判断key是否已经存在,存在将key删除,否则默认删除keys的第一个数据与对应map中的值
key
FIFOCache.prototype.set = function (key, value) { if (this.keys.length >= this.limit) { const 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)算法算是最常见的缓存淘汰算法,根据数据的历史访问记录来进行淘汰数据,其核心思想是如果数据最近被访问过,那么将来被访问的几率也更高。
如果你搜索java的LRU实现,很多都是通过LinkedHashMap来实现的。我这里就照着网上搜索的相关原理通过js来实现一下。
LinkedHashMap
这里稍微注意的是淘汰的方向,有的是淘汰数组最前的,有的是淘汰最后的。可最后的效果都差不多,这里的话我就以淘汰首位的数据来举例编写。
开始的代码跟上面的FIFO实现差不多
const LRUCache = function (limit = 2) { this.limit = limit this.map = {} this.keys = [] }
实现get函数一样是通过map返回对应值,不过需要这里多了一个update函数,用来切换key位置,将最新访问的数据置到最后。
update
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) { const 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实现代码参考:
const LRUCache = function (capacity) { this.cache = new Map() this.capacity = capacity } LRUCache.prototype.get = function (key) { const cache = this.cache if (cache.has(key)) { const temp = cache.get(key) cache.delete(key) cache.set(key, temp) return temp } else { return -1 } } LRUCache.prototype.put = function (key, value) { const 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用来保存访问频率数据
freqMap
const LFUCache = function (capacity) { this.limit = capacity this.map = {} this.freqMap = {} }
get函数跟上面的LRU算法的差不多,不过这里this.map里所保存的对象格式为
this.map
{ value:"value", // 存值 freq:1//<== 频率 }
LFUCache.prototype.get = function (key) { let r = -1 if (typeof this.map[key] !== 'undefined') { const o = this.map[key] r = o.value // 更新频率记录 this.updateL(key, o) } return r }
所以更新频率的时候通过对象保存的freq字段从频率记录this.freqMap中寻找,删除原始记录后重新追加到新的记录
freq
this.freqMap
LFUCache.prototype.updateL = function (key, obj) { let freq = obj.freq const 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) { const fkeys = Object.keys(this.freqMap) const freq = fkeys[0] // 获取key集合 const 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]) } }
1. FIFO 算法实现
FIFO (First Input First Output)可以说是最简单的一种缓存算法,通过设置缓存上限,当达到了缓存上限的时候,按照先进先出的策略进行淘汰,再增加进新的 key-value。
实现的可以创建一个
map
对象来保存键值信息然后创建
keys
的数组用来进行淘汰判断代码示例:
实现
get
函数其实很简单,通过map返回对应值就行代码示例:
在
set
函数中,先keys
长度是否达到限制没达到限制直接追加
如果达到限制判断key是否已经存在,存在将
key
删除,否则默认删除keys
的第一个数据与对应map
中的值代码示例:
2. LRU 算法实现
LRU(Least recently used)算法算是最常见的缓存淘汰算法,根据数据的历史访问记录来进行淘汰数据,其核心思想是如果数据最近被访问过,那么将来被访问的几率也更高。
如果你搜索java的LRU实现,很多都是通过
LinkedHashMap
来实现的。我这里就照着网上搜索的相关原理通过js来实现一下。这里稍微注意的是淘汰的方向,有的是淘汰数组最前的,有的是淘汰最后的。可最后的效果都差不多,这里的话我就以淘汰首位的数据来举例编写。
开始的代码跟上面的FIFO实现差不多
代码示例:
实现
get
函数一样是通过map
返回对应值,不过需要这里多了一个update
函数,用来切换key
位置,将最新访问的数据置到最后。代码示例:
set
函数判断map
中key
是否存在,存在直接修改值并更新key
在keys
中的位置如果不存在,判断
keys
是否已满,满则删除首位数据,然后将最新数据追加到末位代码示例:
以下是通过Map实现代码参考:
3. LFU 算法实现
LFU(Least Frequently Used ) 也是一种常见的缓存算法。当空间满时,通过访问次数,淘汰访问次数最小的数据。
如果访问次数全部一样则默认淘汰最初添加的数据
根据需求,定义一个
freqMap
用来保存访问频率数据代码示例:
get
函数跟上面的LRU算法的差不多,不过这里this.map
里所保存的对象格式为代码示例:
所以更新频率的时候通过对象保存的
freq
字段从频率记录this.freqMap
中寻找,删除原始记录后重新追加到新的记录代码示例:
set
函数判断逻辑跟LRU的差不多,区别在容量满的时候,默认取freqMap
中第一个索引对应的keys数组中第一个key,删除key对应的数据代码示例: