LRU緩存算法的實(shí)現(xiàn)方法是什么

這篇文章主要講解了“LRU緩存算法的實(shí)現(xiàn)方法是什么”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“LRU緩存算法的實(shí)現(xiàn)方法是什么”吧！

LRU就是Least Recently  Used，即最近最少使用，是一種常用的頁面置換算法，將最近長(zhǎng)時(shí)間未使用的頁面淘汰，其實(shí)也很簡(jiǎn)單，就是要將不受歡迎的頁面及時(shí)淘汰，不讓它占著茅坑不拉shit，浪費(fèi)資源。

LRU是一種常見的頁面置換算法，在計(jì)算中，所有的文件操作都要放在內(nèi)存中進(jìn)行，然而計(jì)算機(jī)內(nèi)存大小是固定的，所以我們不可能把所有的文件都加載到內(nèi)存，因此我們需要制定一種策略對(duì)加入到內(nèi)存中的文件進(jìn)項(xiàng)選擇。

常見的頁面置換算法有如下幾種：

• LRU 最近最久未使用

• FIFO 先進(jìn)先出置換算法 類似隊(duì)列

• OPT 最佳置換算法 (理想中存在的)

• NRU Clock置換算法

• LFU 最少使用置換算法

• PBA 頁面緩沖算法

LRU原理

LRU的設(shè)計(jì)原理就是，當(dāng)數(shù)據(jù)在最近一段時(shí)間經(jīng)常被訪問，那么它在以后也會(huì)經(jīng)常被訪問。這就意味著，如果經(jīng)常訪問的數(shù)據(jù)，我們需要然其能夠快速命中，而不常訪問的數(shù)據(jù)，我們?cè)谌萘砍鱿拗苾?nèi)，要將其淘汰。

其核心就是利用棧，進(jìn)行操作，其中主要有兩項(xiàng)操作，get和put

get

get時(shí)，若棧中有值則將該值的key提到棧頂，沒有時(shí)則返回null

put

棧未滿時(shí)，若棧中有要put的key，則更新此key對(duì)應(yīng)的value，并將該鍵值提到棧頂，若無要put的key，直接入棧

棧滿時(shí)，若棧中有要put的key，則更新此key對(duì)應(yīng)的value，并將該鍵值提到棧頂;若棧中沒有put的key  時(shí)，去掉棧底元素，將put的值入到棧頂

解法：維護(hù)一個(gè)數(shù)組，提供 get 和 put 方法，并且限定 max 數(shù)量。

使用時(shí)，get 可以標(biāo)記某個(gè)元素是最新使用的，提升它去第一項(xiàng)。put 可以加入某個(gè)key-value，但需要判斷是否已經(jīng)到最大限制 max

若未到能直接往數(shù)組第一項(xiàng)里插入 若到了最大限制 max，則需要淘汰數(shù)據(jù)尾端一個(gè)元素。

LRUCache cache = new LRUCache( 2 /* 緩存容量 */ );  cache.put(1, 1); cache.put(2, 2); cache.get(1);       // 返回  1 cache.put(3, 3);    // 該操作會(huì)使得密鑰 2 作廢 cache.get(2);       // 返回 -1 (未找到) cache.put(4, 4);    // 該操作會(huì)使得密鑰 1 作廢 cache.get(1);       // 返回 -1 (未找到) cache.get(3);       // 返回  3 cache.get(4);       // 返回  4

LRU 算法設(shè)計(jì)

分析上面的操作過程，要讓 put 和 get 方法的時(shí)間復(fù)雜度為 O(1)，我們可以總結(jié)出 cache  這個(gè)數(shù)據(jù)結(jié)構(gòu)必要的條件：查找快，插入快，刪除快，有順序之分。

因?yàn)轱@然 cache 必須有順序之分，以區(qū)分最近使用的和久未使用的數(shù)據(jù);而且我們要在 cache  中查找鍵是否已存在;如果容量滿了要?jiǎng)h除最后一個(gè)數(shù)據(jù);每次訪問還要把數(shù)據(jù)插入到隊(duì)頭。

那么，什么數(shù)據(jù)結(jié)構(gòu)同時(shí)符合上述條件呢?哈希表查找快，但是數(shù)據(jù)無固定順序;鏈表有順序之分，插入刪除快，但是查找慢。所以結(jié)合一下，形成一種新的數(shù)據(jù)結(jié)構(gòu)：哈希鏈表。

LRU 緩存算法的核心數(shù)據(jù)結(jié)構(gòu)就是哈希鏈表，雙向鏈表和哈希表的結(jié)合體。這個(gè)數(shù)據(jù)結(jié)構(gòu)長(zhǎng)這樣：

js 實(shí)現(xiàn)

• 具體代碼 一般的解法，通過維護(hù)一個(gè)數(shù)組，數(shù)組項(xiàng)存放了 key-value 鍵值對(duì)對(duì)象，每次需要遍歷去尋找 key 值所在的數(shù)組下標(biāo)操作。

已經(jīng)通過 leetCode 146 的檢測(cè)。執(zhí)行用時(shí) : 720 ms。內(nèi)存消耗 : 58.5 MB。

function LRUCache(capacity) {     this.capacity = capacity;   // 最大限制     this.cache = []; };  /**  * @param {number} key  * @return {number}  */ LRUCache.prototype.get = function (key) {     let index = this.cache.findIndex((item) => item.key === key);     if (index === -1) {         return -1;     }     // 刪除此元素后插入到數(shù)組第一項(xiàng)     let value = this.cache[index].value;     this.cache.splice(index, 1);     this.cache.unshift({         key,         value,     });     return value; };  /**  * @param {number} key  * @param {number} value  * @return {void}  */ LRUCache.prototype.put = function (key, value) {     let index = this.cache.findIndex((item) => item.key === key);     // 想要插入的數(shù)據(jù)已經(jīng)存在了，那么直接提升它就可以     if (index > -1) {         this.cache.splice(index, 1);     } else if (this.cache.length >= this.capacity) {         // 若已經(jīng)到達(dá)最大限制，先淘汰一個(gè)最久沒有使用的         this.cache.pop();     }     this.cache.unshift({ key, value }); };

上面的做法其實(shí)有變種，可以通過一個(gè)對(duì)象來存鍵值對(duì)，一個(gè)數(shù)組來存放鍵的順序。

• 進(jìn)階要求O(1)

時(shí)間復(fù)雜度 O(1)，那就不能數(shù)組遍歷去查找 key 值?？梢杂?ES6 的 Map 來解了，因?yàn)?Map 既能保持鍵值對(duì)，還能記住插入順序。

function LRUCache(capacity) {     this.cache = new Map();     this.capacity = capacity;  // 最大限制 };  LRUCache.prototype.get = function (key) {     if (this.cache.has(key)) {         // 存在即更新         let temp = this.cache.get(key);         this.cache.delete(key);         this.cache.set(key, temp);         return temp;     }     return -1; };  LRUCache.prototype.put = function (key, value) {     if (this.cache.has(key)) {         // 存在即更新（刪除后加入）         this.cache.delete(key);     } else if (this.cache.size >= this.capacity) {         // 不存在即加入         // 緩存超過最大值，則移除最近沒有使用的         this.cache.delete(this.cache.keys().next().value);     }     this.cache.set(key, value); };

感謝各位的閱讀，以上就是“LRU緩存算法的實(shí)現(xiàn)方法是什么”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對(duì)LRU緩存算法的實(shí)現(xiàn)方法是什么這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！