小林手撕 LRU 算法！

大家好，我是小林。

前幾天，我寫一篇感受計算機基礎之美的文章：堅持一年了

裏面介紹了個心跳服務的宕機判斷算法，當時只是理論分析了下使用 LRU 算法來實現，沒有手撕代碼。

今天，就帶大家手撕 LRU 算法，先讓大家回顧下案例，然後後面就進行代碼講解。

宕機判斷算法的設計

心跳服務主要做兩件事情：

這個心跳服務最關鍵是判斷宕機的算法。

如果採用暴力遍歷所有主機的方式來找到超時的主機，在面對只有幾百臺主機的場景是沒問題，但是這個算法會隨着主機越多，算法複雜度也會上升，程序的性能也就會急劇下降。

所以，我們應該設計一個可以應對超大集羣規模的宕機判斷算法。

我們先來思考下，心跳包應該有什麼數據結構來管理？

心跳包裏的內容是有主機上報的時間信息的，也就是有時間關係的，那麼可以用「雙向鏈表」構成先入先出的隊列，這樣就保存了心跳包的時序關係。

由於採用的數據結構是雙向鏈表，所以隊尾插入和隊頭刪除操作的時間複雜度是 O(1)。

如果有新的心跳包，則將其插入到雙向鏈表的尾部，那麼最老的心跳包就是在雙向鏈表的頭部，這樣在尋找宕機的主機時，只要看雙向鏈表頭部最老的心跳包，距現在是否超過 5 秒，如果超過 5 秒 則認爲該主機宕機，然後將其從雙向鏈表中刪除。

細心的同學肯定發現了個問題，就是如果一個主機的心跳包已經在隊列中，那麼下次該主機的心跳包要怎麼處理呢？

爲了維持隊列裏的心跳包是主機最新上報的，所以要先找到該主機舊的心跳包，然後將其刪除，再把新的心跳包插入到雙向鏈表的隊尾。

問題來了，在隊列找到該主機舊的心跳包，由於數據結構是雙向鏈表，所以這個查詢過程的時間複雜度時 O(N)，也就是說隨着隊列裏的元素越多，會越影響程序的性能，這一點我們必須優化。

查詢效率最好的數據結構就是「哈希表」了，時間複雜度只有 O(1)，因此我們可以加入這個數據結構來優化。

哈希表的 Key 是主機的 IP 地址，Value 包含主機在雙向鏈表裏的節點，這樣我們就可以通過哈希表輕鬆找到該主機在雙向鏈表中的位置。

這樣，每當收到心跳包時，先判斷其在不在哈希表裏。

可以看到，上面這些操作全都是 O(1)，不管集羣規模多大，時間複雜度都不會增加，但是代價就是內存佔用會越多，這個就是以空間換時間的方式。

有個細節的問題，不知道大家發現了沒有，就是爲什麼隊列的數據結構採用雙向鏈表，而不是單向鏈表？

因爲雙向鏈表比單向鏈表多了個 pre 的指針，可以通過其找到上一個節點，那麼在刪除中間節點的時候，就可以直接刪除，而如果是單向鏈表在刪除中間的時候，我們得先通過遍歷找到需被刪除節點的上一個節點，才能完成刪除操作，這裏中間多了個遍歷操作。

既然引入哈希表，那我們在判斷出有主機宕機了（檢查雙向鏈表隊頭的主機是否超時），除了要將其從雙向鏈表中刪除，也要從哈希表中刪除。
要將主機從哈希表刪除，首先我們要知道主機的 IP，因爲這是哈希表的 Key。

雙向鏈表存儲的內容必須包含主機的 IP 信息，那爲了更快查詢到主機的 IP，雙向鏈表存儲的內容可以是一個鍵值對（Key-Value），其 Key 就是主機的 IP，Value 就是主機的信息。

這樣，在發現雙向鏈表中頭部的節點超時了，由於節點的內容是鍵值對，於是就能快速地從該節點獲取主機的 IP ，知道了主機的 IP 信息，就能把哈希表中該主機信息刪除。

至此，就設計出了一個高性能的宕機判斷算法，主要用了數據結構：哈希表 + 雙向鏈表，通過這個組合，查詢 + 刪除 + 插入操作的時間複雜度都是 O(1)，以空間換時間的思想，這就是數據結構與算法之美！

熟悉算法的同學應該感受出來了，上面這個算法就是類 LRU 算法，用於淘汰最近最久使用的元素的場景，該算法應用範圍很廣的，操作系統、Redis、MySQL 都有使用該算法。

手撕 LRU 算法

在很多大廠面試的時候，經常會考察 LRU 算法，甚至會要求手寫出來，之前就有朋友在面試鵝廠的時候，當初就要手寫 LRU 算法。

今天，就帶大家用 C++ 語言手撕 LRU 算法，我們就採用上面討論的「哈希表 + 雙向鏈表」這兩個數據結構來實現該算法。

爲了要實現 LRU 算法， 鏈表的隊頭要保持是最近訪問或者新加入的數據，鏈表的隊尾要保持是最久未被訪問的，這樣我們在淘汰最久未訪問的時候會很簡單，然後哈希表用於快速查找節點。

雙向鏈表，存放的內容是鍵值對。

typedef std::pair<int key, std::string value> Pair;
typedef std::list<Pair> List;

哈希表，存放的是鏈表節點。

typedef std::map<int key, typename List::iterator> Map;

知道了數據結構後，然後實現兩個函數，分別是 put 用於加入數據，get 用戶獲取數據，

我這裏定義了個 LRUCache 模板類，如下：

接下來，看看存放數據的 put 方法實現的方式，如下：

說一下 put 方法的實現思路。

首先，通過哈希表查找是否存在該 Key：

接着，檢查鏈表的元素大小是否超過了 LRU 容量，如果超過了，就要將鏈表的隊尾元素移除，同時也將該節點從哈希表中刪除。

然後，我們再來看看 get 方法的實現方式，如下：

首先先在哈希表中查找是否存在該 key：

主要的兩個函數已經介紹完了，這裏貼一下整個實現的代碼：

接下來跑一下測試用例。

創建了一個容量爲 3 的 LRUCache 對象，然後使用 put 函數加入 3 組 key-value，這時鏈表的順序是 key:3（隊頭） ->  key:2 -> key:1（隊尾）。

然後通過 get 訪問 key:1 的元素，這時鏈表的順序變爲 key:1（隊頭） ->  key:3 -> key:2（隊尾）。

接着，put 加入 key:4 元素，由於鏈表的大小超過了定義的 LRUCache 的容量，於是就會移除隊尾的元素，也就是 key:2。

最後看到，就無法訪問 key:2 元素的了，運行結果如下。

好了，LRU 算法手撕就到了啦。

我是小林，今天你比昨天更博學了嗎？

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/zPZju2vl8eQ5yXaKcMbUqw

猜你喜歡