JavaScript實(shí)現(xiàn)LRU緩存的三種方式詳解
LRU全稱為Least Recently Used，即最近使用的。針對(duì)的是在有限的內(nèi)存空間內(nèi)，只緩存最近使用的數(shù)據(jù)（即get和set的數(shù)據(jù)），超過有限內(nèi)存空間的數(shù)據(jù)將會(huì)被刪除。這個(gè)在面試題中也是常會(huì)被問到的內(nèi)容，接下來就看看怎么來實(shí)現(xiàn)。
分析
從定義來看，LRU至少有兩個(gè)特性：通過鍵值對(duì)讀寫、有序。實(shí)現(xiàn)鍵值對(duì)讀寫，一般我們會(huì)使用哈希表來表示，注意哈希表是一個(gè)邏輯結(jié)構(gòu)，實(shí)際上我們需要使用object、map等來實(shí)現(xiàn)；數(shù)據(jù)有序，即最近使用的數(shù)據(jù)放在前面，已經(jīng)過時(shí)的數(shù)據(jù)放在后面或被刪除，并且支持?jǐn)?shù)據(jù)是可排序的，我們可以想到數(shù)組、鏈表、map之類的數(shù)據(jù)格式。因此，我們有三種方式可以實(shí)現(xiàn)LRU緩存：
- Map
- Object + Array
- LinkedList
使用Map實(shí)現(xiàn)LRU緩存
Map對(duì)象保存的是鍵值對(duì)，并且可以記住鍵的原始插入順序。
const map = new Map();
map.set(2, 2);
map.set(1, 2);
console.log(map); // Map(2) {2 => 2, 1 => 2}，按照原始的插入順序
const obj = new Object();
obj[2] = 2;
obj[1] = 1
console.log(obj); // {1: 1, 2: 2}，不會(huì)按照原始的插入順序
那么我們就可以根據(jù)Map的特性實(shí)現(xiàn)LRU，下面是原理圖：
實(shí)現(xiàn)代碼：
class LRUCache {
data = new Map(); // 數(shù)據(jù)map
constructor(length) {
if (length < 1) throw new Error('長度不能小于1')
this.length = length
}
set(key, value) {
const data = this.data;
// 如果存在該對(duì)象,則直接刪除
if (data.has(key)) {
data.delete(key);
}
// 將數(shù)據(jù)對(duì)象添加到map中
data.set(key, value);
if (data.size > this.length) {
// 如果map長度超過最大值,則取出map中的第一個(gè)元素,然后刪除
const delKey = data.keys().next().value
data.delete(delKey);
}
}
get(key) {
const data = this.data;
// 數(shù)據(jù)map中沒有key對(duì)應(yīng)的數(shù)據(jù),則返回null
if (!data.has(key)) return null;
const value = data.get(key);
// 返回?cái)?shù)據(jù)前,先刪除原數(shù)據(jù),然后在添加,就可以保持在最新
data.delete(key);
data.set(key, value);
return value;
}
}
測(cè)試一下：
const lruCache = new LRUCache(2);
lruCache.set('1', 1); // Map(1) {1 => 1}
lruCache.set('2',2); // Map(2) {1 => 1, 2 => 2}
console.log(lruCache.get('1')); // Map(2) {2 => 2, 1 => 1}
lruCache.set('3',3); // Map(2) {1 => 1, 3 => 3}
console.log(lruCache.get('2')); // null
lruCache.set('4',4); // Map(2) {3 => 3, 4 => 4}
console.log(lruCache.get('1')); // null
console.log(lruCache.get('3')); // Map(2) {4 => 4, 3 => 3}
console.log(lruCache.get('4')); // Map(2) {3 => 3, 4 => 4}
運(yùn)行結(jié)果：
使用Map基本上就可以實(shí)現(xiàn)LRU緩存，并且其兼容性還可以，除了IE兼容性差點(diǎn)：
如果不使用Map，那么還可以使用什么方式實(shí)現(xiàn)LRU緩存呢？
使用Object + Array實(shí)現(xiàn)LRU緩存
剛剛我們也分析了，LRU需要滿足兩點(diǎn)：鍵值對(duì)和可排序，這兩點(diǎn)可以分別對(duì)應(yīng)到Object和Array，那么我們是不是就可以以此為思路實(shí)現(xiàn)呢？答案是可以的，實(shí)現(xiàn)代碼：
class LRUCacheObjArr {
length = 0; // 定義列表最大長度
dataObj = {}; // 使用對(duì)象暫存數(shù)據(jù),在可保證get時(shí)間復(fù)雜度為O(1)
dataArr = []; // 使用數(shù)組解決有序的問題
constructor(length) {
if (length < 1) throw new Error('參數(shù)非法')
this.length = length;
}
get(key) {
if (!this.dataObj[key] || !this.dataArr.length) return null;
// 需要將訪問到的值,重新放在數(shù)組的最末尾,表示最新的數(shù)據(jù)
const index = this.dataArr.findIndex(item => item.key === key);
// 先刪除原數(shù)據(jù),然后push到數(shù)組末尾
this.dataArr.splice(index, 1);
this.dataArr.push(this.dataObj[key]);
// 返回值,對(duì)象是無序的,我們只需要保證里面的數(shù)據(jù)是最新的即可
return this.dataObj[key].value;
}
set(key, value) {
// 定義對(duì)象數(shù)據(jù)
const obj = {key, value};
const index = this.dataArr.findIndex(item => item.key === key);
// 判斷是否為新增還是修改
if (index !== -1) {
// 如果已存在數(shù)據(jù),則先刪除,然后push到末尾
this.dataArr.splice(index, 1);
this.dataArr.push(obj);
} else {
// 如果不存在數(shù)據(jù),則數(shù)組直接push
this.dataArr.push(obj);
}
// 對(duì)象新增或者修改同一個(gè)對(duì)象
this.dataObj[key] = obj;
// 判斷新增數(shù)據(jù)后,是否超過最大長度
if (this.dataArr.length > this.length) {
// 數(shù)組是有序的,超長后直接從頭部刪除,并且獲取刪除的數(shù)據(jù)
const tmp = this.dataArr.shift();
// 數(shù)據(jù)對(duì)象里面也應(yīng)該刪除當(dāng)前刪除的對(duì)象,避免被再次取到
delete this.dataObj[tmp.key];
}
}
}
我們使用同樣的測(cè)試案例測(cè)試一下：
const lruCache = new LRUCacheObjArr(2);
lruCache.set('1', 1); // dataArr(1) [obj1], dataObj(1) {'1': obj1}
lruCache.set('2',2); // dataArr(2) [obj1, obj2], dataObj(2) {'1': obj1, '2': obj2}
console.log(lruCache.get('1')); // dataArr(2) [obj2, obj1], dataObj(2) {'1': obj1, '2': obj2}
lruCache.set('3',3); // dataArr(2) [obj1, obj3], dataObj(2) {'1': obj1, '3': obj3}
console.log(lruCache.get('2')); // null
lruCache.set('4',4); // dataArr(2) [obj3, obj4], dataObj(2) {'3': obj3, '4': obj4}
console.log(lruCache.get('1')); // null
console.log(lruCache.get('3')); // dataArr(2) [obj4, obj3], dataObj(2) {'3': obj3, '4': obj4}
console.log(lruCache.get('4')); // dataArr(2) [obj3, obj4], dataObj(2) {'3': obj3, '4': obj4}
運(yùn)行結(jié)果：
使用對(duì)象+數(shù)組的方式，雖然可以實(shí)現(xiàn)效果，但是由于會(huì)頻繁操作數(shù)組，因此會(huì)犧牲一些性能，而且實(shí)現(xiàn)起來也沒有Map方便。除了使用數(shù)組+對(duì)象，其實(shí)我們還可以使用雙向鏈表的方式實(shí)現(xiàn)LRU。
使用雙向鏈表實(shí)現(xiàn)LRU
雙向鏈表，顧名思義就是兩個(gè)方向的鏈表，這有別于單向鏈表。直接看圖可能更直觀一點(diǎn)：
雙向鏈表在移動(dòng)元素時(shí)，會(huì)比單向鏈表復(fù)雜一點(diǎn),，例如我們想把B和C節(jié)點(diǎn)交換一下位置，其過程如下：
這對(duì)應(yīng)到LRU有什么意義呢？雙向鏈表是有序的，每一個(gè)節(jié)點(diǎn)都知道其上一個(gè)或者下一個(gè)節(jié)點(diǎn)；其存值的方式也是使用鍵值對(duì)的方式，因此完全可以實(shí)現(xiàn)LRU。
實(shí)現(xiàn)代碼：
class LRUCacheLinked {
data = {}; // 鏈表數(shù)據(jù)
dataLength = 0; // 鏈表長度,使用變量保存,可以更快訪問
listHead = null; // 鏈表頭部
listTail = null; // 鏈表尾部
length = 0; // 鏈表最大長度
// 構(gòu)造函數(shù)
constructor(length) {
if (length < 1) throw new Error('參數(shù)不合法')
this.length = length;
}
set(key, value) {
const curNode = this.data[key];
if (curNode == null) {
// 新增數(shù)據(jù)
const nodeNew = {key, value};
// 移動(dòng)到末尾
this.moveToTail(nodeNew);
// 將新增的節(jié)點(diǎn)保存到數(shù)據(jù)對(duì)象中,其pre或next將在moveToTail中設(shè)置
this.data[key] = nodeNew;
// 鏈表長度遞增
this.dataLength++;
// 初始化鏈表頭部
if (this.dataLength === 1) this.listHead = nodeNew;
} else {
// 修改現(xiàn)有數(shù)據(jù)
curNode.value = value;
// 移動(dòng)到末尾
this.moveToTail(curNode);
}
// 添加完數(shù)據(jù)后可能會(huì)導(dǎo)致超出長度,因此嘗試著刪除數(shù)據(jù)
this.tryClean();
}
get(key) {
// 根據(jù)key值取出對(duì)應(yīng)的節(jié)點(diǎn)
const curNode = this.data[key];
if (curNode == null) return null;
if (this.listTail === curNode) {
// 如果被訪問的元素處于鏈表末尾，則直接返回值，且不用修改鏈表
return curNode.value;
}
// 如果是中間元素或者頭部元素，則在獲取前需要將其移動(dòng)到鏈表尾部,表示最新
this.moveToTail(curNode);
return curNode.value;
}
// 移動(dòng)節(jié)點(diǎn)到鏈表尾部
moveToTail(curNode) {
// 獲取鏈表尾部
const tail = this.listTail;
// 如果當(dāng)前節(jié)點(diǎn)就是鏈表尾部,則不做處理,直接返回
if (tail === curNode) return;
// 1. preNode和nextNode斷絕與curNode之間的關(guān)系
const preNode = curNode.pre;
const nextNode = curNode.next;
if (preNode) {
if (nextNode) {
// 當(dāng)前元素的上一個(gè)節(jié)點(diǎn)指向其下一個(gè)
preNode.next = nextNode;
} else {
// 斷開當(dāng)前元素與上一個(gè)節(jié)點(diǎn)的聯(lián)系
delete preNode.next;
}
}
if (nextNode) {
if (preNode) {
// 當(dāng)前元素的下一個(gè)節(jié)點(diǎn)指向其上一個(gè)
nextNode.pre = preNode;
} else {
// 斷開當(dāng)前元素與下一個(gè)節(jié)點(diǎn)的關(guān)系
delete nextNode.pre;
}
// 如果當(dāng)前節(jié)點(diǎn)是鏈表頭部,則需要重新賦值
if (this.listHead === curNode) this.listHead = nextNode;
}
// 2. curNode斷絕與preNode和nextNode之間的關(guān)系
delete curNode.pre
delete curNode.next
// 3. 在list末尾,重新建立curNode的新關(guān)系
if (tail) {
tail.next = curNode;
curNode.pre = tail;
}
// 重新賦值鏈表尾部,保持最新
this.listTail = curNode;
}
tryClean() {
while(this.dataLength > this.length) {
const head = this.listHead;
if (head == null) throw new Error('鏈表缺少頭部');
const headNext = head.next;
if (headNext == null) throw new Error('鏈表頭部缺失下一個(gè)節(jié)點(diǎn)');
// 1. 斷絕head和headNext之間的關(guān)系
delete head.next;
delete headNext.pre;
// 2. 重新賦值listHead
this.listHead = headNext;
// 3. 清理data
delete this.data[head.key];
// 4. 重新計(jì)數(shù)
this.dataLength = this.dataLength - 1;
}
}
}
這么一看，雙向鏈表是這三種方式中最復(fù)雜的一個(gè)。我們使用同樣的案例測(cè)試一下：
const lruCache = new LRUCacheLinked(2);
lruCache.set('1', 1);
lruCache.set('2',2);
console.log(lruCache.get('1'));
lruCache.set('3',3);
console.log(lruCache.get('2'));
lruCache.set('4',4);
console.log(lruCache.get('1'));
console.log(lruCache.get('3'));
console.log(lruCache.get('4'));
實(shí)現(xiàn)結(jié)果：
總結(jié)
本文總結(jié)了三種實(shí)現(xiàn)LRU緩存的方法，其中使用Map是最佳的方式。使用其他兩種方式，雖然可以實(shí)現(xiàn)效果，但是從效率、可讀性上來看，還是Map更勝一籌。這三種方式你都學(xué)會(huì)了嗎？
到此這篇關(guān)于JavaScript實(shí)現(xiàn)LRU緩存的三種方式詳解的文章就介紹到這了,更多相關(guān)JavaScript LRU緩存內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
原生js實(shí)現(xiàn)秒表計(jì)時(shí)器功能
這篇文章主要為大家詳細(xì)介紹了原生js實(shí)現(xiàn)秒表計(jì)時(shí)器功能，可以開始、暫停、清除，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-02-02
這篇文章主要為大家詳細(xì)介紹了js鼠標(biāo)跟隨運(yùn)動(dòng)效果的相關(guān)資料，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-03-03
清華大學(xué)出版的事半功倍系列 javascript全部源代碼
清華大學(xué)出版的事半功倍系列 javascript全部源代碼...2007-05-05
這篇文章主要介紹了Javascript Worker子線程代碼實(shí)例,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-02-02
JavaScript數(shù)組中相同的元素進(jìn)行分組(數(shù)據(jù)聚合)groupBy函數(shù)詳解
今天在打算從js端時(shí)序數(shù)據(jù)庫TSDB中,按相同的類型的數(shù)據(jù)排在一起,并且取同一時(shí)間段最新的數(shù)據(jù),經(jīng)過查詢這種思想叫做數(shù)據(jù)聚合,就是返回的數(shù)據(jù)要根據(jù)一個(gè)屬性來做計(jì)算,這篇文章主要介紹了JavaScript數(shù)組中相同的元素進(jìn)行分組(數(shù)據(jù)聚合)?groupBy函數(shù),需要的朋友可以參考下2023-12-12
這篇文章主要介紹了js對(duì)字符的驗(yàn)證方法,實(shí)例匯總了漢字驗(yàn)證、手機(jī)驗(yàn)證、郵箱驗(yàn)證、身份證號(hào)驗(yàn)證等各種常用技巧,需要的朋友可以參考下2015-02-02
在寫JS跳轉(zhuǎn)語句的過程中，發(fā)現(xiàn)這么一個(gè)問題，location.href語句與火狐不兼容的問題2010-07-07
解析dom中的children對(duì)象數(shù)組元素firstChild,lastChild的使用
以下是對(duì)dom中的children對(duì)象數(shù)組元素firstChild,lastChild的使用進(jìn)行了詳細(xì)的分析介紹，需要的朋友可以參考下2013-07-07
JavaScript數(shù)據(jù)結(jié)構(gòu)之雙向鏈表
這篇文章主要為大家詳細(xì)介紹了JavaScript數(shù)據(jù)結(jié)構(gòu)之雙向鏈表，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-03-03
JavaScript冒泡算法原理與實(shí)現(xiàn)方法深入理解
這篇文章主要介紹了JavaScript冒泡算法,結(jié)合實(shí)例形式詳細(xì)分析了JavaScript冒泡算法基本原理、實(shí)現(xiàn)方法與相關(guān)注意事項(xiàng),需要的朋友可以參考下2020-06-06