LRU 是 Least Recently Used 的縮寫(xiě)，即最近最少使用。作為一種經(jīng)典的緩存策略，它的基本思想是長(zhǎng)期不被使用的數(shù)據(jù)，在未來(lái)被用到的幾率也不大，所以當(dāng)新的數(shù)據(jù)進(jìn)來(lái)時(shí)我們可以優(yōu)先把這些數(shù)據(jù)替換掉。
目前創(chuàng)新互聯(lián)建站已為上1000家的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)站空間、綿陽(yáng)服務(wù)器托管、企業(yè)網(wǎng)站設(shè)計(jì)、豐臺(tái)網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長(zhǎng)，共同發(fā)展。
下面提供兩種實(shí)現(xiàn)方式，并完成相關(guān)代碼。
在 Javascript 中，Map 的 key 是有序的，當(dāng)?shù)臅r(shí)候，他們以插入的順序返回鍵值。結(jié)合這個(gè)特性，我們也通過(guò) Map 實(shí)現(xiàn) LRU 算法。
我們也可通過(guò)雙向鏈表（Doubly Linked List）維護(hù)緩存條目，通過(guò)對(duì)鏈表的增、刪、改實(shí)現(xiàn)數(shù)據(jù)管理。為確保能夠從鏈表中快速讀取某個(gè)節(jié)點(diǎn)的數(shù)據(jù)，我們可以通過(guò) Map 來(lái)存儲(chǔ)對(duì)鏈表中節(jié)點(diǎn)的引用。
在 初始化時(shí) 完成兩件事情：
在 添加數(shù)據(jù) 時(shí)：
重慶分公司
重慶分公司
map.delete(map.keys().next().value)基于 Javascript Map 實(shí)現(xiàn) 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)
}
}
包含 prev，next，data 三個(gè)屬性，分別用以存儲(chǔ)指向前后節(jié)點(diǎn)的引用，以及當(dāng)前節(jié)點(diǎn)要存儲(chǔ)的數(shù)據(jù)。
{
prev: Node
next: Node
data: { key: string, data: any}
}
包含 head、tail 屬性，分別指向鏈表的 頭節(jié)點(diǎn) 和 尾節(jié)點(diǎn)。
當(dāng)從鏈表中讀取數(shù)據(jù)時(shí)，需要將當(dāng)前讀取的數(shù)據(jù)移動(dòng)到鏈表頭部；添加數(shù)據(jù)時(shí)，將新節(jié)點(diǎn)插入到頭部；當(dāng)鏈表節(jié)點(diǎn)數(shù)量大于限定的閥值，需要從鏈表尾部刪除節(jié)點(diǎn)。
{
head: Node
next: Node
moveNodeToHead(node)
insertNodeToHead(node)
deleteLastNode()
}
為 LRU 定義屬性：linkLine 用以存儲(chǔ)指向鏈表的引用；size 用以配置存儲(chǔ)空間大小限制；
為簡(jiǎn)化從鏈表中查找節(jié)點(diǎn)，再定義 map 屬性，用以存儲(chǔ)不同鍵指向鏈表節(jié)點(diǎn)的引用。
定義成員方法，set(key,value) 用以添加數(shù)據(jù)，get(key) 讀取一條數(shù)據(jù)。
如果 map 中存在當(dāng)前 key，從鏈表中讀取節(jié)點(diǎn)，將其移動(dòng)到鏈表頭部，并返回結(jié)果，否則返回空。
{
linkLine: LinkLine
map: Map
size: Number
set(key, value)
get(key)
}
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 {
// 刪除最后一個(gè)元素
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/
