PYTHON
Implement a Basic LRU Cache with `collections.OrderedDict`
Learn to build a simple Least Recently Used (LRU) cache using Python's `collections.OrderedDict`, an efficient data structure for managing cache entries based on access order.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key: str) -> any:
if key not in self.cache:
return -1
# Move the accessed item to the end (most recently used)
value = self.cache.pop(key)
self.cache[key] = value
return value
def put(self, key: str, value: any) -> None:
if key in self.cache:
self.cache.pop(key) # Remove existing entry to update and move to end
elif len(self.cache) >= self.capacity:
self.cache.popitem(last=False) # Remove the LRU item (first item)
self.cache[key] = value # Add new item to the end (most recently used)
# Example Usage:
lru_cache = LRUCache(capacity=3)
lru_cache.put("user1", {"name": "Alice"})
lru_cache.put("user2", {"name": "Bob"})
lru_cache.put("user3", {"name": "Charlie"})
print(f"Cache after initial puts: {list(lru_cache.cache.keys())}")
print(f"Get user2: {lru_cache.get('user2')['name']}")
print(f"Cache after getting user2: {list(lru_cache.cache.keys())}")
lru_cache.put("user4", {"name": "David"}) # This will evict user1 (LRU)
print(f"Cache after adding user4: {list(lru_cache.cache.keys())}")
print(f"Get non-existent key: {lru_cache.get('user1')}")
How it works: This snippet demonstrates how to implement a basic Least Recently Used (LRU) cache using Python's `collections.OrderedDict`. An `OrderedDict` remembers the order in which its items were inserted. By leveraging `pop(key)` to remove an item and then re-inserting it, we move it to the end (most recently used). When the cache reaches its `capacity`, `popitem(last=False)` efficiently removes the item at the beginning (least recently used) to make space for new entries, ensuring efficient cache management.