大家好，我是小林。前幾天，我寫一篇感受計(jì)算機(jī)基礎(chǔ)之美的文章：堅(jiān)持一年了

里面介紹了個(gè)心跳服務(wù)的宕機(jī)判斷算法，當(dāng)時(shí)只是理論分析了下使用 LRU 算法來(lái)實(shí)現(xiàn)，沒(méi)有手撕代碼。

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

宕機(jī)判斷算法的設(shè)計(jì)

心跳服務(wù)主要做兩件事情：

• 發(fā)現(xiàn)宕機(jī)的主機(jī)；

• 發(fā)現(xiàn)上線的主機(jī)。

這個(gè)心跳服務(wù)最關(guān)鍵是判斷宕機(jī)的算法。

如果采用暴力遍歷所有主機(jī)的方式來(lái)找到超時(shí)的主機(jī)，在面對(duì)只有幾百臺(tái)主機(jī)的場(chǎng)景是沒(méi)問(wèn)題，但是這個(gè)算法會(huì)隨著主機(jī)越多，算法復(fù)雜度也會(huì)上升，程序的性能也就會(huì)急劇下降。

所以，我們應(yīng)該設(shè)計(jì)一個(gè)可以應(yīng)對(duì)超大集群規(guī)模的宕機(jī)判斷算法。

我們先來(lái)思考下，心跳包應(yīng)該有什么數(shù)據(jù)結(jié)構(gòu)來(lái)管理？

心跳包里的內(nèi)容是有主機(jī)上報(bào)的時(shí)間信息的，也就是有時(shí)間關(guān)系的，那么可以用「雙向鏈表」構(gòu)成先入先出的隊(duì)列，這樣就保存了心跳包的時(shí)序關(guān)系。

由于采用的數(shù)據(jù)結(jié)構(gòu)是雙向鏈表，所以隊(duì)尾插入和隊(duì)頭刪除操作的時(shí)間復(fù)雜度是 O(1)。

如果有新的心跳包，則將其插入到雙向鏈表的尾部，那么最老的心跳包就是在雙向鏈表的頭部，這樣在尋找宕機(jī)的主機(jī)時(shí)，只要看雙向鏈表頭部最老的心跳包，距現(xiàn)在是否超過(guò) 5 秒，如果超過(guò) 5秒 則認(rèn)為該主機(jī)宕機(jī)，然后將其從雙向鏈表中刪除。

細(xì)心的同學(xué)肯定發(fā)現(xiàn)了個(gè)問(wèn)題，就是如果一個(gè)主機(jī)的心跳包已經(jīng)在隊(duì)列中，那么下次該主機(jī)的心跳包要怎么處理呢？

為了維持隊(duì)列里的心跳包是主機(jī)最新上報(bào)的，所以要先找到該主機(jī)舊的心跳包，然后將其刪除，再把新的心跳包插入到雙向鏈表的隊(duì)尾。

問(wèn)題來(lái)了，在隊(duì)列找到該主機(jī)舊的心跳包，由于數(shù)據(jù)結(jié)構(gòu)是雙向鏈表，所以這個(gè)查詢過(guò)程的時(shí)間復(fù)雜度時(shí) O(N)，也就是說(shuō)隨著隊(duì)列里的元素越多，會(huì)越影響程序的性能，這一點(diǎn)我們必須優(yōu)化。

查詢效率最好的數(shù)據(jù)結(jié)構(gòu)就是「哈希表」了，時(shí)間復(fù)雜度只有 O(1)，因此我們可以加入這個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)優(yōu)化。

哈希表的 Key 是主機(jī)的 IP 地址，Value 包含主機(jī)在雙向鏈表里的節(jié)點(diǎn)，這樣我們就可以通過(guò)哈希表輕松找到該主機(jī)在雙向鏈表中的位置。

這樣，每當(dāng)收到心跳包時(shí)，先判斷其在不在哈希表里。

• 如果不存在哈希表里，說(shuō)明是新主機(jī)上線，先將其插入到雙向鏈表的頭部，然后將該主機(jī)的 IP 作為 Key，主機(jī)在雙向鏈表的節(jié)點(diǎn)作為 Value 插入到哈希表。

• 如果存在哈希表里，說(shuō)明主機(jī)已經(jīng)上線過(guò)，先通過(guò)查詢哈希表，找到該主機(jī)在雙向鏈表里舊的心跳包的節(jié)點(diǎn)，然后就可以通過(guò)該節(jié)點(diǎn)將其從雙向鏈表中刪除，最后將新的心跳包插入到雙向鏈表的隊(duì)尾，同時(shí)更新哈希表。

可以看到，上面這些操作全都是 O(1)，不管集群規(guī)模多大，時(shí)間復(fù)雜度都不會(huì)增加，但是代價(jià)就是內(nèi)存占用會(huì)越多，這個(gè)就是以空間換時(shí)間的方式。

有個(gè)細(xì)節(jié)的問(wèn)題，不知道大家發(fā)現(xiàn)了沒(méi)有，就是為什么隊(duì)列的數(shù)據(jù)結(jié)構(gòu)采用雙向鏈表，而不是單向鏈表？

因?yàn)殡p向鏈表比單向鏈表多了個(gè) pre 的指針，可以通過(guò)其找到上一個(gè)節(jié)點(diǎn)，那么在刪除中間節(jié)點(diǎn)的時(shí)候，就可以直接刪除，而如果是單向鏈表在刪除中間的時(shí)候，我們得先通過(guò)遍歷找到需被刪除節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)，才能完成刪除操作，這里中間多了個(gè)遍歷操作。

既然引入哈希表，那我們?cè)谂袛喑鲇兄鳈C(jī)宕機(jī)了（檢查雙向鏈表隊(duì)頭的主機(jī)是否超時(shí)），除了要將其從雙向鏈表中刪除，也要從哈希表中刪除。
要將主機(jī)從哈希表刪除，首先我們要知道主機(jī)的 IP，因?yàn)檫@是哈希表的 Key。

雙向鏈表存儲(chǔ)的內(nèi)容必須包含主機(jī)的 IP 信息，那為了更快查詢到主機(jī)的 IP，雙向鏈表存儲(chǔ)的內(nèi)容可以是一個(gè)鍵值對(duì)（Key-Value），其 Key 就是主機(jī)的 IP，Value 就是主機(jī)的信息。

這樣，在發(fā)現(xiàn)雙向鏈表中頭部的節(jié)點(diǎn)超時(shí)了，由于節(jié)點(diǎn)的內(nèi)容是鍵值對(duì)，于是就能快速地從該節(jié)點(diǎn)獲取主機(jī)的 IP ，知道了主機(jī)的 IP 信息，就能把哈希表中該主機(jī)信息刪除。

至此，就設(shè)計(jì)出了一個(gè)高性能的宕機(jī)判斷算法，主要用了數(shù)據(jù)結(jié)構(gòu)：哈希表 雙向鏈表，通過(guò)這個(gè)組合，查詢 刪除 插入操作的時(shí)間復(fù)雜度都是 O(1)，以空間換時(shí)間的思想，這就是數(shù)據(jù)結(jié)構(gòu)與算法之美！

熟悉算法的同學(xué)應(yīng)該感受出來(lái)了，上面這個(gè)算法就是類 LRU 算法，用于淘汰最近最久使用的元素的場(chǎng)景，該算法應(yīng)用范圍很廣的，操作系統(tǒng)、Redis、MySQL 都有使用該算法。

手撕 LRU 算法

在很多大廠面試的時(shí)候，經(jīng)常會(huì)考察 LRU 算法，甚至?xí)笫謱懗鰜?lái)，之前就有朋友在面試鵝廠的時(shí)候，當(dāng)初就要手寫 LRU 算法。

今天，就帶大家用 C 語(yǔ)言手撕 LRU 算法，我們就采用上面討論的「哈希表 雙向鏈表」這兩個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)該算法。

為了要實(shí)現(xiàn) LRU 算法， 鏈表的隊(duì)頭要保持是最近訪問(wèn)或者新加入的數(shù)據(jù)，鏈表的隊(duì)尾要保持是最久未被訪問(wèn)的，這樣我們?cè)谔蕴罹梦丛L問(wèn)的時(shí)候會(huì)很簡(jiǎn)單，然后哈希表用于快速查找節(jié)點(diǎn)。

雙向鏈表，存放的內(nèi)容是鍵值對(duì)。

typedef?std::pair<int?key,?std::string?value>?Pair;
typedef?std::list?List;
哈希表，存放的是鏈表節(jié)點(diǎn)。

typedef?std::map<int?key,?typename?List::iterator>?Map;
知道了數(shù)據(jù)結(jié)構(gòu)后，然后實(shí)現(xiàn)兩個(gè)函數(shù)，分別是 put 用于加入數(shù)據(jù)，get 用戶獲取數(shù)據(jù)，

我這里定義了個(gè) LRUCache 模板類，如下：

接下來(lái)，看看存放數(shù)據(jù)的 put 方法實(shí)現(xiàn)的方式，如下：

說(shuō)一下 put 方法的實(shí)現(xiàn)思路。

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

• 如果存在則表示有老數(shù)據(jù)，那么就需要將老數(shù)據(jù)先從鏈表和哈希表里刪除，然后再將新的數(shù)據(jù)重新加入到鏈表的隊(duì)頭，同時(shí)該鏈表節(jié)點(diǎn)存放到哈希表里，這樣鏈表里就維護(hù)了該 key 數(shù)據(jù)是最熱的。

• 如果哈希表不存在該 Key，則認(rèn)為是新的數(shù)據(jù)，直接將其加入到鏈表的隊(duì)頭，并把該鏈表節(jié)點(diǎn)更新到哈希表里。

接著，檢查鏈表的元素大小是否超過(guò)了 LRU 容量，如果超過(guò)了，就要將鏈表的隊(duì)尾元素移除，同時(shí)也將該節(jié)點(diǎn)從哈希表中刪除。

然后，我們?cè)賮?lái)看看 get 方法的實(shí)現(xiàn)方式，如下：

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

• 如果不存在，則返回 false；

• 如果存在，則鏈表要將數(shù)據(jù)刪除，然后再數(shù)據(jù)加入到鏈表隊(duì)頭，目的是為了維持鏈表隊(duì)頭是最近訪問(wèn)的數(shù)據(jù)。

主要的兩個(gè)函數(shù)已經(jīng)介紹完了，這里貼一下整個(gè)實(shí)現(xiàn)的代碼：

接下來(lái)跑一下測(cè)試用例。

創(chuàng)建了一個(gè)容量為 3 的 LRUCache 對(duì)象，然后使用 put 函數(shù)加入 3 組 key-value，這時(shí)鏈表的順序是 key:3（隊(duì)頭） -> ?key:2 -> key:1（隊(duì)尾）。

然后通過(guò) get 訪問(wèn) key:1 的元素，這時(shí)鏈表的順序變?yōu)?key:1（隊(duì)頭） -> ?key:3 -> key:2（隊(duì)尾）。

接著，put 加入 key:4 元素，由于鏈表的大小超過(guò)了定義的 LRUCache 的容量，于是就會(huì)移除隊(duì)尾的元素，也就是 key:2。

最后看到，就無(wú)法訪問(wèn) key:2 元素的了，運(yùn)行結(jié)果如下。

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

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