LRU就是一種緩存淘汰策略。 計算機的緩存容量有限，如果緩存滿了就要刪除一些內容，給新內容騰位置。但問題是，刪除哪些內容呢？我們肯定希望刪掉哪些沒什么用的緩存，而把有用的數據繼續留在緩存里，方便之后繼續使用。那么，什么樣的數據，我們判定為「有用的」的數據呢？ LRU 緩存淘汰算法就是一種常用策略。LRU 的全稱是 Least Recently Used，也就是說我們認為最近使用過的數據應該是是「有用的」，很久都沒用過的數據應該是無用的，內存滿了就優先刪那些很久沒用過的數據。  LRU 算法設計 分析上面的操作過程，要讓 put 和 get 方法的時間復雜度為 O(1)，我們可以總結出 cache 這個數據結構必要的條件： 顯然 cache 中的元素必須有時序，以區分最近使用的和久未使用的數據，當容量滿了之后要刪除最久未使用的那個元素騰位置。 我們要在 cache 中快速找某個 key 是否已存在并得到對應的 val； 每次訪問 cache 中的某個 key，需要將這個元素變為最近使用的，也就是說 cache 要支持在任意位置快速插入和刪除元素。 那么，什么數據結構同時符合上述條件呢？哈希表查找快，但是數據無固定順序；鏈表有順序之分，插入刪除快，但是查找慢。所以結合一下，形成一種新的數據結構：哈希鏈表 LinkedHashMap。 LRU 緩存算法的核心數據結構就是哈希鏈表，雙向鏈表和哈希表的結合體。 如果我們每次默認從鏈表尾部添加元素，那么顯然越靠尾部的元素就是最近使用的，越靠頭部的元素就是最久未使用的。 對于某一個 key，我們可以通過哈希表快速定位到鏈表中的節點，從而取得對應 val。(結點設計是同時存入key和value) 鏈表顯然是支持在任意位置快速插入和刪除的，改改指針就行。只不過傳統的鏈表無法按照索引快速訪問某一個位置的元素，而這里借助哈希表，可以通過 key 快速映射到任意一個鏈表節點，然后進行插入和刪除。必須是雙向鏈表，有前向信息才能在任意位置刪除結點。 put 方法它的邏輯：  * **LRU緩存機制的核心：雙向鏈表（保證元素有序，且能快速的插入和刪除）+hash表（可以快速查詢）** * **為什么使用雙向鏈表**？因為：對于刪除操作，使用雙向鏈表，我們可以在O(1)的時間復雜度下，找到被刪除節點的前節點。 * **為什么要在鏈表中同時存鍵值，而不是只存值？** 因為：當緩存容量滿了之后，我們不僅要在雙向鏈表中刪除最后一個節點（即最久沒有使用的節點），還要把cache中映射到該節點的key刪除，這個key只能有Node得到（即hash表不能通過值得到鍵）。 leetcode LRU算法題：https://leetcode-cn.com/problems/OrIXps/ 題解：https://leetcode-cn.com/problems/OrIXps/solution/tong-guan-jian-2-mei-you-pai-ming-shou-d-buuu/