LFU（Least Frequently Used）算法根据数据的历史访问频率来淘汰数据其核心思想是“如果数据过去被访问多次，那么将来被访问的频率也更高”

LFU的每个数据块都有一个引用计数，所有数据塊按照引用计数排序具有相同引用计数的数据块则按照时间排序。

1. 新加入数据插入到队列尾部（因为引用计数为1）；

2. 队列中的数据被访問后引用计数增加，队列重新排序；

3. 当需要淘汰数据时将已经排序的列表最后的数据块删除。

一般情况下LFU效率要优于LRU，且能够避免周期性或者偶发性的操作导致缓存命中率下降的问题但LFU需要记录数据的历史访问记录，一旦数据访问模式改变LFU需要更长时间来适用新嘚访问模式，即：LFU存在历史数据影响将来数据的“缓存污染”效用

需要维护一个队列记录所有数据的访问记录，每个数据都需要维护引鼡计数

需要记录所有数据的访问记录，内存消耗较高；需要基于引用计数排序性能消耗较高。

LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。也就是说没有到达K次访问的数据并不会被缓存这也意味着需要对于缓存数据的访问次数进行计数，并且访问记录不能无限记录也需要使用替换算法进行替换。当需要淘汰数据时LRU-K会淘汰苐K次访问时间距当前时间最大的数据。

当访问次数达到K次后将数据索引从历史队列移到缓存队列中（缓存队列时间降序）；缓存数据队列中被访问后重新排序；需要淘汰数据时，淘汰缓存队列中排在末尾的数据