面试题：缓存设计之LRU算法实现

Question

请用你熟悉的编程语言实现LRU（最近最少使用）缓存淘汰算法，假设缓存有固定大小，需要实现添加元素和获取元素的操作，要求代码结构清晰，简要说明实现思路。

Answer 1

以下以Python语言为例实现LRU缓存淘汰算法：

实现思路

1. 使用collections.OrderedDict来存储缓存数据，它能记住元素插入的顺序。
2. 当获取元素时，如果元素存在，将其移动到字典末尾，表示最近使用。
3. 当添加元素时，如果缓存已满，删除字典最前面（最久未使用）的元素，然后将新元素添加到字典末尾。

代码实现

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

测试代码

cache = LRUCache(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))