JavaScript手寫LRU算法的示例代碼
LRU 是 Least Recently Used 的縮寫,即最近最少使用。作為一種經(jīng)典的緩存策略,它的基本思想是長(zhǎng)期不被使用的數(shù)據(jù),在未來(lái)被用到的幾率也不大,所以當(dāng)新的數(shù)據(jù)進(jìn)來(lái)時(shí)我們可以優(yōu)先把這些數(shù)據(jù)替換掉。
一、基本要求
- 固定大小:限制內(nèi)存使用。
- 快速訪問(wèn):緩存插入和查找操作應(yīng)該很快,最好是 O(1) 時(shí)間。
- 在達(dá)到內(nèi)存限制的情況下替換條目:緩存應(yīng)該具有有效的算法來(lái)在內(nèi)存已滿時(shí)驅(qū)逐條目。
二、數(shù)據(jù)結(jié)構(gòu)
下面提供兩種實(shí)現(xiàn)方式,并完成相關(guān)代碼。
2.1 Map
在 Javascript 中,Map 的 key 是有序的,當(dāng)?shù)臅r(shí)候,他們以插入的順序返回鍵值。結(jié)合這個(gè)特性,我們也通過(guò) Map 實(shí)現(xiàn) LRU 算法。
2.2 Doubly Linked List
我們也可通過(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)的引用。
三、Map 實(shí)現(xiàn)
在 初始化時(shí) 完成兩件事情:
1.配置存儲(chǔ)限制,當(dāng)大于此限制,緩存條目將按照最近讀取情況被驅(qū)逐。
2.創(chuàng)建一個(gè)用于存儲(chǔ)緩存數(shù)據(jù)的 Map 。
在 添加數(shù)據(jù) 時(shí):
1.判斷當(dāng)前存儲(chǔ)數(shù)據(jù)中是否包含新進(jìn)數(shù)據(jù),如果存在,則刪除當(dāng)前數(shù)據(jù)
2.判斷當(dāng)前存儲(chǔ)空間是否被用盡,如果已用盡則刪除 Map 頭部的數(shù)據(jù)。
map.delete(map.keys().next().value)
3.插入新數(shù)據(jù)到 Map 的尾部
基于 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) } }
四、雙向鏈表實(shí)現(xiàn)
4.1 定義節(jié)點(diǎn)類
包含 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} }
4.2 定義鏈表類
包含 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() }
4.3 定義 LRU 類
為 LRU 定義屬性:linkLine
用以存儲(chǔ)指向鏈表的引用;size
用以配置存儲(chǔ)空間大小限制;
為簡(jiǎn)化從鏈表中查找節(jié)點(diǎn),再定義 map
屬性,用以存儲(chǔ)不同鍵指向鏈表節(jié)點(diǎn)的引用。
定義成員方法,set(key,value)
用以添加數(shù)據(jù),get(key)
讀取一條數(shù)據(jù)。
4.4 set(key,value)
如果 map 中存在當(dāng)前 key,則修改當(dāng)前節(jié)點(diǎn)的值,然后從鏈表中把當(dāng)前節(jié)點(diǎn)移動(dòng)到鏈表頭部;
否則:
判斷當(dāng)前鏈表節(jié)點(diǎn)數(shù)量是否達(dá)到了存儲(chǔ)上線,如果是,則刪除鏈表尾部的節(jié)點(diǎn)。同時(shí)從 map 中移除相應(yīng)的節(jié)點(diǎn)引用;
創(chuàng)建新節(jié)點(diǎn),然后插入到鏈表頭部,并添加 map 引用。
4.5 get(key)
如果 map 中存在當(dāng)前 key,從鏈表中讀取節(jié)點(diǎn),將其移動(dòng)到鏈表頭部,并返回結(jié)果,否則返回空。
{ linkLine: LinkLine map: Map size: Number set(key, value) get(key) }
4.6 代碼實(shí)現(xiàn)
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 } } }
到此這篇關(guān)于JavaScript手寫LRU算法的示例代碼的文章就介紹到這了,更多相關(guān)JavaScript LRU算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
解析為什么axios會(huì)有params和data兩個(gè)參數(shù)
本文給大家分享為什么axios會(huì)有params和data兩個(gè)參數(shù),先來(lái)回顧一下axios的基本使用,怎么發(fā)送一個(gè)請(qǐng)求,本文結(jié)合實(shí)例代碼給大家介紹的非常詳細(xì),感興趣的朋友跟隨小編一起看看吧2023-10-10JavaScript 關(guān)鍵字屏蔽實(shí)現(xiàn)函數(shù)
JavaScript屏蔽關(guān)鍵字,大概的思路就是去用javascript去替換已有的文本,達(dá)到替換的目的2009-08-08弱類型語(yǔ)言javascript開發(fā)中的一些坑實(shí)例小結(jié)【變量、函數(shù)、數(shù)組、對(duì)象、作用域等】
這篇文章主要介紹了弱類型語(yǔ)言javascript開發(fā)中的一些坑,結(jié)合實(shí)例形式總結(jié)分析了javascript開發(fā)中關(guān)于變量、函數(shù)、數(shù)組、對(duì)象、作用域等相關(guān)知識(shí)點(diǎn)常見易錯(cuò)問(wèn)題,需要的朋友可以參考下2019-08-08js實(shí)現(xiàn)點(diǎn)擊文本框顯示日期選擇器特效代碼分享
這篇文章主要為大家詳細(xì)介紹了javascript實(shí)現(xiàn)點(diǎn)擊文本框顯示日期選擇器特效,提高了工作效率,推薦給大家,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2015-08-08詳解使用Nuxt.js快速搭建服務(wù)端渲染(SSR)應(yīng)用
這篇文章主要介紹了詳解使用Nuxt.js快速搭建服務(wù)端渲染(SSR)應(yīng)用,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2019-03-03