O(1)のgetとputを持つLRUキャッシュをどのように設計しますか?

Question

Accepted Answer

**LRU (Least Recently Used) キャッシュ**は、容量に達したときに最も長時間アクセスされていないアイテムを削除します。古典的な設計は**ハッシュマップ**(O(1)ルックアップ)と**双方向リンクリスト**(O(1)再配列)を組み合わせ、**O(1)のgetとput**を実現します。 ## 2つの構造の設計 ```text HashMap: key -> node DLL (recency order): MRU <-> ... <-> LRU get/put: map finds node move touched node to front (MRU) in O(1); DLL splices it evict the tail (LRU) when full to the front in O(1) ``` ## Code ```python from collections import OrderedDict class LRUCache: def __init__(self, capacity): self.cap = capacity self.cache = OrderedDict() # preserves access order def get(self, key): # O(1) if key not in self.cache: return -1 self.cache.move_to_end(key) # mark as most recently used return self.cache[key] def put(self, key, value): # O(1) if key in self.cache: self.cache.move_to_end(key) self.cache[key] = value if len(self.cache) > self.cap: self.cache.popitem(last=False) # evict least recently used ``` `OrderedDict`は、まさに上記で説明した構造であるハッシュマップと双方向リンクリストそのものです。 | 操作 | 時間 | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## 双方向リンクリストが必要な理由双方向リンクリストにより、**ノードを中央からO(1)で取り外す**ことができます(その`prev`/`next`を保持しているため)。これは単方向リンクリストや配列ではO(n)のシフトなしに不可能です。 ## なぜ重要なのか LRUキャッシュはデータベース、Webサーバー、CPUの前に位置し、ホットデータを高速に保ちながらメモリを制限します。この問題はシニアレベルのインタビューの定番です。なぜなら、2つの構造を組み合わせて、*互いの弱点をカバー*する方法をテストするからです。これはシステムデザインの重要なスキルです。