Как спроектировать LRU-кэш с O(1) для get и put?

Question

Accepted Answer

**LRU (Least Recently Used) кэш** удаляет элемент, который не использовался дольше всего, когда кэш достигает своей емкости. Классический дизайн объединяет **hash map** (O(1) поиск) с **двусвязным списком** (O(1) переупорядочивание), обеспечивая **O(1) для get и put**. ## Дизайн с двумя структурами ```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) ``` ## Код ```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` сам по себе — это hash map плюс двусвязный список, именно структура, описанная выше. | Операция | Время | |---|---| | get | O(1) | | put | O(1) | | память | O(capacity) | ## Зачем двусвязный список Двусвязный список позволяет **отсоединить узел с середины за O(1)** (у вас есть его `prev`/`next`), что невозможно с односвязным списком или массивом без O(n) сдвига. ## Почему это важно LRU-кэши находятся перед базами данных, веб-серверами и процессорами, чтобы горячие данные оставались быстрыми и память была ограничена. Эта задача — основа старших собеседований, потому что проверяет, можете ли вы объединить две структуры так, чтобы *каждая компенсировала слабость другой* — ключевой навык проектирования систем.