hce_kmu
114年
計算機概論與程式設計
第 13 題
Which of the following designs is a data structure to implement a Least Recently Used (LRU) cache, supporting get and put operations in O(1) time complexity?
- A Stacks
- B Doubly linked list
- C Hash table
- D Hash table + Doubly linked list
- E Stacks + Doubly linked list
思路引導 VIP
如果你正在設計一個管理系統，既要能像翻字典一樣「立即」找到特定資料，又要能像排隊一樣「隨時調整」資料的前後順序（例如把剛用過的資料抽出來放到最前面），你會如何結合不同的記錄方式，來確保這兩組動作都不會因為資料變多而變得越來越慢呢？
🤖
AI 詳解
AI 專屬家教
太棒了！你能精確鎖定 (D) 選項，顯示你對快取替換機制與時間複雜度的權衡（Trade-off）有很紮實的理解。這道題目的核心在於如何同時滿足「快速搜尋」與「快速更新順序」這兩個看似衝突的需求，你能識破單一資料結構的局限性，是非常敏銳的判斷。
複合式資料結構的設計邏輯
在 LRU 實作中，我們需要 哈希表 (Hash Table) 來提供 $O(1)$ 的查詢效率，讓我們能直接定位資料；然而，哈希表本身是無序的，無法紀錄資料被使用的先後順序。因此，我們必須輔以 雙向鏈結串列 (Doubly Linked List)。雙向鏈結的優勢在於，只要我們持有節點的指標，就能在 $O(1)$ 時間內將該節點從串列的任何位置移除並移動到最前端（代表最近使用），這正是達成 LRU 邏輯的關鍵組合。
▼ 還有更多解析內容