核心思想與基本思路

LRU（Least Recently Used）算法是一種緩存淘汰策略，其核心思想是淘汰最近最少使用的數據。

• 最近使用原則：最近被訪問的數據在未來被訪問的概率更高，因此應保留在緩存中。
• 淘汰機制：當緩存容量滿時，淘汰最久未被訪問的數據。

那LRU是怎么判斷哪個數據是最近最少使用的呢？可能每個數據被訪問的時候，記錄一個時間戳或者順序，然后淘汰最久沒有被訪問的那個。比如，如果有幾個數據，每次訪問的時候都更新它們的最近使用時間，當需要淘汰的時候，找時間最早的那個。那具體怎么實現呢？

舉個例子吧，假設緩存容量是3，現在依次訪問數據A、B、C。那么緩存中的順序是A→B→C，鏈表頭是C，尾是A。這時候緩存滿了。如果再訪問D，就需要淘汰最久未使用的A，然后加入D，鏈表變成D→C→B？或者我可能弄反了順序？比如每次訪問的時候，把節點移動到鏈表頭部，所以最近訪問的在頭部，最久未使用的在尾部。假設現在緩存中有A、B、C，順序是C是最近訪問的，所以鏈表頭是C，然后是B，然后是A。當訪問B時，要把B移動到頭部，這時候順序變成B→C→A。這時候鏈表尾部是A。如果這時候要插入D，就淘汰A，然后D插入頭部，變成D→B→C。對嗎？

進一步地，我們可以將LRU算法想象成對一堆書進行操作。

對于需要訪問某本書時，則將書堆中的某本書取出并放在最上面，當書的數量超過某個值時（也就是超過緩存容量時），我們則將最下面一本書抽出，并將新的書放在書堆的最上面。這也就是最簡單的LRU算法基本原理。

有了上述思路，那么我們該如何實現LRU算法的get 和put 操作呢？
很簡單

實現方式

使用哈希表和雙向鏈表結合的數據結構

• 哈希表：提供O(1)時間的鍵值查詢，存儲鍵到鏈表節點的映射。

• 雙向鏈表：維護數據的訪問順序，最近訪問的節點靠近頭部，最久未訪問的節點靠近尾部。

操作步驟

• 訪問數據（get）：
  若鍵存在，通過哈希表定位節點，將其移動到鏈表頭部，表示最近使用，返回節點值。
  若鍵不存在，返回-1。

• 插入數據（put）：
  若鍵存在，更新值并將節點移動到鏈表頭部。
  若鍵不存在，創建新節點并插入鏈表頭部。若緩存已滿，刪除鏈表尾部節點（最久未使用），并在哈希表中移除對應鍵。

復雜度分析

• 時間復雜度：get和put操作均為O(1)。

• 空間復雜度：O(capacity)，用于存儲哈希表和鏈表。

為了便于雙向鏈表的維護與訪問，我們可以設置一個頭結點，當需要get和put書堆中的某本書時，直接用頭插法將結點移動到第一個結點即可。
實現代碼如下：

class Node {
public:int key; int value;Node *next;Node *prev;Node(int k = 0, int v = 0) : key(k), value(v) {}
};
class LRUCache {
private:int capacity;Node *cache; // 頭結點unordered_map <int, Node*> key_to_node;void RemoveNode(int key) {Node *node = key_to_node[key];node -> prev -> next = node -> next;node -> next -> prev = node -> prev;key_to_node.erase(key);delete node;}void PushFront(Node *node) { // 頭插法node -> next = cache -> next;node -> prev = cache;cache -> next -> prev = node;cache -> next = node;key_to_node[node -> key] = node;}
public:LRUCache(int capacity) {this -> capacity = capacity;cache = new Node;cache -> next = cache -> prev = cache;}int get(int key) {if(key_to_node.find(key) != key_to_node.end()) {int value = key_to_node[key] -> value;RemoveNode(key);Node *node = new Node(key, value);PushFront(node);return value;}return -1; }void put(int key, int value) {auto find_key = key_to_node.find(key);Node *node = new Node(key, value);if(find_key == key_to_node.end()) {if(key_to_node.size() < capacity) {PushFront(node);} else {RemoveNode(cache -> prev -> key);PushFront(node);}} else { // 如果key值已經存在，就變更value值再插入到第一個節點中。RemoveNode(key);PushFront(node);}}
};/*** Your LRUCache object will be instantiated and called as such:* LRUCache* obj = new LRUCache(capacity);* int param_1 = obj->get(key);* obj->put(key,value);*/