Bộ cache kiểu LRU đơn giản bằng Python

Giả sử bạn có một cache với dung lượng tối đa 3 phần tử. Khi thêm phần tử mới vào mà cache đã đầy, nó sẽ xóa phần tử ít được truy cập gần đây nhất.

Mình dùng OrderedDict (có sẵn trong Python) để làm cho code rõ ràng:

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key):
        if key not in self.cache:
            return -1  # không tìm thấy
        # di chuyển key này ra cuối cùng (mới sử dụng)
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            # cập nhật giá trị
            self.cache.move_to_end(key)
        self.cache[key] = value
        # nếu quá dung lượng
        if len(self.cache) > self.capacity:
            # xóa phần tử cũ nhất
            oldest = next(iter(self.cache))
            print(f"Xóa phần tử: {oldest}")
            self.cache.popitem(last=False)

# demo
cache = LRUCache(3)

cache.put("A", 1)
cache.put("B", 2)
cache.put("C", 3)

print(cache.cache)  # OrderedDict([('A', 1), ('B', 2), ('C', 3)])

# truy cập A -> A thành mới nhất
cache.get("A")

cache.put("D", 4)  # lúc này sẽ phải loại bỏ phần tử ít dùng nhất (B)

print(cache.cache)  # OrderedDict([('C', 3), ('A', 1), ('D', 4)])

✅ Khi chạy xong, bạn sẽ thấy B bị loại bỏ vì lâu rồi chưa đụng tới, đúng với nguyên tắc Least Recently Used.