LRU（Least Recently Used）
LRU 最近最少使用，是一种常见的淘汰（置换）算法，选择最近最久未使用的予以淘汰。常用于内存管理。
浏览器 IndexedDB 达到存储上限后，自动清理采用的策略正是 LRU。
当可用磁盘空间已满时，配额管理器将根据LRU策略开始清除数据——最近最少使用的源将首先被删除，然后是下一个，直到浏览器不再超过限制。 我们使用临时存储跟踪每个源的“上次访问时间”。 一旦达到临时存储的全局限制（之后会有更多限制），我们将尝试查找所有当前未使用的源（即没有打开选项卡/应用程序的那些来保持打开的数据存储）。 然后根据“上次访问时间”对它们进行排序。 然后删除最近最少使用的源，直到有足够的空间来满足触发此源回收的请求。 – IndexedDB LRU策略
要求：初始化时指定最大容量 capacity，当缓存填满时，删除最近最少使用的项。
算法实现：双向链表 哈希表
- 节点：
Node {key, value, pre, post}key、valuepre、post： 前置及后置节点，插入使用
- 双向链表：
DualLinkedList {head, tail, remove(), add()}按照被使用的顺序存储 node，头部head为最近使用的，尾部tail是最久未使用的。head、tail：头及尾节点remove()：移除节点add()：添加节点（追加到 head 节点之后）
- 定义 Hash 表：
cacheMap {key, node}以key为索引，每个索引对应存放相应的 node 节点
/* 节点 */
class Node {
constructor (key, value) {
this.key = key
this.value = value
this.pre = null // 前置节点
this.post = null // 后置节点
}
}
/* 双向链表 */
class DualLinkedList {
constructor () {
this.head = new Node()
this.tail = new Node()
this.head.post = this.tail
this.tail.pre = this.head
}
remove (node) {
node.pre.post = node.post
node.post.pre = node.pre
}
// 添加到开始处（head后）
add (node) {
node.pre = this.head
this.head.post.pre = node
node.post = this.head.post
this.head.post = node
}
}
/* LRU算法 */
class LRUCache {
constructor (capacity) {
this.capacity = capacity // 最大容量
this.size = 0 // 已使用容量
this.list = new DualLinkedList()
this.cacheMap = new Map() // key-node
}
/* 根据key获取value（不存在返回-1），借助cacheMap实现 */
get (key) {
if (this.cacheMap.has(key)) {
let node = this.cacheMap.get(key)
this.list.remove(node)
this.list.add(node)
return node.value
}
return -1
}
/* 添加节点 */
put (key, value) {
let node = new Node(key, value)
// 已存在移到head处
if (this.cacheMap.has(key)) {
let oNode = this.cacheMap.get(key)
this.list.remove(oNode)
this.list.add(node)
this.cacheMap.set(key, node)
return
}
// 不存在需要追加
this.list.add(node)
this.cacheMap.set(key, node)
this.size = 1
// 容量超出，删除尾部节点（最久未使用）
if (this.size > this.capacity) {
let lastNode = this.list.tail.pre
this.list.remove(lastNode)
this.cacheMap.delete(lastNode.key)
}
}
}复杂度：
- 时间复杂度：对于 put 和 get 都是 O(1)。
- 空间复杂度：O(capacity)
map 具备 LRU 特性
map.delete(key) 再 map.set(key, value) 则 map 对应的key被移到了尾部。
示例：map 具备 LRU 性质
代码语言：javascript复制let map = new Map()
map.set('a', 1)
map.set('b', 2)
map.set('c', 3)
console.log(map) // {'a' => 1, 'b' => 2, 'c' => 3}
map.delete('b')
console.log(map) // {'a' => 1, 'c' => 3}
map.set('b', 2)
console.log(map) // {'a' => 1, 'c' => 3, 'b' => 2}LRU 实现： 和上述不同的是，最近被使用的存储在 map 最后，第一个 key 为最久未被使用的。
代码语言：javascript复制var LRUCache = function (capacity) {
this.capacity = capacity
this.cacheMap = new Map()
}
LRUCache.prototype.get = function (key) {
if (this.cacheMap.has(key)) {
const value = this.cacheMap.get(key)
this.cacheMap.delete(key)
this.cacheMap.set(key, value) // 重新插入的 key-value 被追加到了尾部
return value
} else {
return -1
}
}
LRUCache.prototype.put = function (key, value) {
if (this.cacheMap.has(key)) this.cacheMap.delete(key) // 存在删除当前 key
if (this.cacheMap.size === this.capacity) this.cacheMap.delete(this.cacheMap.keys().next().value) // 删除第一个 key 值
this.cacheMap.set(key, value)
}复杂度：
- 时间复杂度：对于 put 和 get 都是 O(1)。
- 空间复杂度：O(capacity)
