很多人都用过手机里的缓存功能:打开APP秒加载,是因为近期常用的数据被存在了缓存里,但手机存储有限,缓存满了之后就会自动删除很久没用的数据——这背后就是缓存淘汰策略在干活。

一、缓存的核心痛点:为什么需要淘汰策略

1.1 缓存的本质:用空间换时间

缓存的核心逻辑是把频繁访问的数据存在访问速度更快的存储里,比如从手机内存里取数据比从硬盘快100倍以上,所以哪怕多占一点空间,换速度都是划算的。但空间不能无限大,哪怕是服务器的内存,单个应用能分配的缓存空间也很有限。

1.2 缓存溢出的问题:不能无限存

如果缓存满了还继续存新数据,就会出现“缓存溢出”:要么把老数据挤掉,要么直接拒绝新数据。如果直接拒绝新数据,就会出现需要用的时候找不到的情况,体验很差;如果随便挤掉老数据,可能挤掉的是之后还要频繁用的,反而降低了效率。

1.3 常见淘汰策略的短板

常见的淘汰策略有“先进先出”(FIFO,先存的先删)和“最近最少访问”(LRU,最近没用的先删)。FIFO的问题是,比如刚用了一次的热门数据会被当成老数据删掉;而纯LRU如果用普通的数组或者单向链表实现,每次找某个数据都要遍历整个列表,数据多了之后速度会变得很慢,完全失去了缓存的优势。

二、链表+哈希表组合的核心思路

要解决这些问题,就得把两种数据结构的优点结合起来:

2.1 两种数据结构的互补性

哈希表(就是字典)的优点是“查得快”:不管数据有多少,用键找数据都是O(1)的时间,但是它的缺点是“不知道顺序”,没法判断哪个数据是最近没用的;而链表的优点是“能存顺序”,能把最近访问的放在一起,删除最久的只要改指针,但是它的缺点是“查得慢”,找任意一个数据都要挨个遍历。 把这俩拼在一起,哈希表负责“快速找数据”,链表负责“维护访问顺序”,刚好互补。

2.2 集成后的操作逻辑

这个组合的核心逻辑很简单,就像你在图书馆占座位:新来的人要占座,就放在离门最近的位置(对应缓存的新数据放在链表头部);有人用某个座位,就把这个座位移到离门最近的位置(对应访问某个数据就移到链表头部);座位满了之后,把离门最远的那个座位清掉(对应缓存满了就删链表尾部的数据,也就是最久未用的)。

三、完整示例:Python实现LRU缓存(链表+哈希表)

我们用Python来实现这个组合,代码里用双向链表(避免移动节点时要遍历)加哈希表(字典),每个步骤都加了注释,保证大家能看懂。

# 技术栈:Python
# 双向链表节点类,用来存储缓存的键、值,以及前后节点的指针
class DLinkedNode:
    def __init__(self, key=0, value=0):
        self.key = key  # 缓存的键,用来删除哈希表中的对应项
        self.value = value  # 缓存要存的实际数据
        self.prev = None  # 指向前面的节点,方便删除当前节点
        self.next = None  # 指向后面的节点,方便移动节点到头部

# LRU缓存主类,集成了双向链表和哈希表
class LRUCache:
    def __init__(self, capacity: int):
        self.cache = dict()  # 哈希表:key对应节点,快速查找
        # 虚拟头尾节点,简化边界处理(比如只有一个节点的时候,不用单独处理头尾)
        self.head = DLinkedNode()  # 头部节点,标记最近访问的
        self.tail = DLinkedNode()  # 尾部节点,标记最久未访问的
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = capacity  # 缓存的最大容量
        self.size = 0  # 当前缓存里实际存的数据量

    def _add_node(self, node):
        # 把新节点加到链表头部,因为新的是最近访问的
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def _remove_node(self, node):
        # 从链表中删除指定节点,调整前后节点的指针
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node

    def _move_to_head(self, node):
        # 节点被访问后,移到头部,标记为最近访问
        self._remove_node(node)
        self._add_node(node)

    def _pop_tail(self):
        # 删除尾部节点(最久未用的),返回这个节点
        res_node = self.tail.prev
        self._remove_node(res_node)
        return res_node

    def get(self, key):
        # 对外提供的获取数据接口,key不存在返回-1
        node = self.cache.get(key)
        if not node:
            return -1
        # 存在的话,更新访问顺序,移到头部
        self._move_to_head(node)
        return node.value

    def put(self, key, value):
        # 对外提供的写入数据接口,key存在则更新,不存在则新增,满了删最久的
        node = self.cache.get(key)
        if not node:
            # 新增节点
            new_node = DLinkedNode(key, value)
            self.cache[key] = new_node
            self._add_node(new_node)
            self.size += 1
            # 容量超了,删除最久未用的
            if self.size > self.capacity:
                tail_node = self._pop_tail()
                del self.cache[tail_node.key]
                self.size -= 1
        else:
            # 存在节点,更新值,同时更新访问顺序
            node.value = value
            self._move_to_head(node)

# 测试代码,验证功能是否正确
if __name__ == "__main__":
    # 初始化一个容量为2的LRU缓存
    lru = LRUCache(2)
    lru.put(1, 1)
    lru.put(2, 2)
    print(lru.get(1))  # 输出1,数据1被访问,移到头部
    lru.put(3, 3)  # 缓存满了,删除最久的2,现在缓存是1和3
    print(lru.get(2))  # 输出-1,数据2已经被删除

这个测试的结果完全符合我们的预期,说明代码是正确的。

四、这个组合的应用场景

把链表和哈希表集成的缓存策略,几乎是所有需要用到缓存的地方的标准方案,比如:

  1. APP的用户会话缓存:每个用户的登录状态是频繁访问的,要把最近活跃的用户会话存在缓存里,删除很久没登录的,用这个策略能快速处理。
  2. 网页的静态资源缓存:比如浏览器缓存CSS、JS文件,常用的网站的资源会存在缓存里,用户再次访问不用重新下载,删除很久没访问的网站的资源。
  3. 数据库的热点数据缓存:数据库里经常被查询的热门商品信息,存在缓存里,不用每次都查数据库,满了就删很久没被查的商品信息。

五、优缺点分析

这个策略的优缺点都很明显,适合大部分常规场景:

5.1 核心优点

最大的优点是读写时间都是O(1):不管缓存里有多少数据,找一个数据、加一个数据、删一个最久的,都是几步指针操作,不会因为数据多了变慢。对比纯数组实现的LRU,找数据要遍历,时间是O(n),数据多了之后性能差距会非常大。

5.2 主要缺点

主要是实现稍微复杂:要处理链表的指针操作,还要注意虚拟头尾节点的边界,新手很容易出错;另外,内存开销比单纯的哈希表大,因为每个数据要存键、值,还有前后节点的指针,不过这点开销和带来的性能提升相比,完全可以忽略。

六、注意事项

用这个策略的时候,有几个细节要注意,不然会出问题:

  1. 虚拟头尾节点的使用:一定要加虚拟的头尾,不然处理只有一个节点的时候,会出现空指针异常,比如刚加了第一个数据,删除的时候如果没有虚拟节点,就会不知道指向谁。
  2. 更新键的处理:写入的时候如果键已经存在,一定要更新对应的节点的值,而不是新建一个节点,不然链表的顺序会乱,哈希表也会存重复的键。
  3. 容量边界的判断:缓存满了之后,一定要先删除最久的节点,再加新的节点,顺序不能反,不然会出现数据量超过容量的情况。

七、总结

缓存淘汰策略是提升系统性能的核心技巧,而把链表和哈希表集成的LRU策略,是目前最实用的方案:用哈希表解决快速查找的问题,用链表解决维护访问顺序的问题,两者互补后,既保持了O(1)的读写速度,又能高效判断该淘汰哪个数据。不管是做服务器开发、前端开发还是移动端开发,理解这个思路都能帮你写出性能更好的缓存逻辑。