LRU 最近最少使用，是一种常见的淘汰（置换）算法，选择最近最久未使用的予以淘汰。常用于内存管理。
浏览器 IndexedDB 达到存储上限后，自动清理采用的策略正是 LRU。
当可用磁盘空间已满时，配额管理器将根据LRU策略开始清除数据——最近最少使用的源将首先被删除，然后是下一个，直到浏览器不再超过限制。
我们使用临时存储跟踪每个源的“上次访问时间”。 一旦达到临时存储的全局限制（之后会有更多限制），我们将尝试查找所有当前未使用的源（即没有打开选项卡/应用程序的那些来保持打开的数据存储）。 然后根据“上次访问时间”对它们进行排序。 然后删除最近最少使用的源，直到有足够的空间来满足触发此源回收的请求。
– IndexedDB LRU策略
要求：初始化时指定最大容量 capacity，当缓存填满时，删除最近最少使用的项。
算法实现：双向链表 + 哈希表
-
节点：Node {key, value, pre, post}
- key、value
- pre、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
}
}
class LRUCache {
constructor (capacity) {
this.capacity = capacity // 最大容量
this.size = 0 // 已使用容量
this.list = new DuallinkedList()
this.cacheMap = new Map() // key-node
}
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 性质
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 为最久未被使用的。
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(1) O(1)。
- 空间复杂度： O ( c a p a c i t y ) O(capacity) O(capacity)
