面试题：缓存设计：MRU缓存替换策略的实现思路

以Python为例：

数据结构：
- 使用OrderedDict来实现MRU缓存。OrderedDict是Python标准库collections模块中的一个字典子类，它记住元素插入的顺序，并且在对字典进行更新操作时，会将刚访问或插入的元素移动到字典的末尾，这一特性正好符合MRU缓存策略。
主要操作逻辑：
- 获取数据（get操作）：
  - 当请求缓存中的数据时，首先检查缓存中是否存在该数据。
  - 如果存在，将该数据移动到OrderedDict的末尾（表示最近使用），然后返回该数据。
  - 如果不存在，返回None（或者根据业务需求返回其他表示未命中的值）。
- 插入数据（put操作）：
  - 当插入新数据时，首先检查缓存是否已满。
  - 如果缓存已满，移除OrderedDict中最早插入的元素（也就是字典的第一个元素）。
  - 然后将新数据插入到OrderedDict的末尾。

以下是Python代码示例：

from collections import OrderedDict


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

    def get(self, key):
        if key not in self.cache:
            return None
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        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

你可以这样使用这个缓存类：

cache = MRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))  
cache.put(3, 3)  
print(cache.get(2))  
cache.put(4, 4)  
print(cache.get(1))  
print(cache.get(3))  
print(cache.get(4))

上述代码实现了一个简单的MRU缓存，MRUCache类在初始化时接受一个capacity参数表示缓存的容量。get方法用于获取缓存数据并将其标记为最近使用，put方法用于插入或更新缓存数据，同时在缓存满时移除最早使用的数据。

星途面试题库

面试题：缓存设计：MRU缓存替换策略的实现思路

知识考点

面试题答案