缓存淘汰算法是计算机科学中用于管理缓存中数据的一种策略，目的是在缓存空间有限的情况下，决定哪些数据应该被保留，哪些应该被替换。
几种常见的缓存淘汰算法：
- 先进先出（FIFO, First In First Out）
- FIFO算法是最简单的缓存淘汰策略，它按照数据进入缓存的顺序淘汰数据，最先进入缓存的数据会在缓存满时被首先淘汰。
- 最近最少使用（LRU, Least Recently Used）
- LRU算法淘汰最近最少被访问的数据项。它通常通过一个链表来实现，最近访问的数据会被移动到链表的头部，而最老的数据位于链表的尾部，当缓存满时，尾部的数据会被替换。
- 最近最少使用（LFU, Least Frequently Used）
- 这种算法淘汰那些在最近一段时间内被访问次数最少的数据。LFU算法会跟踪每个数据项的访问频率，并在需要淘汰数据时选择频率最低的项。
- 自适应替换缓存（ARC, Adaptive Replacement Cache）
- ARC算法结合了LRU和LFU的特点，它维护两个列表：一个用于最近访问的数据（类似于LRU），另一个用于频繁访问的数据（类似于LFU）。ARC算法会根据访问模式动态调整这两个列表的大小，以适应不同的访问模式。
- 二叉树+链表（2Q）
- 2Q算法是一种基于LRU的改进算法，它使用两个链表来维护缓存中的元素。第一个链表（Q1）包含最近访问的数据，第二个链表（Q2）包含可能再次被访问的数据。当缓存满时，2Q算法会从Q2中淘汰最老的数据。