what is lru

what is LRU

LRU算法，全程是：Least Recently Used。最近最少使用算法。

这个算法（淘汰算法）的思想是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。所以，当指定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。

LRU实现

leetcode-146-LRU缓存

数组方案

如果我们之前完全没有接触过LRU算法，仅仅知道算法的思路。用数组应该是我们最容易想到的第一个方案。

假设我们又一个定长的数组，数组中的元素都有一个标记。这个标记可以是时间戳、或者是一个自增的数字。

时间戳比较容易。
- 当我们放入一位元素之后，判断数组是否满了，遍历数组找到时间戳最小的一个删除。
- 每访问一个元素，就要更新其时间戳。
如果我们使用的是一个自增数字。
- 每放入一个元素，就把数组中已经存在的数据标记更新一下，进行自增。当数组满了后，就将标记数字最大的元素删除。
- 每访问一个元素，就将被访问的元素的数字置为 0 。

但是这种方案的弊端也很明显：需要不停地维护数组中元素的标记。

你还有其他更优的方案吗？

链表方案

最近最少使用：需要一个有序的结构。假设我们采用链表来实现。

插入一个元素，我们追加到数组的末尾（保证尾部的数据都是最近被访问的数据）
1. 遍历数组，如果数组中存在这个元素，删除当前位置，直接追到到末尾。
2. 如果是新元素：
  - 如果此时缓存未满，直接追到到末尾。
  - 如果此时缓存满了，就删除链表的的头部元素，然后再在末尾追加。
访问一个元素，我们就把被访问到的元素移动到数组的末尾。
当数组满了之后，我们直接从头部移除元素就可以了。

但是这个方案的时间复杂度还是O(n)。你能不能给一个查询和插入的时间复杂度都是O(1)的解决方案？

双向链表+哈希表方案

为了实现插入和查询的时间复杂度都是O(1)，我们需要满足下面三个条件的数据结构：

首先这个数据结构必须是有时序的，以区分最近使用的和很久没有使用的数据，当容量满了之后，要删除最久未使用的那个元素。

要在这个数据结构中快速找到某个 key 是否存在，并返回其对应的 value。

每次访问这个数据结构中的某个 key，需要将这个元素变为最近使用的。也就是说，这个数据结构要支持在任意位置快速插入和删除元素。

我们思考下：

查询要快，哈希表可以满足。但是哈希表的数据是无序的。有序我们可以考虑链表来实现，并且链表支持快速的插入、删除操作，但是查询慢。

所以我们让哈希表和链表结合一下，形成一个新的数据结构：哈希链表，LinkedHashMap

我们画一张图：感受下：

LinkedHashMap

接下来我们就基于LinkedHashMap来深入探讨2个问题。

为什么要用双向链表呢？单链表可以吗？
为什么链表还需要存储key呢？只存储value不可以吗？

为什么要双向链表呢？

假设我们要删除一个元素，删除一个元素，我们可以通过hash表通过O(1)来定位到元素。我们得到了要删除的元素，但是此时我们需要维护链表的结构，我们还需要此元素的前驱节点的指针。这样才满足用O(1)的时间复杂度来完成删除操作。

为什么链表的节点要存储key呢？

此时我们顺利删除了链表中的节点，但是我们还需要维护hash表的元素呀，我们需要通过key来定位hash表的元素。

Java-LinkedHashMap方案

经过我们前面的讨论，我们直接给出java的实现版本。

class LRUCache extends LinkedHashMap<Integer, Integer>{

    private Integer capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return getOrDefault(key, -1);

    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */