手寫LRU緩存算法這個話題網(wǎng)上已經(jīng)有很多版本了但大部分都停在用LinkedHashMap重寫一個removeEldestEntry的程度。我能理解面試或者日常開發(fā)里碰到緩存淘汰需求第一反應就是找個現(xiàn)成的輪子。但如果你真的打算手寫一版LRU并且想把它寫明白、寫對、寫到能在生產(chǎn)環(huán)境里扛住壓力那這篇文章應該能幫到你。我會從最基礎的場景說起講到HashMap加雙向鏈表的經(jīng)典實現(xiàn)再深入到幾個真正會讓人翻車的細節(jié)最后聊一些面試和工作里更進階的思考比如熱點數(shù)據(jù)污染、多級緩存和并發(fā)安全。全程都是我自己寫過的代碼、踩過的坑不繞彎子。1. LRU緩存到底在解決什么問題1.1 一個真實場景緩存失效帶來的連鎖反應先來說個實際場景。假設你在維護某個訂單查詢接口數(shù)據(jù)庫里存著幾千萬訂單數(shù)據(jù)用戶端會高頻查詢最近半小時的訂單狀態(tài)。最開始你直接查庫QPS一上去數(shù)據(jù)庫連接池就告警了慢查詢日志里全是同一條SQL。然后你引入了緩存把最近查過的訂單放進去。緩存一上接口P99從800ms降到了50ms效果立竿見影。但問題來了緩存空間是有限的不可能把所有訂單都放在內存里。當緩存滿了新數(shù)據(jù)要進來就得有人出去。誰出去這就是淘汰策略的職責。最樸素的思路是先進先出FIFO誰先進來誰先走。但你很快發(fā)現(xiàn)這有問題某個訂單雖然是很早之前查過一次但它其實仍然在被高頻查詢只是查詢頻率是間歇性的。如果它進來了卻被FIFO無情淘汰下一次訪問就會再次穿透到數(shù)據(jù)庫。LRULeast Recently Used最近最少使用的思路就是當一個數(shù)據(jù)被訪問過就把它標記為最近使用當緩存滿優(yōu)先淘汰那些最久沒被訪問的數(shù)據(jù)。它解決的核心問題是把有限的內存資源優(yōu)先留給那些近期活躍的數(shù)據(jù)。1.2 怎樣理解最近最少使用這個定義LRU的淘汰依據(jù)不是使用次數(shù)而是距離現(xiàn)在的時間間隔。你可以把它想象成一個原始的登記表每個數(shù)據(jù)進來時在表上蓋一個時間戳每次被訪問時間戳刷新成當前時間淘汰時掃描整張表找到時間戳最舊的那條刪掉。這個邏輯用直覺就能理解但如果真用每次訪問都更新時間戳、淘汰時全表掃描的方式實現(xiàn)性能會非常糟糕。訪問一次的時間復雜度是O(n)緩存越大越慢根本扛不住高并發(fā)。所以工程上幾乎不會用時間戳方案。真正普遍采用的數(shù)據(jù)結構組合是哈希表加雙向鏈表哈希表負責O(1)地定位數(shù)據(jù)是否存在、數(shù)據(jù)在鏈表哪個節(jié)點雙向鏈表負責維護訪問時間順序最近訪問的節(jié)點在鏈表頭部最久未訪問的在尾部。你的每一次訪問核心動作就兩個把被訪問的節(jié)點摘下來、再掛到鏈表頭部。淘汰時直接刪除鏈表尾部節(jié)點就行。全部操作都是O(1)。這個組合是整個LRU實現(xiàn)的靈魂也是手寫時最應該先想清楚的部分。2. 最容易跑偏的初版實現(xiàn)為什么能用不等于夠用2.1 用數(shù)組維護訪問時間的版本很多第一次手寫LRU的人都會先寫一個直觀版用一個Map存key和value用一個數(shù)組或者List存key的訪問順序。訪問某個key時先把key從數(shù)組里刪掉再把它放到數(shù)組末尾淘汰時取數(shù)組第一個元素刪掉。這樣寫起來確實很快二十分鐘就能跑通功能。如果面試官只問講講你LRU怎么實現(xiàn)的這個版本勉強也能說。但一旦被問到get和put的時間復雜度是多少就露餡了。從數(shù)組中間刪除一個元素需要把后續(xù)元素全部往前移動一位這是O(n)。當緩存容量是幾千甚至幾萬時刪除操作會變成性能瓶頸。我見過有人用ArrayList然后調remove(key)在容量1萬、每秒幾百次寫操作的情況下接口RT直接翻了好幾倍。另一個隱蔽問題是并發(fā)。ArrayList本身線程不安全如果同一個緩存實例被多個線程同時訪問刪除和插入操作會造成數(shù)據(jù)覆蓋、元素丟失甚至ArrayIndexOutOfBounds。網(wǎng)上很多demo級別代碼根本不考慮這個但你在真實項目里敢這么用線上遲早會給你顏色看。2.2 為什么能用和夠用差距那么大手寫LRU很容易寫出功能正確但性能不合格的版本問題就出在對操作復雜度的理解上。你需要對每個操作都問一句它是不是O(1)查詢一個key是否存在O(1)用HashMap。把一個節(jié)點從當前位置移到鏈表頭部O(1)前提是你直接持有這個節(jié)點的引用而不是遍歷鏈表去找它。淘汰最久未使用的節(jié)點O(1)刪除尾部節(jié)點本身很快關鍵是能O(1)地拿到這個節(jié)點對應的key從而同步刪除HashMap里的映射。第二條是重點。很多實現(xiàn)里把節(jié)點移到頭部靠的是先刪除再重新遍歷鏈表這就是O(n)的來源。正確做法是用HashMap記錄key到節(jié)點Node的映射節(jié)點持有prev和next兩個指針。拿到引用之后摘除和插入都是指針操作沒有任何遍歷。這個設計理念可以延伸到很多場景。比如你做熱更新配置、做任務調度器的超時管理凡是需要快速定位某個元素 按順序淘汰的組合幾乎都可以套用哈希表加鏈表的結構。LRU手寫一遍真正練的是這種思考方式而不僅僅是背一道面試題。3. HashMap加雙向鏈表的經(jīng)典組合核心實現(xiàn)拆解3.1 數(shù)據(jù)結構選型背后的邏輯在動手寫代碼前先把三個角色想清楚Cache接口對外暴露get和put兩個方法。Node節(jié)點鏈表的基本單元包含key、value、prev、next四個字段。LRUCache類內部持有一個HashMap和一個雙向鏈表HashMap的value類型直接設置為Node節(jié)點。為什么要用雙向鏈表而不是單向鏈表未經(jīng)深思熟慮的選擇——如果用一個HashMap維護key到節(jié)點的映射那么把某個節(jié)點移到頭部時按照單向鏈表你要把它的前驅節(jié)點的next指針指向當前節(jié)點的next。問題是單向鏈表不知道前驅是誰你得從頭遍歷才能找到前驅。雙向鏈表天生就能通過node.prev拿到前驅摘除節(jié)點這一步就變成了O(1)。這是雙向鏈表在手寫LRU中幾乎不可替代的原因。3.2 逐段拆解一個可直接運行的版本以下是Java實現(xiàn)。不用第三方依賴純JDK就能跑。import java.util.HashMap; import java.util.Map; public class LRUCacheK, V { private static class NodeK, V { K key; V value; NodeK, V prev; NodeK, V next; Node(K key, V value) { this.key key; this.value value; } } private final int capacity; private final MapK, NodeK, V map; private final NodeK, V head; private final NodeK, V tail; public LRUCache(int capacity) { if (capacity 1) { throw new IllegalArgumentException(capacity must be positive); } this.capacity capacity; this.map new HashMap(capacity); this.head new Node(null, null); this.tail new Node(null, null); head.next tail; tail.prev head; } public V get(K key) { NodeK, V node map.get(key); if (node null) { return null; } // 訪問過的節(jié)點移到鏈表頭部 moveToHead(node); return node.value; } public void put(K key, V value) { NodeK, V node map.get(key); if (node ! null) { node.value value; moveToHead(node); return; } NodeK, V newNode new Node(key, value); map.put(key, newNode); addToHead(newNode); if (map.size() capacity) { NodeK, V tailNode removeTail(); map.remove(tailNode.key); } } private void addToHead(NodeK, V node) { node.prev head; node.next head.next; head.next.prev node; head.next node; } private void removeNode(NodeK, V node) { node.prev.next node.next; node.next.prev node.prev; } private void moveToHead(NodeK, V node) { removeNode(node); addToHead(node); } private NodeK, V removeTail() { NodeK, V result tail.prev; removeNode(result); return result; } }這段代碼是我在實際項目里用過的精簡版。邏輯核心就是四段初始化虛擬節(jié)點、get時移動、put時插頭、容量超限時刪尾。3.3 為什么引入虛擬頭尾節(jié)點這里有個很實用的細節(jié)在雙向鏈表里聲明兩個哨兵節(jié)點head和tail。一個表示鏈表頭部一個表示鏈表尾部但實際上它們不存儲任何業(yè)務數(shù)據(jù)。哨兵節(jié)點的好處是不管鏈表是空的、只有一個節(jié)點、還是有很多節(jié)點頭部插入和尾部刪除的指針操作代碼都完全一樣。不需要再寫特判邏輯來處理如果鏈表為空怎么辦這類分支。如果沒有哨兵節(jié)點頭插和尾刪都得判斷head、tail是否為null代碼會多出一堆分支不說還特別容易在邊界狀態(tài)下出錯。我見過不少初版實現(xiàn)最后崩潰都發(fā)生在緩存里只有一個元素的時候。哨兵節(jié)點直接把這個坑填平了。4. 手寫過程中最容易翻車的幾個細節(jié)4.1 容量邊界的差一錯誤容量邊界是手寫LRU時最經(jīng)典的問題。核心判斷是map.size() capacity還是map.size() capacity還是一次寫入時要先插后刪還是先刪后插假設容量是3當前map里已經(jīng)有3個元素?，F(xiàn)在put一個新key。如果寫的是if (map.size() capacity) { removeTail(); }那就意味著只要達到容量上限就先刪一個再插入。表面看沒什么問題但如果你剛開始緩存還不滿比如現(xiàn)在只有2個元素put第3個時map.size() capacity成立會把最老的還沒被淘汰的節(jié)點刪掉再插新節(jié)點。結果容量永遠用不滿。正確做法是先插入后判斷是否超容量判斷條件用map.size() capacity只刪多出來的那一個。這也是上面代碼里的寫法。如果先把某個節(jié)點刪掉再插入也是一樣的結果只是要小心刪除之前別忘了把對應的map映射也刪掉。4.2 更新已有key時的順序問題當put一個已經(jīng)存在的key時有兩個動作要做更新value、把節(jié)點移到頭部。我見過有人寫先刪掉舊節(jié)點再new一個新節(jié)點重新插入。這樣做功能沒問題但白白多了一次節(jié)點對象分配和一次指針摘除操作在高頻更新場景下會產(chǎn)生不必要的GC壓力。更優(yōu)雅的方式直接復用原節(jié)點找到節(jié)點修改value然后移動節(jié)點位置。整個過程中節(jié)點在鏈表里的鄰居關系不變只是當前節(jié)點被摘除再插到頭部。對應的更新value之后不需要重新put到map因為map里存的引用本來就是同一個節(jié)點對象value是節(jié)點內部的字段。有人會問如果我把value改成新值但map里沒動會不會出現(xiàn)map里的node和鏈表里的node不是同一個在正確實現(xiàn)中不會。map的value就是鏈表節(jié)點的引用兩者始終指向同一個對象。如果你在任何一處重新new了Node而忘記更新map就會出現(xiàn)這種幽靈節(jié)點——鏈表里有個節(jié)點但map根本查不到它或者map指向的節(jié)點已經(jīng)不在鏈表里了。4.3 鏈表自環(huán)與引用丟失還有一個特別隱蔽的bug在removeNode和addToHead里如果指針更新的順序不對鏈表會自環(huán)。比如在addToHead里如果你先執(zhí)行head.next node再執(zhí)行head.next.prev node此時head.next已經(jīng)變成新節(jié)點了所以node.prev指向了node自己。沒錯節(jié)點自己指向自己鏈表直接死循環(huán)。正確順序是先處理新節(jié)點自己的prev和next再更新前驅和后繼的指針。也就是node.prev head; node.next head.next; head.next.prev node; head.next node;這個順序的要點是先把新節(jié)點的指針都安排好再去碰鏈條上的其他節(jié)點。一旦你動了head.next后面引用head.next.prev時拿到的是新節(jié)點自己而不是原來的第一個業(yè)務節(jié)點。這類bug在功能測試階段很難暴露因為鏈表自環(huán)后正常的插入、查詢、淘汰流程可能還能跑一陣子直到某個操作遍歷到死循環(huán)才會卡住。想快速定位的話調試時直接打印鏈表長度發(fā)現(xiàn)它和map.size()對不上基本就鎖定問題在指針操作上。5. 進階思考一只保留訪問順序還不夠如何防止緩存被熱點污染5.1 LRU的固有短板LRU雖然經(jīng)典但有明顯的短板它只關注最近是否被訪問不關注被訪問的頻率。極端情況下一個熱點key在短時間內被高頻訪問之后就不再訪問了而另一個key訪問頻率不高但一直穩(wěn)定地每隔一會訪問一次。在LRU的視角里熱點key因為最近被訪問過會一直留在緩存里而那個穩(wěn)定的低頻key反而可能被淘汰。這在業(yè)務上有個很直觀的場景某個秒殺活動開始后活動商品id被瞬間刷爆大量進入緩存活動結束這些商品再也不被訪問但它們霸占了緩存空間把其他正常業(yè)務的緩存全擠出去了。這就是緩存污染問題。緩存的命中率會明顯下降數(shù)據(jù)庫壓力反而上升。針對這個場景最簡單的策略之一是給緩存項設置過期時間而且這個過期時間不能用固定值而是要根據(jù)業(yè)務類型分成幾檔。比如熱點數(shù)據(jù)給30秒普通數(shù)據(jù)給5分鐘。再配合LRU本身容量淘汰可以緩解大部分污染問題。5.2 LFU和LRU的取舍LFULeast Frequently Used最近最不常使用用訪問次數(shù)代替訪問時間作為淘汰依據(jù)。對于上面秒殺場景LFU可能表現(xiàn)更好因為訪問頻率高的key會一直待著。但LFU也有自己的問題一個key曾經(jīng)被猛烈訪問過之后冷下來了但因為歷史計數(shù)很高它會一直賴在緩存里不走。LRU天然會把它洗掉LFU卻不一定。所以在實際系統(tǒng)里LRU和LFU都不是銀彈。很多框架會做折中比如Redis的近似LRU加上volatile-lfu策略允許用戶根據(jù)場景選擇。在你手寫算法時也要想清楚時間維度和頻率維度哪種更適合你的業(yè)務流量特征。5.3 LRU-K的近似實現(xiàn)思路如果面試被問到如何改進LRU一個很好的回答方向是LRU-K。簡單說LRU-K記錄每個key的最近K次訪問時間只有當訪問次數(shù)達到K次才把key放進真正的LRU緩存。這樣偶爾一兩次的冷訪問不會立刻把數(shù)據(jù)帶進緩存能有效過濾掉低質量的訪問流量。而一個真正會被高頻訪問的數(shù)據(jù)會盡快通過K次閾值進入緩存。實現(xiàn)LRU-K并不需要完整再寫一套。可以拆成兩個階段第一階段是歷史訪問記錄用一個容量小得多的LRU只記錄key和時間不存value第二階段才是真正的緩存放value。當?shù)谝浑A段某個key被訪問超過K次就把value寫入第二階段。這個方案對內存的額外開銷很小但能明顯提升緩存命中率適合讀多寫少、訪問模式相對穩(wěn)定的業(yè)務。6. 進階思考二工程落地時的并發(fā)、一致性與成本6.1 并發(fā)安全從加鎖到分段鎖上面那段代碼嚴格來說是單線程版本。真實項目里緩存必然被多個線程共享。最簡單的做法是給get和put加synchronized但這樣會引入全局鎖競爭。當一個線程正在執(zhí)行耗時較長的淘汰操作時其他所有線程的get都得排隊。更好的思路是使用ConcurrentHashMap來存儲映射再配合一個顯式鎖來保護鏈表的修改操作。因為get操作需要修改鏈表移動到頭部所以不能只靠ConcurrentHashMap自身保證線程安全還是需要鎖但鎖的粒度可以細一些。我見過一種工程上比較平衡的做法使用ReentrantReadWriteLock讀操作get獲取讀鎖寫操作put獲取寫鎖。在讀多寫少的緩存場景中讀鎖可以并發(fā)持有只有put才串行性能比全局synchronized好不少。代價是代碼復雜度上升鎖的獲取與釋放要格外小心避免死鎖。6.2 緩存與數(shù)據(jù)庫的一致性問題手寫LRU只是解決了緩存里放什么、滿了淘汰誰的問題但還有一個更難的問題淘汰之后如果緩存再被訪問怎么保證拿到的是最新的數(shù)據(jù)常見做法是旁路緩存Cache-Aside模式讀時先查緩存未命中再查數(shù)據(jù)庫并把結果寫入緩存寫時先更新數(shù)據(jù)庫再刪除緩存。刪除不是直接更新緩存是很多團隊踩過坑之后總結出來的經(jīng)驗——直接更新緩存會有并發(fā)寫導致的數(shù)據(jù)不一致刪除緩存則會強迫下一次讀去數(shù)據(jù)庫拉最新值。這里面還有一個坑刪除緩存失敗怎么辦很多系統(tǒng)引入消息隊列做異步重試在數(shù)據(jù)庫寫完binlog后由消費端去刪除對應緩存。如果binlog消費有延遲可能會短暫出現(xiàn)緩存里還是舊值的情況。這個問題沒有銀彈只能在實時性和一致性之間做取舍。6.3 多級緩存與淘汰策略的成本權衡最后聊一點工程視野。真正的生產(chǎn)環(huán)境通常不是單層緩存。CPU有L1/L2/L3本地有堆內緩存下面還有Redis這一類集中式緩存再下面才是數(shù)據(jù)庫。每一層都有不同的訪問速度和容量成本淘汰策略的選擇也不一樣。在堆內緩存這一層我們可以用LRU或者LRU-K控制內存占用容量一般很小幾十到幾百MB級在Redis這一層雖然容量更大但仍然有限需要配置maxmemory和淘汰策略。不同數(shù)據(jù)的重要性和訪問QPS差異很大因此還可以在業(yè)務代碼里給緩存項設置不同的等級等級高的用獨立緩存實例或獨立Redis避免被其他數(shù)據(jù)擠掉。有意思的是在Java生態(tài)里LinkedHashMap本身就實現(xiàn)了LRU的大部分能力它內部維護了雙向鏈表accessOrder設為true時每次get會觸發(fā)afterNodeAccess把節(jié)點移到鏈表尾部。你只需要重寫removeEldestEntry就能得到一個可用的LRU。但真正的面試題往往要求你手動實現(xiàn)原因就是考察你對指針操作、邊界條件、復雜度分析的掌握程度。把這些基本功練扎實了寫一遍LRU再去做緩存框架的二次開發(fā)或者去閱讀Redis、Caffeine這類優(yōu)秀開源項目的源碼會順暢很多。我在實際寫這一段代碼并拿去壓測時最大的體會是LRU看著簡單但要寫得有質量核心不在于鏈表操作本身而在于對每一個操作復雜度的敏感度以及對緩存策略選擇背后業(yè)務語義的理解。如果你也被要求寫一個LRU別急著背代碼先想想業(yè)務方到底需要什么訪問模式再來設計你的數(shù)據(jù)結構——這樣寫出來的才不是一個玩具。