LRU 是 Least Recently Used 的縮寫，即最近最少使用。作為一種經典的緩存策略，它的基本思想是長期不被使用的數據，在未來被用到的幾率也不大，所以當新的數據進來時我們可以優先把這些數據替換掉。 一、基本要求 固定大小：限制記憶體使用。 快速訪問：緩存插入和查找操作應該很快，最好是 O ...
LRU 是 Least Recently Used 的縮寫，即最近最少使用。作為一種經典的緩存策略，它的基本思想是長期不被使用的數據，在未來被用到的幾率也不大，所以當新的數據進來時我們可以優先把這些數據替換掉。
一、基本要求
- 固定大小：限制記憶體使用。
- 快速訪問：緩存插入和查找操作應該很快，最好是 O(1) 時間。
- 在達到記憶體限制的情況下替換條目：緩存應該具有有效的演算法來在記憶體已滿時驅逐條目。
二、數據結構
下麵提供兩種實現方式，並完成相關代碼。
2.1 Map
在 Javascript 中，Map 的 key 是有序的，當迭代的時候，他們以插入的順序返回鍵值。結合這個特性，我們也通過 Map 實現 LRU 演算法。
2.2 Doubly Linked List
我們也可通過雙向鏈表（Doubly Linked List）維護緩存條目，通過對鏈表的增、刪、改實現數據管理。為確保能夠從鏈表中快速讀取某個節點的數據，我們可以通過 Map 來存儲對鏈表中節點的引用。
三、Map 實現
在 初始化時 完成兩件事情：
- 配置存儲限制，當大於此限制，緩存條目將按照最近讀取情況被驅逐。
- 創建一個用於存儲緩存數據的 Map 。
在 添加數據 時：
- 判斷當前存儲數據中是否包含新進數據，如果存在，則刪除當前數據
- 判斷當前存儲空間是否被用盡，如果已用盡則刪除 Map 頭部的數據。
map.delete(map.keys().next().value) - 插入新數據到 Map 的尾部
基於 Javascript Map 實現 LRU，代碼如下：
class LRUCache {
size = 5
constructor(size) {
this.cache = new Map()
this.size = size || this.size
}
get(key) {
if (this.cache.has(key)) {
// 存在即更新
let temp = this.cache.get(key)
this.cache.delete(key)
this.cache.set(key, temp)
return temp
}
return null
}
set(key, value) {
if (this.cache.has(key)) {
this.cache.delete(key)
}
if (this.cache.size >= this.size) {
this.cache.delete(this.cache.keys().next().value)
}
this.cache.set(key, value)
}
}
四、雙向鏈表實現
4.1 定義節點類
包含 prev，next，data 三個屬性，分別用以存儲指向前後節點的引用，以及當前節點要存儲的數據。
{
prev: Node
next: Node
data: { key: string, data: any}
}
4.2 定義鏈表類
包含 head、tail 屬性，分別指向鏈表的 頭節點 和 尾節點。
當從鏈表中讀取數據時，需要將當前讀取的數據移動到鏈表頭部；添加數據時，將新節點插入到頭部；當鏈表節點數量大於限定的閥值，需要從鏈表尾部刪除節點。
{
head: Node
next: Node
moveNodeToHead(node)
insertNodeToHead(node)
deleteLastNode()
}
4.3 定義 LRU 類
為 LRU 定義屬性：linkLine 用以存儲指向鏈表的引用；size 用以配置存儲空間大小限制；
為簡化從鏈表中查找節點，再定義 map 屬性，用以存儲不同鍵指向鏈表節點的引用。
定義成員方法，set(key,value) 用以添加數據，get(key) 讀取一條數據。
4.4 set(key,value)
- 如果 map 中存在當前 key，則修改當前節點的值，然後從鏈表中把當前節點移動到鏈表頭部；
- 否則：
- 判斷當前鏈表節點數量是否達到了存儲上線，如果是，則刪除鏈表尾部的節點。同時從 map 中移除相應的節點引用；
- 創建新節點，然後插入到鏈表頭部，並添加 map 引用。
4.5 get(key)
如果 map 中存在當前 key，從鏈表中讀取節點，將其移動到鏈表頭部，並返回結果，否則返回空。
{
linkLine: LinkLine
map: Map
size: Number
set(key, value)
get(key)
}
4.6 代碼實現
class LinkNode {
prev = null
next = null
constructor(key, value) {
this.data = { key, value }
}
}
class LinkLine {
head = null
tail = null
constructor() {
const headNode = new LinkNode('head', 'head')
const tailNode = new LinkNode('tail', 'tail')
headNode.next = tailNode
tailNode.prev = headNode
this.head = headNode
this.tail = tailNode
}
moveNodeToFirst(node) {
node.prev.next = node.next
node.next.prev = node.prev
this.insertNodeToFirst(node)
}
insertNodeToFirst(node) {
const second = this.head.next
this.head.next = node
node.prev = this.head
node.next = second
second.prev = node
}
delete(node) {
node.prev.next = node.next
node.next.prev = node.prev
}
deleteLastNode() {
const last = this.tail.prev
this.tail.prev = last.prev
last.prev.next = this.tail
return last
}
}
class LRUCache {
linkLine = null
map = {}
size = 5
constructor(size) {
this.size = size || this.size
this.linkLine = new LinkLine
}
get(key) {
let value
if (this.map[key]) {
const node = this.map[key]
value = node.value
this.linkLine.moveNodeToFirst(node)
}
return value
}
set(key, value) {
if (this.map[key]) {
const node = this.map[key]
node.value = value
this.linkLine.moveNodeToFirst(node)
} else {
// 刪除最後一個元素
if (Object.keys(this.map).length >= this.size) {
const lastNode = this.linkLine.deleteLastNode()
delete this.map[lastNode.data.key]
}
const newNode = new LinkNode(key, value)
this.linkLine.insertNodeToFirst(newNode)
this.map[key] = newNode
}
}
}
https://gauliang.github.io/blogs/2022/lru-algorithm/
識微見遠 格物致知
