LRU算法

一、什么是LRU

LRU是什么？按照英文的直接原义就是Least Recently Used,最近最久未使用法，它是按照一个非常著名的计算机操作系统基础理论得来的：最近使用的页面数据会在未来一段时期内仍然被使用,已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用。基于这个思想,会存在一种缓存淘汰机制，每次从内存中找到最久未使用的数据然后置换出来，从而存入新的数据！它的主要衡量指标是使用的时间，附加指标是使用的次数。在计算机中大量使用了这个机制，它的合理性在于优先筛选热点数据，所谓热点数据，就是最近最多使用的数据！因为，利用LRU我们可以解决很多实际开发中的问题，并且很符合业务场景。

二、LRU的实现原理

根据LRU的原理我们可以知道数据在淘汰时总会先淘汰最久未被使用的，如果我们可以按照数据的更新时间排序不就可以很好的处理这样的场景了吗？所以我们采用双端链表，头部一定是最近更新的数据，尾部就是最久未被更新的数据。

public class LRU<K, V> {
    private int currentSize;//当前的大小
    private int capcity;//总容量
    private HashMap<K, Node> caches;//所有的node节点，这里加map的原因是为了提高查询效率，时间复杂度O(1)
    private Node first;//头节点
    private Node last;//尾节点
 
    public LRU(int size) {
        currentSize = 0;
        this.capcity = size;
        caches = new HashMap<K, Node>(size);
    }

插入：添加元素的时候首先判断是不是新的元素，如果是新元素，判断当前的大小是不是大于总容量了，防止超过总链表大小，如果大于的话直接抛弃最后一个节点，然后再以传入的keyvalue值创建新的节点。对于已经存在的元素，直接覆盖旧值，再将该元素移动到头部，然后保存在map中。

这种方式虽然简单，在频繁访问热点数据的时候效率高，但是它的缺点在于如果是偶尔的批量访问不同的数据时其命中率就会很低。比如我频繁的访问A，接着访问不同的数据直到A被淘汰，此时我再访问A，则不得不又再次把A加入到Cache中，显然这种方式是不合时宜的，因为A已经访问了很多次了，不应该将其淘汰而把一堆只访问一次的数据加入到Cache中。

LRU-K
LRU-K中的K代表最近使用的次数，因此LRU可以认为是LRU-1。LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题，其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。
相比LRU，LRU-K需要多维护一个队列，用于记录所有缓存数据被访问的历史。只有当数据的访问次数达到K次的时候，才将数据放入缓存。当需要淘汰数据时，LRU-K会淘汰第K次访问时间距当前时间最大的数据。

数据第一次被访问时，加入到历史访问列表，如果数据在访问历史列表中没有达到K次访问，则按照一定的规则（FIFO,LRU）淘汰；当访问历史队列中的数据访问次数达到K次后，将数据索引从历史队列中删除，将数据移到缓存队列中，并缓存数据，缓存队列重新按照时间排序；缓存数据队列中被再次访问后，重新排序，需要淘汰数据时，淘汰缓存队列中排在末尾的数据，即“淘汰倒数K次访问离现在最久的数据”。
LRU-K具有LRU的优点，同时还能避免LRU的缺点，实际应用中LRU-2是综合最优的选择。由于LRU-K还需要记录那些被访问过、但还没有放入缓存的对象，因此内存消耗会比LRU要多。