中資源 網站域名解析,奉賢廣州網站建設,wordpress 的主題,陜西省建設廳安全證考試官網目錄 ?編輯 前言 一、緩存與 LRU#xff1a;為什么 LRU 能成為主流#xff1f; 1.1 緩存的本質#xff1a;速度鴻溝的 “橋梁” 1.2 主流緩存替換算法對比#xff1a;LRU 的優(yōu)勢在哪#xff1f; 1.3 LRU 的核心定義#xff1a;“最久未使用” 才是關鍵 二、LRU 的…目錄?編輯前言一、緩存與 LRU為什么 LRU 能成為主流1.1 緩存的本質速度鴻溝的 “橋梁”1.2 主流緩存替換算法對比LRU 的優(yōu)勢在哪1.3 LRU 的核心定義“最久未使用” 才是關鍵二、LRU 的實現(xiàn)思路如何做到 O (1) 效率2.1 核心數(shù)據結構雙向鏈表 哈希表2.2 數(shù)據結構設計細節(jié)2.3 LRU 核心操作流程拆解2.3.1 get 操作獲取數(shù)據并更新優(yōu)先級2.3.2 put 操作插入或更新數(shù)據2.4 為什么必須用雙向鏈表三、C 完整實現(xiàn)手把手寫 LRU Cache3.1 完整代碼實現(xiàn)3.2 代碼關鍵細節(jié)解析3.2.1 迭代器的作用3.2.2 鏈表節(jié)點的移動邏輯3.2.3 緩存淘汰邏輯3.3 測試結果驗證四、深入理解LRU 的時間復雜度與空間復雜度4.1 時間復雜度分析4.2 空間復雜度分析4.3 與其他實現(xiàn)方式的對比五、LRU 的實際應用場景5.1 操作系統(tǒng)中的 LRU5.2 數(shù)據庫中的 LRU5.3 框架與應用中的 LRU5.4 面試中的 LRU六、常見問題與優(yōu)化方向6.1 線程安全問題6.2 內存占用優(yōu)化6.3 近似 LRU 的實現(xiàn)總結前言在程序員的技術成長路上緩存是繞不開的核心話題 —— 小到瀏覽器的本地存儲大到分布式系統(tǒng)的 Redis 集群緩存的存在總能讓數(shù)據訪問速度實現(xiàn)質的飛躍。而在眾多緩存替換算法中LRULeast Recently Used絕對是 “明星選手”它原理直觀、實現(xiàn)高效被廣泛應用于操作系統(tǒng)、數(shù)據庫、框架源碼等各類場景。如果你曾被 “如何設計一個 O (1) 時間復雜度的 LRU 緩存” 面試題難住或是想深入理解 LRU 的底層邏輯這篇文章將帶你從 0 到 1 吃透 LRU Cache。下面就讓我們正式開始吧一、緩存與 LRU為什么 LRU 能成為主流在正式講解 LRU 之前我們得先搞懂兩個核心問題什么是緩存為什么 LRU 算法能脫穎而出1.1 緩存的本質速度鴻溝的 “橋梁”緩存Cache本質上是一種高速數(shù)據存儲層位于速度相差較大的兩種硬件或系統(tǒng)之間用于協(xié)調數(shù)據傳輸?shù)乃俣炔町?。就像生活中常用的物品會放在桌面高速緩存不常用的會放進柜子低速存儲緩存的核心思想是 “把最常用的數(shù)據放在最快的地方”。從狹義到廣義緩存無處不在CPU 緩存位于 CPU 和主存之間用高速 SRAM 芯片實現(xiàn)速度是主存的數(shù)十倍解決 CPU 運算速度與主存讀取速度不匹配的問題內存緩存位于內存和硬盤之間比如操作系統(tǒng)的頁面緩存讓頻繁訪問的硬盤數(shù)據常駐內存避免重復的磁盤 IO應用層緩存比如瀏覽器的 Internet 臨時文件夾、Redis 數(shù)據庫甚至是我們自己寫的本地緩存都是為了減少對后端服務或底層存儲的訪問壓力。但緩存的容量始終是有限的 ——CPU 一級緩存可能只有幾十 KBRedis 實例的內存也有上限。當新數(shù)據需要存入而緩存已經滿了的時候就必須 “踢掉” 一部分舊數(shù)據這就是緩存替換策略要解決的問題。1.2 主流緩存替換算法對比LRU 的優(yōu)勢在哪常見的緩存替換算法有四種我們用一個簡單的例子對比它們的邏輯假設緩存容量為 3數(shù)據訪問順序是 1→2→3→4→2→5看看每種算法會保留哪些數(shù)據算法核心邏輯最終緩存數(shù)據優(yōu)缺點FIFO先進先出按數(shù)據存入順序淘汰最早的3、4、5實現(xiàn)簡單但忽略數(shù)據訪問頻率可能淘汰常用數(shù)據LFU最近最不常使用淘汰訪問次數(shù)最少的數(shù)據2、4 、5考慮訪問頻率但需要統(tǒng)計次數(shù)實現(xiàn)復雜且不適合突發(fā)訪問場景OPT最優(yōu)替換淘汰未來最久不會使用的數(shù)據2、4、5理論最優(yōu)但需要預知未來訪問實際無法實現(xiàn)LRU最近最少使用淘汰最長時間未被使用的數(shù)據2、4、5兼顧直觀性和高效性無需統(tǒng)計次數(shù)僅關注最近訪問時間可以看到LRU 是性價比最高的選擇它的邏輯符合人類使用習慣最近使用的 data 未來大概率還會被使用且實現(xiàn)難度低、時間復雜度可控完美平衡了 “效果” 和 “成本”這也是它成為工業(yè)界首選的核心原因。1.3 LRU 的核心定義“最久未使用” 才是關鍵很多人會把 LRU 翻譯成 “最近最少使用”但更形象的理解是 “最久未使用”—— 算法的核心規(guī)則是當緩存未滿時新數(shù)據直接存入當緩存已滿時淘汰 “距離上次使用時間最久” 的數(shù)據當訪問get或更新put緩存中的數(shù)據時該數(shù)據會被標記為 “最近使用”優(yōu)先級提升。舉個生活中的例子你的手機桌面只能放 3 個 APP你先裝了微信、抖音、淘寶緩存[微信抖音淘寶]之后你打開了微信訪問操作微信變成最近使用緩存調整為 [抖音淘寶微信]接著你裝了小紅書緩存滿了此時最久未使用的是抖音所以抖音被淘汰緩存變?yōu)?[淘寶微信小紅書]—— 這就是 LRU 的核心邏輯。二、LRU 的實現(xiàn)思路如何做到 O (1) 效率要實現(xiàn) LRU關鍵是解決兩個核心問題如何快速找到 “最久未使用” 的數(shù)據以便淘汰如何快速插入新數(shù)據、更新已有數(shù)據的優(yōu)先級如果用常規(guī)數(shù)據結構實現(xiàn)會遇到明顯的效率瓶頸數(shù)組插入 / 刪除需要移動元素時間復雜度 O (n)單鏈表查找數(shù)據需要遍歷時間復雜度 O (n)哈希表查找 / 插入 O (1)但無法記錄數(shù)據的訪問順序無法快速找到 “最久未使用” 的數(shù)據。2.1 核心數(shù)據結構雙向鏈表 哈希表要實現(xiàn) O (1) 時間復雜度的 get 和 put 操作必須結合兩種數(shù)據結構的優(yōu)勢形成 “互補”雙向鏈表std::list負責維護數(shù)據的訪問順序最近使用的數(shù)據放在鏈表頭部最久未使用的放在鏈表尾部。雙向鏈表的優(yōu)勢是支持 O (1) 時間的任意位置插入和刪除只需修改前后節(jié)點的指針哈希表std::unordered_map負責快速查找數(shù)據key 是緩存的鍵值value 是雙向鏈表中對應節(jié)點的迭代器iterator。哈希表的優(yōu)勢是查找、插入、刪除的時間復雜度均為 O (1)。這個組合的 “精妙之處” 在于哈希表的 value 存儲鏈表迭代器使得我們可以通過 key 快速定位到鏈表中的節(jié)點再通過雙向鏈表的 O (1) 插入 / 刪除操作調整節(jié)點順序最終實現(xiàn)所有操作的 O (1) 效率。2.2 數(shù)據結構設計細節(jié)我們先明確 C 中具體的數(shù)據結構選型雙向鏈表使用std::liststd::pairint, int每個節(jié)點存儲(key, value)鍵值對 —— 因為淘汰鏈表尾部節(jié)點時需要通過 key 刪除哈希表中對應的記錄哈希表使用std::unordered_mapint, std::liststd::pairint, int::iteratorkey 是緩存的 keyvalue 是鏈表節(jié)點的迭代器 —— 通過迭代器可以直接操作鏈表節(jié)點無需遍歷鏈表緩存容量使用size_t _capacity記錄緩存的最大容量當鏈表大小超過容量時觸發(fā)淘汰邏輯。2.3 LRU 核心操作流程拆解LRU 的核心操作有兩個get獲取數(shù)據和put插入 / 更新數(shù)據我們逐一拆解它們的執(zhí)行流程。2.3.1 get 操作獲取數(shù)據并更新優(yōu)先級get 操作的目標是根據 key 查找緩存如果存在則返回 value并將該節(jié)點移動到鏈表頭部標記為最近使用如果不存在則返回 - 1。具體步驟用哈希表查找 key 對應的迭代器auto hash_it _hash_map.find(key)如果哈希表中沒有該 keyhash_it _hash_map.end()返回 - 1如果存在通過迭代器獲取鏈表節(jié)點的鍵值對std::pairint, int kv *hash_it-second從鏈表中刪除該節(jié)點_list.erase(hash_it-second)—— 雙向鏈表刪除已知迭代器的節(jié)點是 O (1)將該節(jié)點插入到鏈表頭部_list.push_front(kv)—— 標記為最近使用更新哈希表中該 key 對應的迭代器_hash_map[key] _list.begin()—— 因為節(jié)點位置變了迭代器需要重新指向頭部返回kv.second即 value。2.3.2 put 操作插入或更新數(shù)據put 操作的目標是如果 key 已存在則更新 value 并將節(jié)點移到頭部如果 key 不存在則插入新節(jié)點到頭部若緩存已滿則淘汰鏈表尾部節(jié)點。具體步驟用哈希表查找 key 對應的迭代器auto hash_it _hash_map.find(key)如果 key 已存在hash_it ! _hash_map.end()① 通過迭代器獲取鏈表節(jié)點std::pairint, int kv *hash_it-second② 更新節(jié)點的 valuekv.second value③ 從鏈表中刪除該節(jié)點_list.erase(hash_it-second)④ 將更新后的節(jié)點插入到鏈表頭部_list.push_front(kv)⑤ 更新哈希表中的迭代器_hash_map[key] _list.begin()如果 key 不存在hash_it _hash_map.end()① 檢查緩存是否已滿_list.size() _capacitya. 如果已滿獲取鏈表尾部節(jié)點的 keyint delete_key _list.back().firstb. 刪除鏈表尾部節(jié)點_list.pop_back()—— 淘汰最久未使用的數(shù)據c. 刪除哈希表中該 key 對應的記錄_hash_map.erase(delete_key)② 創(chuàng)建新的鍵值對節(jié)點插入到鏈表頭部_list.push_front(std::make_pair(key, value))③ 在哈希表中添加該 key 與鏈表頭部迭代器的映射_hash_map[key] _list.begin()。2.4 為什么必須用雙向鏈表可能有同學會問為什么不用單鏈表這里的關鍵是 “刪除節(jié)點時需要前驅節(jié)點的指針”。在單鏈表中要刪除一個節(jié)點必須先找到它的前驅節(jié)點這需要遍歷鏈表O (n) 時間而雙向鏈表的每個節(jié)點都有 prev 和 next 指針通過迭代器可以直接獲取前后節(jié)點的信息刪除操作只需修改兩個指針無需遍歷實現(xiàn) O (1) 時間復雜度。這也是雙向鏈表在 LRU 實現(xiàn)中不可替代的原因 —— 它讓節(jié)點的刪除操作擺脫了對 “遍歷查找前驅” 的依賴完美配合哈希表實現(xiàn)高效操作。三、C 完整實現(xiàn)手把手寫 LRU Cache基于上面的思路我們來編寫完整的 C 實現(xiàn)代碼。代碼將基于 LeetCode 第 146 題《LRU 緩存》的接口規(guī)范編寫大家可以直接提交進行驗證。3.1 完整代碼實現(xiàn)#include iostream #include list #include unordered_map #include utility // for std::make_pair using namespace std; class LRUCache { public: // 構造函數(shù)初始化緩存容量 LRUCache(int capacity) { _capacity capacity; } // 獲取key對應的value不存在返回-1 int get(int key) { // 1. 在哈希表中查找key auto hash_it _hash_map.find(key); // 2. 未找到返回-1 if (hash_it _hash_map.end()) { return -1; } // 3. 找到獲取鏈表節(jié)點的迭代器 auto list_it hash_it-second; // 4. 取出節(jié)點的鍵值對 pairint, int kv *list_it; // 5. 從鏈表中刪除該節(jié)點 _list.erase(list_it); // 6. 將節(jié)點插入到鏈表頭部標記為最近使用 _list.push_front(kv); // 7. 更新哈希表中的迭代器指向新的頭部位置 _hash_map[key] _list.begin(); // 8. 返回value return kv.second; } // 插入或更新key對應的value void put(int key, int value) { // 1. 在哈希表中查找key auto hash_it _hash_map.find(key); // 2. key已存在更新value并移動到頭部 if (hash_it ! _hash_map.end()) { // 獲取鏈表節(jié)點迭代器 auto list_it hash_it-second; // 取出節(jié)點并更新value pairint, int kv *list_it; kv.second value; // 從鏈表中刪除該節(jié)點 _list.erase(list_it); // 插入到頭部 _list.push_front(kv); // 更新哈希表迭代器 _hash_map[key] _list.begin(); } else { // 3. key不存在插入新節(jié)點 // 檢查緩存是否已滿 if (_list.size() _capacity) { // 緩存已滿淘汰鏈表尾部節(jié)點最久未使用 int delete_key _list.back().first; // 獲取尾部節(jié)點的key _list.pop_back(); // 刪除鏈表尾部節(jié)點 _hash_map.erase(delete_key); // 刪除哈希表中的對應記錄 } // 插入新節(jié)點到鏈表頭部 _list.push_front(make_pair(key, value)); // 在哈希表中添加映射 _hash_map[key] _list.begin(); } } private: // 雙向鏈表存儲(key, value)頭部是最近使用尾部是最久未使用 listpairint, int _list; // 緩存容量 size_t _capacity; // 哈希表key - 鏈表節(jié)點的迭代器實現(xiàn)O(1)查找 unordered_mapint, listpairint, int::iterator _hash_map; }; // 測試代碼 int main() { // 創(chuàng)建容量為2的LRU緩存 LRUCache cache(2); // 執(zhí)行測試用例參考LeetCode示例 cache.put(1, 1); cout put(1,1) - 緩存: [(1,1)] endl; cache.put(2, 2); cout put(2,2) - 緩存: [(2,2), (1,1)] endl; int res1 cache.get(1); cout get(1) - res1 緩存: [(1,1), (2,2)] endl; // 輸出1 cache.put(3, 3); cout put(3,3) - 淘汰2緩存: [(3,3), (1,1)] endl; int res2 cache.get(2); cout get(2) - res2 endl; // 輸出-1 cache.put(4, 4); cout put(4,4) - 淘汰1緩存: [(4,4), (3,3)] endl; int res3 cache.get(1); cout get(1) - res3 endl; // 輸出-1 int res4 cache.get(3); cout get(3) - res4 緩存: [(3,3), (4,4)] endl; // 輸出3 int res5 cache.get(4); cout get(4) - res5 緩存: [(4,4), (3,3)] endl; // 輸出4 return 0; }3.2 代碼關鍵細節(jié)解析3.2.1 迭代器的作用哈希表的 value 存儲鏈表迭代器是整個實現(xiàn)的 “靈魂”—— 迭代器相當于鏈表節(jié)點的 “指針”通過它可以直接定位到節(jié)點無需遍歷鏈表。當節(jié)點在鏈表中移動位置后只需更新哈希表中的迭代器就能保證下一次查找依然是 O (1) 時間。需要注意的是std::list的迭代器在節(jié)點插入 / 刪除后不會失效只要節(jié)點本身沒被刪除這也是選擇std::list而不是std::vector的重要原因 ——std::vector的迭代器在插入時可能因擴容失效無法滿足我們的需求。3.2.2 鏈表節(jié)點的移動邏輯無論是 get 還是 put 操作只要數(shù)據被訪問或更新就需要移動到鏈表頭部這是 LRU “最近使用” 規(guī)則的體現(xiàn)。移動過程分為 “刪除原節(jié)點” 和 “插入頭部” 兩步都是 O (1) 時間不會影響整體效率。3.2.3 緩存淘汰邏輯當緩存已滿時直接刪除鏈表尾部節(jié)點 —— 因為鏈表尾部是最久未使用的數(shù)據這完全符合 LRU 的淘汰規(guī)則。刪除時必須同時刪除哈希表中的對應記錄否則會出現(xiàn) “哈希表中有 key但鏈表中無節(jié)點” 的不一致情況。3.3 測試結果驗證運行上面的測試代碼輸出如下put(1,1) - 緩存: [(1,1)] put(2,2) - 緩存: [(2,2), (1,1)] get(1) - 1緩存: [(1,1), (2,2)] put(3,3) - 淘汰2緩存: [(3,3), (1,1)] get(2) - -1 put(4,4) - 淘汰1緩存: [(4,4), (3,3)] get(1) - -1 get(3) - 3緩存: [(3,3), (4,4)] get(4) - 4緩存: [(4,4), (3,3)]結果與 LeetCode 示例是完全一致證明我們的實現(xiàn)是正確的。四、深入理解LRU 的時間復雜度與空間復雜度4.1 時間復雜度分析我們的實現(xiàn)中get 和 put 操作的每一步都是 O (1) 時間復雜度哈希表查找、插入、刪除O (1)std::unordered_map的平均時間復雜度雙向鏈表插入、刪除O (1)通過迭代器直接操作無需遍歷節(jié)點移動本質是 “刪除 插入”兩步都是 O (1)。因此get 和 put 操作的時間復雜度均為 O (1)這是 LRU 最理想的效率表現(xiàn)。4.2 空間復雜度分析空間復雜度由緩存容量決定雙向鏈表存儲的節(jié)點數(shù)最多為_capacity空間復雜度 O (capacity)哈希表存儲的鍵值對數(shù)量與鏈表節(jié)點數(shù)一致空間復雜度 O (capacity)整體空間復雜度為 O (capacity)沒有額外的空間開銷。4.3 與其他實現(xiàn)方式的對比除了 “雙向鏈表 哈希表”還有幾種常見的 LRU 實現(xiàn)方式但效率都不如我們的方案僅用雙向鏈表查找需要遍歷時間復雜度 O (n)適合小容量緩存數(shù)組 時間戳用數(shù)組存儲數(shù)據每個元素記錄最后訪問時間淘汰時遍歷找時間戳最小的元素時間復雜度 O (n)平衡二叉搜索樹 哈希表比如用std::map紅黑樹維護訪問順序哈希表查找時間復雜度 O (log n)實現(xiàn)復雜不如雙向鏈表高效?！半p向鏈表 哈希表” 的組合是時間和實現(xiàn)復雜度的最優(yōu)解也是工業(yè)界的標準實現(xiàn)方式。五、LRU 的實際應用場景LRU 的應用場景遠比我們想象的廣泛從底層系統(tǒng)到上層應用都能看到它的身影5.1 操作系統(tǒng)中的 LRU頁面置換算法操作系統(tǒng)為了減少磁盤 IO會將部分內存頁面緩存起來當內存不足時使用 LRU 算法淘汰最久未使用的頁面CPU 緩存替換CPU 的一級、二級緩存容量有限當新指令或數(shù)據需要緩存時用 LRU 淘汰最久未使用的緩存行。5.2 數(shù)據庫中的 LRUMySQL 緩沖池Buffer PoolMySQL 會將磁盤上的表數(shù)據和索引緩存到內存的 Buffer Pool 中采用 LRU 算法管理緩存頁提高查詢效率Redis 緩存Redis 的過期策略中除了定期刪除還會結合 LRU 算法淘汰過期鍵volatile-lru 策略。5.3 框架與應用中的 LRU瀏覽器緩存瀏覽器的本地存儲LocalStorage和會話存儲SessionStorage會使用 LRU 算法管理緩存數(shù)據當存儲容量滿時淘汰最久未使用的條目框架緩存Spring Boot 的Cacheable注解、MyBatis 的一級緩存默認都支持 LRU 緩存策略自定義本地緩存在高并發(fā)場景中開發(fā)者會基于 LRU 實現(xiàn)本地緩存減少對分布式緩存的訪問壓力。5.4 面試中的 LRULRU 是面試中的 “高頻考點”常見問題包括設計一個 O (1) 時間復雜度的 LRU 緩存手寫代碼LRU 和 LFU 的區(qū)別與實現(xiàn)Redis 中的 LRU 優(yōu)化Redis 采用的是近似 LRU通過隨機采樣實現(xiàn)而非精確 LRU。掌握本文的實現(xiàn)思路就能輕松應對這類面試題。六、常見問題與優(yōu)化方向6.1 線程安全問題我們的實現(xiàn)是非線程安全的在單線程環(huán)境如 LeetCode 測試中完全沒問題但在多線程環(huán)境如高并發(fā)服務中會出現(xiàn)數(shù)據競爭。解決方案加鎖使用std::mutex對 get 和 put 操作加鎖保證同一時間只有一個線程操作緩存無鎖實現(xiàn)使用原子操作std::atomic和CASCompare And Swap機制實現(xiàn)無鎖 LRU適合高并發(fā)場景。示例加鎖版 get 操作int get(int key) { std::lock_guardstd::mutex lock(_mutex); // 自動加鎖和解鎖 auto hash_it _hash_map.find(key); if (hash_it _hash_map.end()) { return -1; } auto list_it hash_it-second; pairint, int kv *list_it; _list.erase(list_it); _list.push_front(kv); _hash_map[key] _list.begin(); return kv.second; }6.2 內存占用優(yōu)化如果緩存中存儲的是大數(shù)據如大對象、長字符串單純的 LRU 可能會導致內存占用過高。優(yōu)化方向限制緩存容量的同時限制單個節(jié)點的大小結合 TTLTime To Live過期時間自動淘汰過期數(shù)據定期清理后臺線程定期掃描緩存刪除長期未使用的數(shù)據。6.3 近似 LRU 的實現(xiàn)精確 LRU 的實現(xiàn)需要雙向鏈表和哈希表在某些場景下如超大容量緩存可以使用近似 LRU 減少實現(xiàn)復雜度Redis 的近似 LRU隨機采樣 N 個鍵淘汰其中最久未使用的N 默認是 5可以通過maxmemory-samples配置調整基于計數(shù)器的 LRU每個節(jié)點維護一個計數(shù)器訪問時遞增淘汰時選擇計數(shù)器最小的節(jié)點實現(xiàn)簡單但精度略低?？偨Y緩存的本質是 “用空間換時間”而 LRU 則是讓這份 “空間” 發(fā)揮最大價值的最佳策略之一。希望這篇文章能幫助你真正吃透 LRU在技術成長路上再添一個 “硬核技能”如果覺得本文對你有幫助歡迎點贊、收藏、轉發(fā)也可以在評論區(qū)交流你的疑問或見解