大家好，我是锋哥。今天分享关于【Python大厂笔试题：手写 LRU 缓存淘汰算法】面试题。希望对大家有帮助；

Python大厂笔试题：手写 LRU 缓存淘汰算法

LRU（Least Recently Used，最少使用）缓存淘汰算法是一种常见的缓存管理策略，它的主要思想是：当缓存达到最大容量时，淘汰最久未被使用的缓存项。在一些实际应用中，比如数据库缓存、浏览器缓存等，LRU算法能有效提高缓存命中率，避免频繁地从磁盘或者数据库读取数据。

在Python中，我们可以通过不同的方式手写实现LRU缓存算法。下面将介绍如何使用Python实现LRU缓存，并给出代码示例。

LRU缓存的实现思路

1. 数据结构的选择：

   • 为了高效地实现LRU缓存，我们需要在O(1)的时间复杂度内完成插入、删除以及查询操作。因此，可以使用双向链表（Doubly Linked List）和哈希表（Hash Map）的组合来实现LRU缓存。
     • 双向链表：可以让我们在O(1)时间内移除最久未使用的缓存项（即链表尾部）以及将缓存项移到最前面（表示最近使用）。
     • 哈希表：可以让我们在O(1)时间内访问缓存项。

2. 操作说明：

   • get(key)：返回缓存中存储的值，如果缓存中没有该key，返回-1。
   • put(key, value)：插入缓存项，如果缓存已满，删除最久未使用的缓存项。

Python实现LRU缓存

我们将使用OrderedDict来实现LRU缓存，OrderedDict是Python内置的一个字典，它保持元素插入顺序。我们可以利用它提供的move_to_end方法来模拟LRU缓存中的访问顺序。

代码实现：

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        """
        初始化LRU缓存
        :param capacity: 缓存的最大容量
        """
        self.capacity = capacity
        # 使用OrderedDict来保持缓存项的顺序
        self.cache = OrderedDict()

    def get(self, key: int) -> int:
        """
        获取缓存中key对应的值，如果缓存中没有该key，返回-1
        :param key: 键值
        :return: 如果key存在则返回对应的值，否则返回-1
        """
        if key not in self.cache:
            return -1
        else:
            # 将该key移动到OrderedDict的末尾，表示最近访问
            self.cache.move_to_end(key)
            return self.cache[key]

    def put(self, key: int, value: int) -> None:
        """
        将key-value插入缓存
        :param key: 键值
        :param value: 值
        """
        if key in self.cache:
            # 如果缓存中已有该key，更新其值并将其移动到末尾
            self.cache.move_to_end(key)
        elif len(self.cache) >= self.capacity:
            # 如果缓存满了，删除最旧的缓存（即OrderedDict的第一个元素）
            self.cache.popitem(last=False)
        # 将新的key-value添加到OrderedDict末尾
        self.cache[key] = value

# 示例使用：
lru_cache = LRUCache(3)
lru_cache.put(1, 1)  # 缓存 = {1=1}
lru_cache.put(2, 2)  # 缓存 = {1=1, 2=2}
lru_cache.put(3, 3)  # 缓存 = {1=1, 2=2, 3=3}
print(lru_cache.get(1))  # 返回 1, 缓存 = {2=2, 3=3, 1=1}
lru_cache.put(4, 4)  # 该操作会删除key 2, 缓存 = {3=3, 1=1, 4=4}
print(lru_cache.get(2))  # 返回 -1 (未找到)
print(lru_cache.get(3))  # 返回 3
lru_cache.put(5, 5)  # 该操作会删除key 1, 缓存 = {3=3, 4=4, 5=5}
print(lru_cache.get(1))  # 返回 -1 (未找到)
print(lru_cache.get(4))  # 返回 4

代码解析

1. 构造函数 __init__：

   • 初始化LRU缓存时，我们指定缓存的最大容量 capacity，并使用 OrderedDict 来存储缓存项。OrderedDict 能保持插入的顺序，方便我们访问最旧的元素。

2. get 方法：

   • 如果缓存中存在 key，我们将它移到链表的尾部，表示最近访问，并返回其对应的值。如果缓存中没有 key，返回 -1。

3. put 方法：

   • 如果缓存已满，首先删除最久未使用的缓存项（即 OrderedDict 中的第一个元素）。
   • 如果 key 已存在于缓存中，则更新其对应的值，并将其移到尾部（表示最近访问）。
   • 如果 key 不在缓存中，直接插入新的键值对。

复杂度分析

• get(key) 操作：

  • 时间复杂度是 O(1)，因为我们使用了 OrderedDict，并且访问是基于哈希表的查找。

• put(key, value) 操作：

  • 时间复杂度是 O(1)，在最坏情况下，删除最久未使用的元素也是 O(1)，而更新或者插入操作也是 O(1)。

最后总结下吧

LRU缓存是一种非常高效的缓存淘汰策略，适用于大多数需要缓存的场景。通过结合使用双向链表和哈希表，可以实现高效的缓存管理。Python提供的OrderedDict使得LRU缓存的实现变得非常简单且高效。如果需要更复杂的缓存策略，可以进一步扩展此基础实现。