lru与lru-k区别
LRU（最近最少使用替换算法）
思想：如果数据最近被访问过，那么将来被访问的几率也更高。
实现：使用一个栈，新页面或者命中的页面则将该页面移动到栈底，每次替换栈顶的缓存页面。
优点：LRU算法对热点数据命中率是很高的。
缺点：
1.缓存颠簸，当缓存（1，2，3）满了，之后数据访问（0，3，2，1，0，3，2，1。。。）（3弹出，0进入。后面为了访问3又要置换而弹出2，PUSH入3，而马上又要访问2，又要在置换。。。。）。
2.缓存污染，突然大量偶发性的数据访问，会让内存中存放大量冷数据。(可能会由于一次冷数据的批量查询而误导大量热点的数据)
LRU-K（LRU-2、LRU-3）
思想：最久未使用K次淘汰算法。
LRU-K中的K代表最近使用的次数，因此LRU可以认为是LRU-1。LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题，其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。
相比LRU，LRU-K需要多维护一个队列，用于记录所有缓存数据被访问的历史。只有当数据的访问次数达到K次的时候，才将数据放入缓存。当需要淘汰数据时，LRU-K会淘汰第K次访问时间距当前时间最大的数据。
实现：
1）数据第一次被访问，加入到访问历史列表；
2）如果数据在访问历史列表里后没有达到K次访问，则按照一定规则（FIFO，LRU）淘汰；
3）当访问历史队列中的数据访问次数达到K次后，将数据索引从历史队列删除，将数据移到缓存队列中，并缓存此数据，缓存队列重新按照时间排序；
4）缓存数据队列中被再次访问后，重新排序；
5）需要淘汰数据时，淘汰缓存队列中排在末尾的数据，即：淘汰“倒数第K次访问离现在最久”的数据。
LRU
LRU（Least Recently Used）是一种缓存淘汰策略，用于在缓存空间不足时决定哪些项目被移除以腾出空间来存储新的数据。LRU策略的基本思想是：当需要淘汰一个缓存项时，选择最近最少使用的缓存项进行移除。
具体来说，LRU策略会维护一个访问顺序列表，当有数据被访问时，该数据项会被移动到列表的最前面，表示它是最近访问过的。当缓存达到容量上限且需要插入新数据时，LRU策略会移除列表末尾的数据项，因为那些在最长时间内没有被访问的数据项被认为是最近最少使用的。
例如，假设缓存容量为3，按以下访问顺序访问缓存项：A -> B -> C -> A -> D。那么在进行D的插入时，缓存中的数据项顺序可能变为：C -> A -> D，B被淘汰，因为它是最近最少使用的。
LRU策略在许多情况下表现良好，特别适合对数据访问模式有时局部性（局部数据集会被反复访问）的场景。
LRU-K
LRU-K是对经典的LRU（Least Recently Used）缓存淘汰策略的一种改进和扩展，它引入了历史信息来更准确地判断哪些缓存项应该被淘汰。LRU-K考虑了过去K次访问的历史，而不仅仅是最近的一次访问。
在经典的LRU策略中，当缓存满时，会选择最久未使用的缓存项进行淘汰。但在某些情况下，这可能不是最优的选择，特别是在存在顺序泛洪（Sequential Flooding）等情况下，经典LRU策略可能会失效。
LRU-K引入了K这个参数，表示考虑过去K次访问的历史。它的工作原理如下：
当访问一个缓存项时，将其移动到链表的最前面（或更新历史访问信息）。
当需要淘汰缓存项时，不仅考虑最久未使用的，还要考虑过去K次访问中最久未使用的。
具体实现时，LRU-K可以使用一个双向链表和一个哈希表来维护缓存项和它们的访问历史。在插入和访问操作时，需要更新链表中的顺序，而在淘汰操作时，需要根据历史访问信息选择最适合淘汰的项。
LRU-K可以根据不同的场景和访问模式进行调整K值，从而在不同情况下获得更好的性能。它相对于经典LRU策略来说，在一些特殊情况下，例如频繁顺序访问或周期性访问模式，可能能够更准确地识别和保留需要缓存的数据项。