我们曾经讨论过 LRU 缓存的实现，在那篇文章中，我们也顺带介绍了什么是缓存替换策略。
现在我们再来回顾一下，简单来说，缓存是一种支持键值对的存、取操作的数据结构，因为计算机上的缓存空间是非常昂贵的，所以一个缓存实例总共支持存取的键值对的数量 capacity（包括每个键值对中值的长度大小）都是相对固定的，「相对」是说它不像常规的、建立在主内存 RAM 上的那些数据结构一样可以随着自身的 size 的增长而动态增长 capacity .
例如，考虑一个标准库模板 std::vector 的实例类型 std::vector<int> 的对象 std::vector<int> v , 举例来说，它一开始的 capacity 可能是 10, 但是当我们已经对 v 这个 vector 对象 push_back 了 10 个元素之后，是不是就不能再继续往里边 push_back 了呢？
事实上，v 的 capacity 会按需增加，std::vector 的实现会在 capacity 不够用的时候为 v 申请更多的存储空间，然后更新 v 的 capacity , 确保 v 始终能装下更多的元素。
这个动态申请更多内存空间的过程是通过系统调用 (system call) 完成的，而操作系统的内核调用最终会由 CPU 交给操作系统内核 (kernel) 的代码来处理，内核代码先查看这个进程的堆内存链表上是否有足够多的空间可用于分配，如果不够就增长进程的 [brk 指针](https://man7.org/linux/man-pages/man2/sbrk.2.html)，然后从链表中切出一块儿来满足这个动态内存分配请求。
之所以能够这么做，是因为现代计算机的主内存和磁盘空间都是相当大的，我们说「相当大」的意思是说，对于个人而言这么大的空间大多数时候都够用，而对于运行在计算机上的操作系统和运行在操作系统上的进程而言，对于进程里边的某个数据结构的实例，比如说这个 std::vector<int> v 而言，空间不够的时候总能再请求分配更多。
而一个 cache, 它通常来说都是被构建在空间大小相对固定的地方，毕竟我们都知道，高速缓存的存取需要的 CPU 指令周期数相对于主内存的而言要少很多，也就是说它非常「快速」（快速是一个不严谨但是很形象的词，不过请不要把这里的「快速」和「高吞吐量」混淆），快速、大容量和低价格是不可兼得的，所以说 cache 它一般而言就没法动态申请更多的 capacity 来满足不断 push 进来的键值对的存储空间需求。
这样一来就需要在 cache 的 capacity 不够用时，把「很久不用了的」键值对抛弃掉，把抛弃掉这个键值对释放出来的那点空间用来存储新进来的那个键值对。
那么，cache 里面有这么多个键值对，在这么多个键值对当中，判断哪个键值对是「很久不用了的」的键值对的算法，就是缓存失效算法，或者叫做缓存失效策略，也有叫缓存替换策略。
逻辑上，你可以认为 LRU 缓存或者 LFU 缓存的具体实现内部都维护着一个队列，这个队列可以认为是关于 key 的队列，那么，所谓的 LFU, LRU 都可以看作是这个 key 队列的一个「排序准则」。
在 LRU 缓存替换策略中，这个 key 队列的队尾一定是对应着那个 LRU Key, 每一次缓存需要 evict 一个 key 的时候，就会去看一下这个队尾，队尾是哪个，LRU Key 就是哪个。
而在 LFU 缓存替换策略中，这个「key 队列」仍然存在，它的排序准则是这样：首先把 key 按照命中频次排列（一个新的 key 它的命中频次在首次使用之后是 1，一个正常 key 经过 evict 之后它就又变成新的 key），而如果两个 key 的命中频次相同，再按照最近命中时间排列——最近一次命中离现在更近的排前面。
举例来说，假设我们以 (key,useCount) 这样的格式来表示一个 key (value 对于 key 的顺序而言不重要，换句话说 value 不会影响 key 队列的格局），假设当前的 cache 的 key 队列是这样的格局：
(3,10) (7,2) (1,2) (5,2) (9,1), (8,1)
|
这个就是 LFU Key
队首在最左，队尾在最右，8 是 LFU Key, 1 代表这个 key 目前总计被命中一次（初始命中那次也算），
假设我们当前再 get 一次 5 这个 key（也就是对应图中 (5,2) 那个 key，它当前已经被命中了 2 次），那么这个队列的格局会如何变化呢？或者说，5 这个 key 的新位置在哪呢？
首先，5 的命中次数会自增，从 2 变成 3, 然后我们从队列的左边往右边遍历，找到第一个这样的节点 (key,useCount), 它满足 useCount ≤ 3, 然后把 (5,3) 插入在这个节点前面。