Hur designar du en LRU-cache med O(1) get och put?

Question

Accepted Answer

En **LRU (Least Recently Used) cache** kastar ut elementet som inte har använts på längst tid när den når sin kapacitet. Den klassiska designen kombinerar en **hash map** (O(1) lookup) med en **dubbelriktad länkad lista** (O(1) omordning), vilket ger **O(1) get och put**. ## Designen med två strukturer ```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) ``` ## Kod ```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` är i sig själv en hash map plus en dubbelriktad länkad lista, exakt samma struktur som beskrevs ovan. | Operation | Tid | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## Varför dubbelriktad länkad lista En dubbelriktad länkad lista låter dig **koppla ur en nod från mitten på O(1)** (du håller dess `prev`/`next`), vilket är omöjligt med en enkellänkad lista eller array utan en O(n) förflyttning. ## Varför det spelar roll LRU-cachear sitter framför databaser, webbservrar och processorer för att hålla populär data snabb och minnet begränsat. Det här problemet är ett klassiskt seniornivåintervjusproblem eftersom det testar kombinationen av två strukturer så att *varje täcker den andras svaghet* — en nyckelkunskap inom systemdesign.