缓存淘汰算法LRU-K，2Q（Two queues）

本文主要是介绍缓存淘汰算法LRU-K，2Q（Two queues），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.LRU-K

1.1 简介

LRU-K中的K代表最近使用的次数，LRU可以当作LRU-1。LRU-K主要目的是为了解决LRU算法的缓存污染问题。

什么是缓存污染？

当数据访问次数非常少，甚至只会被访问一次，数据服务完访问请求后还继续留在缓存中，白白占用缓存空间，这就是缓存污染。

1.2 原理

相比LRU，LRU-K除了缓存队列还要维护一个访问历史队列，这个队列不缓存数据，仅记录数据的历史访问次数。当数据访问次数达到k次时，数据才放入缓存队列。历史队列、缓存队列的维护与LRU中缓存队列的维护一样，遵循LRU原则。
在这里插入图片描述

1.3 过程

(1). 数据第一次被访问，加入到访问历史列表；

(2). 如果数据在访问历史列表里后没有达到K次访问，则按照一定规则（FIFO，LRU）淘汰；

(3). 当访问历史队列中的数据访问次数达到K次后，将数据索引从历史队列删除，将数据移到缓存队列中，并缓存此数据，缓存队列重新按照时间排序；

(4). 缓存数据队列中被再次访问后，重新排序；

(5). 需要淘汰数据时，淘汰缓存队列中排在末尾的数据，即：淘汰“倒数第K次访问离现在最久”的数据。

LRU-K具有LRU的优点，同时能够避免LRU的缺点，实际应用中LRU-2是综合各种因素后最优的选择，LRU-3或者更大的K值命中率会高，但适应性差，需要大量的数据访问才能将历史访问记录清除掉。

1.4 实现

// 直接继承我们前面写好的LRUCache
public class LRUKCache extends LRUCache {private int k; // 进入缓存队列的评判标准private LRUCache historyList; // 访问数据历史记录public LRUKCache(int cacheSize, int historyCapacity, int k) {super(cacheSize);this.k = k;this.historyList = new LRUCache(historyCapacity);}@Overridepublic Integer get(Integer key) {// 记录数据访问次数Integer historyCount = historyList.get(key);historyCount = historyCount == null ? 0 : historyCount;historyList.put(key, ++historyCount);return super.get(key);}@Overridepublic Integer put(Integer key, Integer value) {if (value == null) {return null;}// 如果已经在缓存里则直接返回缓存中的数据if (super.get(key) != null) {return super.put(key, value);;}// 如果数据历史访问次数达到上限，则加入缓存Integer historyCount = historyList.get(key);historyCount = historyCount == null ? 0 : historyCount;if (historyCount >= k) {// 移除历史访问记录historyList.remove(key);return super.put(key, value);}}
}
————————————————
版权声明：本文为CSDN博主「沙滩de流沙」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_41231928/article/details/120593579