當前位置：首頁 > 前端技术 > javascript >内容正文

javascript

【文科生带你读JavaScript数据结构与算法】2. 双向链表与LRU缓存算法原理与实现（下）

發布時間：2024/1/8 javascript 31 豆豆

生活随笔收集整理的這篇文章主要介紹了【文科生带你读JavaScript数据结构与算法】2. 双向链表与LRU缓存算法原理与实现（下）小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

上篇聊了聊雙向鏈表（doubly linked list）這個數據結構，今天就來點更實際的，也可以用雙鏈表來實現的一種生活工作中不可或缺的優化算法——LRU緩存（Least Recently Used Cache）算法。OK，直接進入正題吧。

打個廣告：歡迎關注我的B站主頁，本文也同步更新B站專欄文章

【松尾鷹志的個人空間-嗶哩嗶哩】https://b23.tv/NsEL2y9

原理篇

概念

基本思路

生活中的LRU緩存算法

前后端技術中的LRU緩存算法

代碼篇

雙向鏈表 + hashMap實現

ES6 Map實現

Complexities

原理篇

概念

依舊國際慣例，先上概念，懶得翻譯了，懂的都懂：

A?Least Recently Used (LRU) Cache?organizes items in order of use,?allowing you to quickly identify which item hasn't been used for the longest amount of time.

簡單概括一下，LRU緩存即“最近使用緩存”（Least Recently Used Cache），即使你不看上面這段概念，也能從字面上明白它是干嘛的。也就是在一個固定容量的空間內，只保存最近使用過的內容，太久沒用的就丟棄掉。

先來看張圖：

這張圖畫得非常直觀，左邊是一個最大容量為3的LRU緩存列表，右邊的幾行示例指的是LRU緩存算法的運行原理。

基本思路

那就開始舉例子吧，這個例子估計寫博客的很少有人說：

比如你的Switch里最多只能裝30G左右的游戲（為了方便解釋，這里假設每個游戲大小一樣都是10個G），也就是最多只能裝3個游戲，你要是想下載新買的《塞爾達傳說：王國之淚》，就得把目前最不想玩的那個游戲（你心目中那個linked list的尾節點）刪掉，才能下載最新的塞爾達，而當你開始下載時，在主界面上它也會跑到游戲列表的最前端。這就是LRU緩存的策略機制——最新使用的放在最前面，過期的就丟棄掉。

沒錯，PS、Xbox或者Switch等主機的游戲展示列表，本質上就是用LRU緩存算法去維護的。?下面我再用PS5舉例，隨便找了張兩年前的截圖來說明。

PS5主界面的快捷游戲列表一般最多可以展示9個（現在的最新版系統什么樣沒留意了）最近在玩的游戲，其余的會被回收進最右邊圖標鏈接的游戲資料庫里。如果用LRU緩存算法來處理這個游戲列表的維護，就需要考慮下面兩種情況：

CASE 1 玩快捷列表里有的游戲

這種情況比較簡單。假設我從當前正在玩的游戲中途按PS HOME鍵切回主界面，準備玩這個快捷列表中的另外一個游戲比如只狼，打開只狼后再看這個列表，PS5會執行這樣的操作：把只狼移到游戲列表的最前端（嚴謹一點說應該是PS商店圖標的右邊👉，NBA2K圖標的左邊👈），其他游戲依次往后移動一個方塊的位置。結果是所有這些游戲還是這些游戲，只不過排列順序發生了線性變化。

CASE 2 玩快捷列表里沒有的游戲

這種情況是LRU 緩存算法的主要邏輯。假設我不想玩這9個游戲，而是想玩個新的比如艾爾登法環并且我之前沒買過這個游戲，那當我買完下載時，會看到老頭環被放到了快捷列表的最前端，但是往右邊看會發現之前在最末端的仁王2不見了。

對于快捷列表來說，它的作用就是保存你最近玩的9個游戲，只要超出列表的容量，就會被丟進資料庫（打入冷宮）。這就是LRU緩存算法向我們傳達的一種斷舍離的核心價值觀。

文章最開始那張圖右邊的幾種案例我就不細說了，都包含在上面這兩個CASE內，只不過有一些檢索的get操作，一會在講代碼的時候再看吧。

生活中的LRU緩存算法

看完了剛才的例子，是不是覺得LRU緩存算法其實早就在自己的日常起居中根深蒂固了，只是你沒有察覺它就是這玩意兒而已。其他比如刷抖音、B站、小紅書的瀏覽記錄，還有每天從衣柜里取衣服、掛舊衣服的循環往復，或者其他任何生活場景中類似的決策，本質上都是用的LRU緩存這套核心思想，畢竟算法本來就是用來解決具體問題的嘛。

講完了一些感性的東西，再來看看技術領域LRU緩存算法的應用吧。

前后端技術中的LRU緩存算法

前端無人不知無人不曉的Vue.js，其源碼中就有不少地方用到了LRU緩存算法，其中最具代表性的keep-alive緩存組件，底層的緩存維護核心邏輯，就是一套LRU緩存算法。

上面的截圖是Vue官方文檔中關于keep-alive組件的描述和使用說明，其中就有用于設置最大緩存實例數的API max屬性。這里只做舉例，至于Vue源碼中keep-alive的具體實現，我下次應該會在Vue源碼的專欄里單獨說，或者你也可直接去查閱官方GitHub或者其他參考資料。反正待會兒我們也需要去手動實現一個相對通用一些的LRU緩存算法。

除了Vue的keep-alive內置組件，這里再列舉另外兩個前端技術領域能用到LRU緩存算法的好東西——lru-memoize?or?lru-momoizer

就是這倆貨，都是用來創建緩存函數的。如果你需要用JavaScript實現一個緩存函數，同時還希望能指定最大緩存容量以避免內存釋放不及導致的潛在性能問題，就可以通過引入lru-memoize或者lru- memoizer這倆npm包，輕松創建一個能配置最大緩存容量的緩存函數，比起underscore和lodash的緩存函數memoize方法，多了最大緩存容量這個概念，可以更好的根據具體業務場景管理自己的緩存列表大小。

看起來lru-memoizer功能似乎更強大，除了客戶端的接口請求數據緩存，也適合用于node服務端，因為它的參數是個options對象，可以配置資源加載、緩存key的hash生成、最大緩存數和過期時間等等。

最后再列舉一個應用于node服務端的LRU緩存例子——基于Koa框架模板的Lru緩存插件lru-cache

如果有這方面的需求可以試試用這個插件實現服務端的LRU緩存，當然也需要根據實際業務情況權衡利弊。?

原理和應用舉例就到這了，下面進入實戰環節，我們將通過兩種方式來實現一個基本的LRU緩存算法。

代碼篇

再看一遍這張圖，加深一下理解，同時也便于思考可以通過哪種數據結構去實現這個緩存列表。

結合這張圖，從LRU緩存的目的去理解，可以總結出這樣的結論——在LRU緩存算法的淘汰機制運行過程中，我們的程序主要是在做增刪改查中的刪增操作。再結合我上一篇提到的，雙鏈表的刪增操作時間復雜度為常數級的O(1)，就能理解為什么說雙鏈表這種數據結構很適合被用來做LRU緩存算法了。

那就先學以致用，用剛學過的雙鏈表來實現一下LRU緩存算法吧。

雙向鏈表 + hashMap實現

雙鏈表的實現我們現在也比較熟悉了，首先用最簡單的模型實現一個鏈表節點構造類。

class LinkedListNode {/*** Creates a doubly-linked list node.* @param {string} key* @param {any} val* @param {LinkedListNode} prev* @param {LinkedListNode} next*/constructor(key, val, prev = null, next = null) {this.key = key;this.val = val;this.prev = prev;this.next = next;} }

這個LinkedListNode的構造方法中有四個屬性，我們熟悉的key、value、prev、next。

接下來我們來實現一個緩存列表也就是雙鏈表結構的構造類LRUCache。

LRUCache的constructor在初始化時接收一個number類型的參數capacity，用于設置緩存最大容量（最多允許存儲的緩存對象個數）。除了capacity，constructor中還有4個屬性，他們分別是nodesMap（用于描述緩存對象映射關系的一個hashMap，這個很關鍵）、size（當前緩存列表的大小，也就是node總個數）、head（鏈表的頭節點，也就是最新的那個緩存對象）、tail（鏈表的尾節點，也就是最老的那個即將被刪除的緩存對象）。

剛才也提到了，LRU緩存算法淘汰機制運行過程中的主要操作是刪和增，但整個運行過程中還有另外兩個非常重要的操作查和改，需要根據key的匹配來命中緩存列表中的被調度的緩存對象，以及對特定緩存對象進行重新賦值。而這倆尤其是改，如果拿雙鏈表來實現的話顯然效率會很低下，所以我們就需要借助hashMap的天生優勢（key-value映射）來實現查和改的操作，哦對還有刪（都有hashMap了，就不需要用雙鏈表做刪了）。也就是說，雙鏈表負責增，hashMap負責查改刪，這樣一來，全部四種操作的時間復雜度都能控制在常數級O(1)內。

OK，開始寫代碼，因為這里涉及的引用關系比較多，就不分開寫了，直接上完整代碼。

class LRUCache {/*** Creates a cache instance of a specific capacity.* @param {number} capacity*/constructor(capacity) {this.capacity = capacity; // How many items to store in cache at max.this.nodesMap = {}; // The quick links to each linked list node in cache.this.size = 0; // The number of items that is currently stored in the cache.this.head = new LinkedListNode(); // The Head (first) linked list node.this.tail = new LinkedListNode(); // The Tail (last) linked list node.}/*** Returns the cached value by its key.* Time complexity: O(1) in average.* @param {string} key* @returns {any}*/get(key) {if (this.nodesMap[key] === undefined) return undefined;const node = this.nodesMap[key];this.promote(node);return node.val;}/*** Sets the value to cache by its key.* Time complexity: O(1) in average.* @param {string} key* @param {any} val*/set(key, val) {if (this.nodesMap[key]) {const node = this.nodesMap[key];node.val = val;this.promote(node);} else {const node = new LinkedListNode(key, val);this.append(node);}}/*** Promotes the node to the end of the linked list.* It means that the node is most frequently used.* It also reduces the chance for such node to get evicted from cache.* @param {LinkedListNode} node*/promote(node) {this.evict(node);this.append(node);}/*** Appends a new node to the end of the cache linked list.* @param {LinkedListNode} node*/append(node) {this.nodesMap[node.key] = node;if (!this.head.next) {// First node to append.this.head.next = node;this.tail.prev = node;node.prev = this.head;node.next = this.tail;} else {// Append to an existing tail.const oldTail = this.tail.prev;oldTail.next = node;node.prev = oldTail;node.next = this.tail;this.tail.prev = node;}this.size += 1;if (this.size > this.capacity) {this.evict(this.head.next);}}/*** Evicts (removes) the node from cache linked list.* @param {LinkedListNode} node*/evict(node) {delete this.nodesMap[node.key];this.size -= 1;const prevNode = node.prev;const nextNode = node.next;// If one and only node.if (prevNode === this.head && nextNode === this.tail) {this.head.next = null;this.tail.prev = null;this.size = 0;return;}// If this is a Head node.if (prevNode === this.head) {nextNode.prev = this.head;this.head.next = nextNode;return;}// If this is a Tail node.if (nextNode === this.tail) {prevNode.next = this.tail;this.tail.prev = prevNode;return;}// If the node is in the middle.prevNode.next = nextNode;nextNode.prev = prevNode;} }

可以看到，比起之前的雙鏈表，這個實現過程還是相對比較簡單的，沒有用到循環。只是多了一個置頂操作promote。這個promote主要做兩件事，用俗話說就是“舊的不去新的不來”——淘汰老節點、增加新節點。因為LRU的U是Used，也就是說只要用到了就會更新緩存列表，因此查操作get里就需要執行一遍promote。這一點很好理解，可以類比Vue響應式的實現。剛吃也說了，get是通過hashMap的查來做的，也就是根據key去到nodesMap里查出來對應的緩存對象。

在改操作set中，需要處理兩種情況，也就是之前PS5游戲快捷列表那個例子里的兩種情況——nodesMap里有值和沒值。有值就改舊對象的值，然后挪到最前端去，而緩存列表里的對象還是原來那些；沒值就增加新的，調用append方法。至于append方法執行的操作，其實和雙鏈表里講過的大致比較相似，分沒頭和有頭兩種處理方式，只是多了個size遞增的相關操作。如果size大于capacity，也就是剛才例子中的第2種情況，就需要執行一次緩存淘汰的操作。

而整個算法中最核心的緩存淘汰機制，就是evict里面的這堆東西。首先，刪直接用delete操作符完成，主打一個快準狠，刪完后size減1。刪到這基本也完成了一半了，后面就是根據四種情況，去處理最后的鏈表鏈接關系。

如果只有一個node，就頭尾都為指向null，size變成0。

如果被刪的這個node是個頭，那就執行雙鏈表的掐頭操作。

如果被刪的這個node是個尾，那就執行雙鏈表的去尾操作。

如果被刪的這個node在頭尾之間，那就把他前后的倆鄰居連起來。

以上就是用雙鏈表+hashMap實現這樣一個具備基本功能的LRU緩存算法的過程。

ES6 Map實現

既然hashMap都用上了，那為啥不直接用ES6現成的Map對象呢？OK，直接安排！

class LRUCacheOnMap {/*** Creates a cache instance of a specific capacity.* @param {number} capacity*/constructor(capacity) {this.capacity = capacity; // How many items to store in cache at max.this.items = new Map(); // The ordered hash map of all cached items.}/*** Returns the cached value by its key.* Time complexity: O(1) in average.* @param {string} key* @returns {any}*/get(key) {if (!this.items.has(key)) return undefined;const val = this.items.get(key);this.items.delete(key);this.items.set(key, val);return val;}/*** Sets the value to cache by its key.* Time complexity: O(1).* @param {string} key* @param {any} val*/set(key, val) {this.items.delete(key);this.items.set(key, val);if (this.items.size > this.capacity) {for (const headKey of this.items.keys()) {this.items.delete(headKey);break;}}} }

你看看，這多簡單，三下五除二就實現了，總共也就這么幾行。

Complexities

Average

Space	O(n)
Get item	O(1)
Set item	O(1)

好了，今天的LRU緩存算法解說就到這兒了，感謝你百忙之中抽我，哦不是，抽時間看我的文章。我要繼續去海拉魯大陸整花活兒了，拜拜了您內～（全篇完）

總結

以上是生活随笔為你收集整理的【文科生带你读JavaScript数据结构与算法】2. 双向链表与LRU缓存算法原理与实现（下）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。