MST

星途 面试题库

面试题：缓存设计：LRU与LFU基础实现对比

请分别简述LRU（最近最少使用）和LFU（最不经常使用）缓存淘汰策略的核心思想。如果让你用Python实现一个简单的LRU缓存和LFU缓存（假设缓存容量固定），请给出大致的代码框架，并说明关键的数据结构和操作逻辑。
13.4万 热度难度
后端开发缓存设计

知识考点

AI 面试

面试题答案

一键面试

LRU（最近最少使用）缓存淘汰策略核心思想

LRU策略认为如果数据最近被访问过，那么将来被访问的几率也更高。当缓存满时，淘汰最久未使用的数据。

LFU（最不经常使用）缓存淘汰策略核心思想

LFU策略根据数据的访问频率来淘汰数据，认为访问频率低的数据将来被访问的可能性也低。当缓存满时，淘汰访问频率最低的数据，如果有多个访问频率相同的最低数据，则淘汰其中最久未使用的。

Python实现LRU缓存大致代码框架

from collections import OrderedDict


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

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        else:
            if len(self.cache) >= self.capacity:
                self.cache.popitem(last=False)
        self.cache[key] = value

关键数据结构和操作逻辑

  • 数据结构：OrderedDict，它可以记住元素插入的顺序。
  • 操作逻辑：
    • get操作：如果键存在，将其移到OrderedDict末尾（表示最近使用），并返回对应值；不存在则返回 -1。
    • put操作：如果键已存在，更新值并移到末尾；如果键不存在且缓存已满，移除最久未使用（OrderedDict头部）的键值对，再插入新键值对到末尾。

Python实现LFU缓存大致代码框架

import collections


class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.key_to_freq = {}
        self.freq_to_keys = collections.defaultdict(collections.OrderedDict)
        self.min_freq = 0

    def get(self, key: int) -> int:
        if key not in self.key_to_freq:
            return -1
        freq = self.key_to_freq[key]
        value = self.freq_to_keys[freq].pop(key)
        self.key_to_freq[key] = freq + 1
        self.freq_to_keys[freq + 1][key] = value
        if not self.freq_to_keys[self.min_freq]:
            self.min_freq += 1
        return value

    def put(self, key: int, value: int) -> None:
        if not self.capacity:
            return
        if key in self.key_to_freq:
            freq = self.key_to_freq[key]
            self.freq_to_keys[freq].pop(key)
            self.key_to_freq[key] = freq + 1
            self.freq_to_keys[freq + 1][key] = value
            if not self.freq_to_keys[self.min_freq]:
                self.min_freq += 1
        else:
            if len(self.key_to_freq) >= self.capacity:
                while not self.freq_to_keys[self.min_freq]:
                    self.min_freq += 1
                del_key, _ = self.freq_to_keys[self.min_freq].popitem(last=False)
                del self.key_to_freq[del_key]
            self.key_to_freq[key] = 1
            self.freq_to_keys[1][key] = value
            self.min_freq = 1

关键数据结构和操作逻辑

  • 数据结构：
    • key_to_freq：字典，用于记录每个键的访问频率。
    • freq_to_keys：defaultdict(OrderedDict)，外层字典键为频率，值为OrderedDict，记录该频率下的键值对，OrderedDict用于记录相同频率下键的使用顺序。
    • min_freq：记录当前最小访问频率。
  • 操作逻辑：
    • get操作：如果键存在，先从原频率的OrderedDict中移除，更新频率并插入到新频率的OrderedDict中。如果原最小频率的OrderedDict为空，更新min_freq。
    • put操作：如果键已存在，类似get操作更新频率。如果键不存在且缓存已满，移除最小频率且最久未使用的键值对，插入新键值对并设置频率为1，更新min_freq。