背景

最近沒(méi)事看公司自研ssr框架feb，注意到里面頁(yè)面級(jí)緩存和組件級(jí)緩存用到了LRU緩存，這讓我想起了之前看keep-alive源碼，貌似也是使用了LRU緩存。之前看過(guò)redis的文章，好像也是基于這個(gè)理念實(shí)現(xiàn)的；在刷leetcode的時(shí)候，有時(shí)候也會(huì)碰到類似LRU的題目。今天記錄一下LRU算法，加深我們對(duì)這塊的印象。

研究

LRU （Least recently used：最近最少使用）最近被訪問(wèn)的，被訪問(wèn)的幾率變大。最少被訪問(wèn)的，當(dāng)磁盤被寫滿時(shí)，會(huì)被清除。

一張圖來(lái)理解一下：

假設(shè)我們有一塊內(nèi)存，一共能夠存儲(chǔ) 5 數(shù)據(jù)塊；

依次向內(nèi)存存入A、B、C、D、E，此時(shí)內(nèi)存已經(jīng)存滿；

再次插入新的數(shù)據(jù)時(shí)，會(huì)將在內(nèi)存存放時(shí)間最久的數(shù)據(jù)A淘汰掉；

當(dāng)我們?cè)谕獠吭俅巫x取數(shù)據(jù)B時(shí)，已經(jīng)處于末尾的B會(huì)被標(biāo)記為活躍狀態(tài)，提到頭部，數(shù)據(jù)C就變成了存放時(shí)間最久的數(shù)據(jù)；

再次插入新的數(shù)據(jù)G，存放時(shí)間最久的數(shù)據(jù)C就會(huì)被淘汰掉；

算法實(shí)現(xiàn)

class LRUCache {// 存儲(chǔ)數(shù)據(jù)put (key, value) {if (this.cache[key]) {// 如果該 key 之前存在，將 key 重新激活this.active(key)this.cache[key] = value// 而且此時(shí)緩存的長(zhǎng)度不會(huì)發(fā)生變化// 所以不需要進(jìn)行后續(xù)的長(zhǎng)度判斷，可以直接返回return} ?// 存儲(chǔ)之前需要先判斷長(zhǎng)度是否達(dá)到上限if (this.list.length >= this.capacity) {// 由于每次存儲(chǔ)后，都會(huì)將 key 放入 list 最后，// 所以，需要取出第一個(gè) key，并刪除cache中的數(shù)據(jù)。const latest = this.list.shift()delete this.cache[latest]}// 寫入緩存this.cache[key] = value// 寫入緩存后，需要將 key 放入 list 的最后this.list.push(key)} }

總結(jié)

以上是生活随笔為你收集整理的对LRU算法的理解和应用场景的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。