图解 LFU 缓存淘汰算法以及在 Redis 中的应用（附带个人完整代码实现）

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.freq_dict = {}
        self.min_freq = 0
        self.data = {}
 
    def get(self, key: int) -> int:
        if key not in self.data:
            return -1
        self.increase_freq(key)
        return self.data[key]
 
    def put(self, key: int, value: int) -> None:
        if self.capacity <= 0:
            return
        if key in self.data:
            self.data[key] = value
            self.increase_freq(key)
        else:
            if len(self.data) >= self.capacity:
                self.remove_min_freq()
            self.data[key] = value
            self.freq_dict[key] = 1
            self.min_freq = 1
 
    def increase_freq(self, key):
        freq = self.freq_dict[key]
        del self.freq_dict[key]
        self.freq_dict[key] = freq + 1
 
    def remove_min_freq(self):
        for key in self.freq_dict:
            if self.freq_dict[key] == self.min_freq:
                del self.data[key]
                del self.freq_dict[key]
                self.min_freq += 1
                break
 
# 使用示例
cache = LFUCache(2)  # 创建一个容量为2的LFU缓存
cache.put(1, 1)
cache.put(2, 2)
cache.get(1)       # 返回 1
cache.put(3, 3)    # 自动淘汰键 2
cache.get(2)       # 返回 -1 (未找到)
cache.get(3)       # 返回 3
cache.put(4, 4)    # 自动淘汰键 1
cache.get(1)       # 返回 -1 (未找到)
cache.get(3)       # 返回 3
cache.get(4)       # 返回 4

这段代码实现了一个简单的LFU缓存淘汰算法。它首先定义了一个LFUCache类，其中包含了缓存的容量、各数据项的访问频率、数据项的数据以及最小的访问频率。put方法用于添加或更新数据，get方法用于获取数据，并根据需要更新访问频率。如果缓存已满，当添加新数据时，会首先淘汰最少访问次数的数据项。这个实现很简单，适合理解LFU原理和实现缓存淘汰策略。