📌 實現思路

一、核心目標

我們要實現一個緩存類：

• 支持通過 get(key) 獲取緩存的值；
• 支持通過 put(key, value) 寫入緩存；
• 緩存容量有限，當超過容量時要淘汰最久未使用的元素。

二、為什么用「哈希表 + 雙向鏈表」

功能	使用的結構	原因
快速查找 key	哈希表 (dict)	O(1) 時間復雜度
快速移動元素到頭部	雙向鏈表	O(1) 移除 / 插入節點，無需整體移動元素
快速刪除最舊元素	鏈表尾部淘汰	尾節點指針指向最久未使用項，刪除也只需 O(1) 操作

---

🧾 完整代碼 + 注釋

// 聲明一個通用的 LRU 緩存類，Key 必須是 Hashable 的，Value 任意類型
class LRUCache<Key: Hashable, Value> {// 內部節點類：用于雙向鏈表的節點結構private class Node {let key: Keyvar value: Valuevar prev: Node?var next: Node?init(key: Key, value: Value) {self.key = keyself.value = value}}private let capacity: Int                        // 最大緩存容量private var dict: [Key: Node] = [:]              // 哈希表，用于快速訪問節點private var head: Node?                          // 鏈表頭（最近使用）private var tail: Node?                          // 鏈表尾（最久未使用）// 初始化函數init(capacity: Int) {self.capacity = capacity}// 讀取緩存func get(_ key: Key) -> Value? {guard let node = dict[key] else {return nil // 如果找不到，返回 nil}moveToHead(node) // 將訪問的節點移到頭部，表示“最近被使用”return node.value}// 寫入緩存func put(_ key: Key, value: Value) {if let node = dict[key] {// 已存在，更新值并移到頭部node.value = valuemoveToHead(node)} else {// 新節點，插入到頭部let newNode = Node(key: key, value: value)dict[key] = newNodeaddToHead(newNode)// 如果超過容量，移除尾部最久未使用的節點if dict.count > capacity {if let removed = removeTail() {dict.removeValue(forKey: removed.key)}}}}// 添加節點到鏈表頭部private func addToHead(_ node: Node) {node.next = headnode.prev = nilhead?.prev = nodehead = nodeif tail == nil {tail = head}}// 從鏈表中移除某個節點private func removeNode(_ node: Node) {if let prev = node.prev {prev.next = node.next} else {head = node.next // node 是頭部}if let next = node.next {next.prev = node.prev} else {tail = node.prev // node 是尾部}}// 將某個節點移到頭部（表示最近使用）private func moveToHead(_ node: Node) {removeNode(node)addToHead(node)}// 移除尾部節點（最久未使用的）private func removeTail() -> Node? {guard let oldTail = tail else { return nil }removeNode(oldTail)return oldTail}
}

---

📈 使用示例（調試輸出）

let cache = LRUCache<String, Int>(capacity: 2)
cache.put("a", value: 1)
cache.put("b", value: 2)
print(cache.get("a") ?? -1)  // 輸出 1 （"a" 成為最近使用）
cache.put("c", value: 3)     // 淘汰 "b"，因為 "b" 是最久未使用的
print(cache.get("b") ?? -1)  // 輸出 -1（已被淘汰）

---

🔍 運行原理圖解

每次執行操作時，雙向鏈表的結構如下所示（假設 head 在左，tail 在右）：

• 初始放入 a → head = a, tail = a
• 放入 b → a <-> b
• 訪問 a：a 移到頭部 → a <-> b
• 放入 c，超過容量，淘汰尾部 b → a <-> c

---

? 總結亮點

特性	實現方式
泛型支持	<Key: Hashable, Value> 泛型設計
O(1) 查找	使用 Dictionary
O(1) 插入刪除	使用雙向鏈表
高復用性	泛型設計支持任意 Key/Value 類型

---