面试题：缓存设计之LRU算法应用

Question

请阐述LRU（最近最少使用）缓存算法的基本原理，并说明在后端开发中，如何基于Python实现一个简单的LRU缓存。假设缓存的容量是固定的，需要考虑缓存满时如何替换数据，以及缓存命中和未命中时的操作。

Answer 1

LRU缓存算法基本原理

LRU（Least Recently Used）缓存算法的核心思想是，如果数据最近被访问过，那么将来被访问的几率也更高；相反，长时间未被访问的数据，在未来被访问的可能性更低。当缓存已满，需要新的数据进入缓存时，LRU算法会淘汰掉最近最少使用的数据。

基于Python实现简单LRU缓存

from collections import OrderedDict


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

    def get(self, key):
        if key not in self.cache:
            return -1
        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

代码说明

1. 初始化：使用OrderedDict来存储缓存数据，OrderedDict可以记住元素插入的顺序。capacity表示缓存的最大容量。
2. get方法：
   • 如果key不存在于缓存中，返回-1。
   • 如果key存在，将该键值对移动到OrderedDict的末尾，表示最近使用过。然后返回对应的值。
3. put方法：
   • 如果key已存在于缓存中，将该键值对移动到OrderedDict的末尾，并更新值。
   • 如果key不存在，且缓存已满，使用popitem(last = False)删除OrderedDict中最久未使用的元素（最左边的元素）。
   • 最后，将新的键值对插入到OrderedDict的末尾。