題幹與適用情境
實作 LRUCache(capacity)，其中 capacity 是正整數，鍵和值都是非負整數。get(key) 回傳對應值，鍵不存在時回傳 -1；put(key, value) 新增或更新鍵。成功的 get 和每次 put 都要把該鍵標記為最近使用。快取已滿時新增鍵，只淘汰一個最久未使用的鍵。兩個公開操作都要達到預期 O(1)。
本題是在單一行程、單執行緒內完成的資料結構程式題；分散式快取設計、TTL、持久化、依大小計費和並行存取都不在範圍內。「預期 O(1)」依賴雜湊表操作的一般平均效能假設；鏈結串列的指標修改本身是最壞情況 O(1)。
完整答案要從限制推導兩種結構為何缺一不可，明確說出對映與串列的不變量，處理既有鍵更新時不能誤淘汰，並在每次操作後驗證使用順序。
面試官考察重點
第一項訊號是能否把需求翻成操作。依鍵查找不能掃描，所以需要雜湊表；最近使用順序又要求把任意命中的節點移到最近端，並從另一端刪除最舊節點。只要雜湊表已經提供節點，雙向鏈結串列就能用固定次數的指標修改完成這兩件事。
第二項訊號是能否把兩個結構視為同一份狀態。雜湊表不能只保存值，而要把每個鍵對映到串列節點。每個真實節點必須恰好有一筆對映，每筆對映也必須指向串列中的一個真實節點。淘汰時要從兩個結構刪除同一個鍵。
第三項訊號是指標操作是否穩定。虛擬頭尾節點讓所有真實節點都位於串列中間，刪除和插入不必為第一個、最後一個或唯一節點分別處理。寫程式前要先約定哪一側代表最近使用，之後保持一致。
最後看測試能否驗證完整順序。只檢查回傳值會遺漏串列狀態錯誤；容量為 1、滿容量時更新既有鍵、反覆讀取同一鍵、未命中後再新增等案例，能揭露單一正常範例找不到的問題。
回答前需要釐清的問題
get會更新最近使用順序嗎？ 本題會。若另有唯讀peek，它才不移動節點。- 更新既有鍵會占用新容量嗎？ 不會。
put只修改同一筆資料的值和順序，不能淘汰其他鍵。 - 未命中回傳什麼？ 本題的值是非負整數，
-1專門表示未命中；若值域也包含-1，API 應改為回傳可選值。 - 容量 0 是否合法？ 本實作拒絕非正容量。若允許 0，每次新增都要立即消失，建構式契約也會改變。
- 要求嚴格最壞情況
O(1)嗎？ 一般雜湊表通常提供預期常數時間。若要求嚴格最壞界限，需要不同查找結構或更強假設。 - 能否使用標準有序對映？ 正式程式或短題中可能允許，但面試官仍可要求手寫底層串列並說明不變量。
- 需要執行緒安全嗎？ 本題不需要。若加入這項要求，要記得
get會修改順序，因此同步語意上也是寫入操作。
30 秒回答框架
「我需要預期常數時間的查找和順序更新，所以用雜湊表把鍵對映到雙向鏈結串列節點。靠近頭部的是最近使用，靠近尾部的是最久未使用；虛擬頭尾讓取下與插入保持一致。命中或更新就把節點移到頭部；新增造成超出容量時，從串列和雜湊表同時刪除 tail.prev。對映與串列始終包含同一組真實節點，因此 get、put 都是預期 O(1)，空間是 O(capacity)。」
分步深入解答
只用串列可以保存順序，但查找鍵和刪除任意資料要 O(n)。只用雜湊表可以快速找到值，卻不能直接知道誰最久沒用。陣列加雜湊表仍會在搬移元素或尋找前一個節點時付出 O(n)。題目的兩項限制共同需要一份查找索引和一份可快速修改的順序。
全文採用這個方向：
head <-> 最近使用 <-> ... <-> 最久未使用 <-> tail兩個虛擬節點永遠不進入雜湊表，也不計入容量。每個真實節點保存 key、value、prev 和 next。節點必須保存鍵，因為淘汰從 tail.prev 開始，需要直接刪除對應的對映，不能再反向掃描雜湊表。
四條不變量讓實作可以逐行檢查：
- 快取非空時，
head.next是最近使用節點，tail.prev是最久未使用節點。 - 雜湊表中的鍵與串列中的真實節點一一對應，描述同一組資料。
- 任意相鄰節點都滿足
left.next is right且right.prev is left。 - 每個公開操作結束後，都有
0 <= len(nodes) <= capacity。
get 和 put 確實重複使用相同的指標操作，因此把取下與插到頭部放在兩個私有方法中：
class Node:
__slots__ = ("key", "value", "prev", "next")
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
if capacity <= 0:
raise ValueError("capacity must be positive")
self.capacity = capacity
self.nodes = {}
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def _detach(self, node: Node) -> None:
node.prev.next = node.next
node.next.prev = node.prev
def _attach_after_head(self, node: Node) -> None:
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def _mark_recent(self, node: Node) -> None:
self._detach(node)
self._attach_after_head(node)
def get(self, key: int) -> int:
node = self.nodes.get(key)
if node is None:
return -1
self._mark_recent(node)
return node.value
def put(self, key: int, value: int) -> None:
node = self.nodes.get(key)
if node is not None:
node.value = value
self._mark_recent(node)
return
node = Node(key, value)
self.nodes[key] = node
self._attach_after_head(node)
if len(self.nodes) > self.capacity:
victim = self.tail.prev
self._detach(victim)
del self.nodes[victim.key]attachafter_head 中的指定順序有實際意義。新節點先記住原本第一個節點，再讓原節點反向指向新節點，最後才覆蓋 head.next。若太早改掉 head.next，可能失去仍需修改 prev 的相鄰節點參照。
正確性可以對操作序列做歸納。初始化滿足四條不變量；未命中不改變狀態；命中或更新只取下一個已對映節點，再把同一節點插到頭部，成員集合和大小都不變。新增鍵時先同時加入兩個結構；若大小變成 capacity + 1，再從串列和對映刪除 tail.prev，一一對應關係與容量上限隨即恢復。容量為正保證被淘汰的是一個真實節點。
容量為 2 時，依序執行 put(1,10)、put(2,20)、get(1)、put(3,30)、put(1,15)，從最近到最舊的順序依次是 [1]、[2,1]、[1,2]、[3,1]、[1,3]。鍵 2 被淘汰，更新鍵 1 只改值和順序，不會淘汰鍵 3。
在雜湊表平均效能假設下，每個公開方法只做一次查找、固定次數的指標修改和對映操作，所以預期時間為 O(1)。雜湊表和串列最多保存 capacity 個真實節點，空間為 O(capacity)。這不代表雜湊表在任何輸入下都有嚴格最壞常數時間。
驗證要把範例軌跡和不變量檢查放在一起：空快取未命中、容量 0 被拒絕、容量 1、不同鍵使用相同值、滿容量更新既有鍵、重複命中、交替淘汰和長隨機操作流。隨機測試可以用簡單的 O(n) 參考模型比較回傳值與順序，並在每次操作後斷言雙向指標互相對應、節點不重複、對映與串列集合相同、大小不超過容量。
若允許使用函式庫，依存取順序排列的對映可以更短地表達同一策略。例如 Java 的 LinkedHashMap 支援依存取排序和移除最舊資料的鉤子，適合正式程式，但不能取代面試中的不變量證明。也要區分面試中的精確單行程 LRU 與正式快取淘汰：大型服務可能採用抽樣近似 LRU，以減少全域順序的中繼資料和競爭。
高品質示範回答
「我先明確契約：容量必須為正，未命中回傳 -1，每次命中和 put 都更新最近使用順序；更新既有鍵不增加大小。目標是建立在雜湊表平均查找上的預期 O(1)。
雜湊表解決依鍵定位，卻沒有淘汰順序。雙向鏈結串列保存順序，而且只要已拿到節點，就能用固定指標操作把它取下。我會把雜湊表寫成 key -> node，串列從頭部虛擬節點後的最近使用項目排到尾部虛擬節點前的最久未使用項目。節點保存鍵，尾部淘汰時才能同步刪除對映。
核心不變量是雜湊表與真實串列節點始終是同一集合。命中時取下節點並插到頭部；更新時修改值後做相同移動；新鍵先加入兩個結構，若超過容量，再從兩個結構刪除 tail.prev。虛擬節點讓第一個、最後一個和唯一節點都走同一套指標邏輯。
我會重點測容量 1、滿容量更新、重複 get 改變淘汰對象，以及未命中不改變順序；再用慢速參考模型比對隨機操作，逐次走訪串列檢查不變量。最後每個操作預期 O(1)，空間是 O(capacity)。」
常見錯誤
- 雜湊表只保存值 → 命中後仍要在線性結構中尋找節點 → 讓每個鍵直接指向串列節點。
- 使用單向鏈結串列 → 雜湊表提供節點卻沒有前一個節點，刪除任意節點仍可能掃描 → 同時保存
prev和next。 - 節點不保存鍵 → 尾部淘汰時無法直接刪除對映 → 節點同時保存鍵和值。
- 把插入順序當成最近使用順序 → 成功的
get沒有改變下一次淘汰對象 → 每次命中都移到最近端。 - 更新既有鍵時也執行淘汰 → 大小沒有增加，卻誤刪無關資料 → 先處理更新並回傳，再進入新鍵超容判斷。
- 只從一個結構刪除淘汰項 → 產生過期對映或串列幽靈節點 → 對稱更新兩個結構，並測試集合相等。
- 分別處理頭、尾和單節點 → 指標路徑過多，邊界行為容易不一致 → 使用兩個永久虛擬節點。
- 聲稱嚴格
O(1)→ 雜湊表通常只是預期界限，碰撞時可能退化 → 明確說出雜湊假設。 - 只檢查回傳值 → 錯誤順序可能到後續淘汰才曝光 → 同時斷言完整順序與指標不變量。
追問及應對
追問一：如何改成執行緒安全？
get 會修改串列，因此也是寫入操作。最簡單的正確擴充是用一把互斥鎖包住完整的 get 或 put，確保對映和串列原子更新。一般讀寫鎖不能把命中視為讀取。分片可以降低競爭，但每個分片會有獨立 LRU 順序；若要維持一個精確全域順序，仍需要共享的排序協調。
追問二：如何加入 TTL？
TTL 與最近使用是兩種獨立淘汰規則。命中前要先判斷是否過期，put 也可能在容量淘汰前清理過期項目。使用依過期時間排序的最小堆可以惰性清理，但維護成本變成 O(log n)，也會產生舊堆紀錄；時間輪則改變精度和實作。沒有重新定義過期機制與界限時，不能繼續宣稱兩個操作都是 O(1)。
追問三：能否保證嚴格最壞情況 O(1)？
串列部分已經只有固定次數的指標操作。查找部分取決於雜湊表保證。嚴格最壞常數查找需要更強的字典模型、有限鍵域上的直接定址，或專門的雜湊假設。使用一般語言雜湊表時，應依其契約表述為預期或攤銷 O(1)。
追問四：為什麼不用 LinkedHashMap 或 OrderedDict？
當函式庫的存取順序和淘汰語意符合需求、手寫指標沒有額外價值時，應使用函式庫。面試中先說明底層對映和鏈式順序不變量，再提出函式庫方案。還要核對讀取、更新、走訪和最舊項目刪除是否都算一次存取；名稱相近的有序對映不一定有相同語意。
追問五：大型快取服務會使用精確 LRU 嗎？
不一定。維護一個精確全域存取順序，會讓每次命中都產生中繼資料寫入和競爭點。正式快取可能依分片維護順序、抽樣候選鍵，或在存取頻率更能預測重複使用時選擇 LFU。這些方案用淘汰精確度交換記憶體與吞吐；面試物件仍有價值，因為它的精確策略與不變量可以完整驗證。