缓存淘汰策略
LRU
LRU(Least Recently Used) 最近最久未使用算法，也就是说我们认为最近使用过的数据应该是是「有用的」，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据。
比方说手机杀后台，同时开启了若干个应用在后台，再开一个内存就不够了，这时系统就会把后台中最久没有使用过的程序杀掉。
一个 LRU 算法通常要实现以下的功能：
- 接受一个
max参数作为缓存的最大容量。 - 有一个
put(key, val)方法用来存键值对。 - 有一个
get(key)用来取对应的值，找不到返回-1。同时，触发该方法也会改变顺序。
我们可以利用数组实现算法：
function LRU(max) {
this.cache = []
this.max = max
}
LRU.prototype.find = function(key) {
return this.cache.findIndex((item) => item.key === key)
}
LRU.prototype.put = function(key, val) {
const index = this.find(key)
if (index > -1) {
// 如果相同key的数据已经存在，就将其移动到数组头部
this.cache.splice(index, 1)
} else if (this.cache.length >= this.max) {
// 达到或超出最大缓存限制，就删除最后的
this.cache.pop()
}
this.cache.unshift({ key, val })
}
LRU.prototype.get = function(key) {
const index = this.find(key)
if (index > -1) {
const cache = this.cache
const temp = cache[index].val
cache.splice(index, 1)
cache.unshift({ key, val: temp })
return temp
return
} else {
return -1
}
}
由于数组需要进行遍历检查 key 值，因此我们可以使用 Map 来存储以达到时间复杂度 $O(1)$：
function LRU(max) {
this.cache = new Map()
this.max = max
}
LRU.prototype.has = function(key) {
return this.cache.has(key)
}
LRU.prototype.put = function(key, val) {
const cache = this.cache
if (this.has(key)) {
// 如果相同key的数据已经存在，就将其移动到数组头部
cache.delete(key)
} else if (cache.size >= this.max) {
// 达到或超出最大缓存限制，就删除最后的
cache.delete(cache.keys().next().value)
}
cache.set(key, val)
}
LRU.prototype.get = function(key) {
if (this.has(key)) {
const cache = this.cache
const temp = cache.get(key)
cache.delete(key)
cache.set(key, temp)
return temp
} else {
return -1
}
}
LFU
LFU(Least Frequently Used) 最少使用算法，也就是使用频率最少的数据。
和 LRU 不同，LRU 按照访问先后排序，而 LFU 则是按照访问次数排序，因此每次添加或获取数据的时候，我们需要根据频率更新列表的排序。
我们可以使用双向链表+哈希表来实现 LFU。
class Node {
constructor(key, val) {
this.key = key
this.val = val
this.freq = 0 // 频率
this.pre = null // 上一个节点
this.next = null // 下一个节点
}
}
// 双向链表，接受一个初始节点做初始化
class DoubleLinkedList {
constructor() {
// 我们需要先创造两个哑巴节点，这是为了省去对边界节点的额外处理，使得每个节点的处理过程一样
this.head = new Node('head') // 头指针
this.tail = new Node('tail') // 尾指针
this.head.next = this.tail
this.tail.pre = this.head
}
remove(node) {
node.pre.next = node.next
node.next.pre = node.pre
}
// 在preNode后面插入节点
insert(preNode, node) {
const nextNode = preNode.next
nextNode.pre = node
node.next = nextNode
preNode.next = node
node.pre = preNode
}
}
class LFU {
constructor(max = 0) {
this.max = max <= 0 ? 0 : max
this.size = 0
this.cache = new Map()
this.list = null
}
// 增加节点的频率并更新链表顺序
increaseFreq(node) {
const cpyNode = node
cpyNode.freq++
const curFreq = cpyNode.freq
// 从当前节点开始遍历直到freq小于前面的节点为止
node = node.pre || this.list.tail.pre
while (node.freq <= curFreq) {
// 遍历到头节点跳出
if (node === this.list.head) {
break
}
node = node.pre
}
this.list.insert(node, cpyNode)
this.size++
}
// 新增节点
put(key, val) {
if (this.max === 0) return void 0
const cache = this.cache
if (cache.has(key)) {
// 如果已存在，就只更新val和增加频率
let node = cache.get(key)
node.val = val
this.list.remove(node)
this.increaseFreq(node)
} else {
/**
* 判断是否达到最大缓存
* 是：移除频率最小(链表尾指针指向)的node，并将新节点插入
* 否：将新的节点并插入到链表尾部
*/
if (this.size >= this.max) {
const list = this.list
const removedNode = list.tail.pre
list.remove(removedNode)
this.cache.delete(removedNode.key)
this.size--
}
const node = new Node(key, val)
this.cache.set(key, node)
if (this.list === null) {
this.list = new DoubleLinkedList()
}
const list = this.list
this.increaseFreq(node)
}
}
// 获取节点
get(key) {
const cache = this.cache
if (cache.has(key)) {
const node = cache.get(key)
this.increaseFreq(node)
return node
} else {
return -1
}
}
log() {
let node = this.list.head
let res = ''
let sum = 0
while (true) {
res += `(${node.key}, ${node.val}, ${node.freq})`
if (node.next === null) {
break
}
res += '-->'
node = node.next
}
console.log(res)
}
}
const lfu = new LFU(4)
lfu.put(1, '第一个节点')
lfu.put(2, '第二个节点')
lfu.put(3, '第三个节点')
lfu.put(3, '第三个节点+')
lfu.put(3, '第三个节点++')
lfu.put(4, '第四个节点')
lfu.log()
// (head, undefined, 0)-->(3, 第三个节点++, 3)-->(4, 第四个节点, 1)-->(2, 第二个节点, 1)-->(tail, undefined, 0)
也可以直接利用 Map 的特性：被 set 的元素会移到尾部。
class Node {
constructor(key, value) {
this.key = key
this.value = value
this.freq = 1 // 访问频次
}
}
class LFUCache {
constructor(capacity) {
this.capacity = capacity
this.minFreq = 0 // 最小使用频率，删除使用
this.size = 0 // 当前已使用的容量
this.freqMap = new Map() // 频率-map<node>（不使用双向链表）
this.cacheMap = new Map() // key-node（用于get方法，快捷获取相对应key的value值）
}
/**
* 频率+1
* ① 从freqMap的旧频率的key中移除
* ② 旧频率为空 && 当前频率是最小频率，需要将最小频率+1
* ③ 添加到新频率（旧频率+1）对应的map队列中 => 当前队列没有需要新建
*/
increaseFreq(node) {
let map = this.freqMap.get(node.freq)
map.delete(node.key)
if (!map.size && node.freq === this.minFreq) {
this.minFreq += 1
}
node.freq += 1
let newMap = this.freqMap.get(node.freq)
if (newMap === undefined) {
newMap = new Map()
}
newMap.set(node.key, node)
this.freqMap.set(node.freq, newMap)
}
// 借助缓存的 cacheMap 处理
get(key) {
let node = this.cacheMap.get(key)
if (node === undefined) {
return -1
}
this.increaseFreq(node)
return node.value
}
put(key, value) {
if (this.capacity === 0) return void 0
const cacheMap = this.cacheMap
const freqMap = this.freqMap
// 如果节点已存在，则变更其值
if (cacheMap.has(key)) {
let node = cacheMap.get(key)
node.value = value
cacheMap.set(key, node)
this.increaseFreq(node)
return void 0
}
// 达到最大容量，需要删除访问频次最小&&最久的节点
// 访问频次最小=>通过minFreq标记获取相应的map
// map中第一个元素为最久未被访问元素（map lru特性决定）
if (this.size === this.capacity) {
let miniFreqMap = freqMap.get(this.minFreq)
let miniFreqNode = miniFreqMap.get(miniFreqMap.keys().next().value) // 频次最小，第一个key（借助map的lru特性）
miniFreqMap.delete(miniFreqNode.key)
freqMap.set(this.minFreq, miniFreqMap)
cacheMap.delete(miniFreqNode.key)
}
// 增加节点元素（这里只处理节点不存在，已存在上面已处理）
let node = new Node(key, value)
cacheMap.set(key, node)
let map = freqMap.get(1)
if (map === undefined) {
map = new Map()
}
map.set(node.key, node)
// 对应新节点，访问频次一定是1，且最小频次为1
freqMap.set(1, map)
this.minFreq = 1
if (this.size < this.capacity) {
this.size += 1
}
return void 0
}
}