前言

LRU算法和LFU算法是属于页面置换的一种算法，或者更通俗的说，就是缓存如何淘汰的一种策略。

我们通常在设计一个系统的时候，由于数据库的读取速度远小于内存的读取速度，所以为了加快读取速度，会将一部分数据放到内存中，称为缓存。

但是内存容量是有限的，当你要缓存的数据超出容量，就得有部分数据删除，这时候哪些数据删除，哪些数据保留，就是LRU算法和LFU算法要干的事。

什么是LRU算法

LRU算法，全称Least recently used，即最近最少使用。LRU算法的思想是如果数据最近被访问过，那么将来被访问的概率也会很高。

根据这个思想，我们可以想到，实现LRU算法肯定会用到列表/链表，目的是保证有序；还有一个是用到哈希表，这是因为缓存经常是key-value键值对的形式。

比较简单的做法是使用列表+哈希表，但是这种方式查询和插入的时间复杂度都是O(n)，还有一种做法是使用双向链表+哈希表，查询和插入的时间复杂度都是O(1)，但是耗费的空间资源比较多。

如上图，假设我们使用头插法，即最近访问的元素放在最前面，最晚的元素放在最后面，则实现LRU算法的步骤如下：

这应该是面试比较常考的点，面试官可能会问你，如果实现一个时间复杂度为O(1)的LRU缓存？

这种实现的结构如下：

上述LRUCache的m其实就是上图左边的HashMap，它的目的是为了实现查找的时间复杂度为O(1)。

如果没有这个m，则查找元素的时候，需要遍历双向链表，时间复杂度为O(n)。

而使用双向链表的原因主要是为了实现节点插入/删除的时间复杂度为O(1)。

那使用单链表不行吗？

如上，使用单链表的话，可以实现头部快速插入新节点，尾部快速删除旧节点，时间复杂度都是O(1)。

但是对于中间节点，比如我需要节点1的值由2更新为4，这时候除了更新值，还需要将其移动到最前面，而对于单链表，它只知道下一个元素，并不知道上一个元素，为了得到上一个元素，它必须遍历一次链表才知道，时间复杂度为O(n)，这就是为什么要用双向链表的原因。

关于这种方式的源码实现，可以查看Leetcode LRU双向链表实现

LFU算法，全称Least frequently used，即最不经常使用。LFU算法的思想是一定时期内被访问次数最少的节点，在将来被访问到的几率也是最小的。

由此可以看到，LFU强调的是访问次数，而LRU强调的是访问时间。

LFU有两种实现方式，一是哈希表+平衡二叉树，二是双哈希表，下面以双哈希表为例，说明LFU具体的步骤：

双哈希表的实现如下图：

如上，双哈希表需要维护两个哈希表以及一个最少频次使用的计数minFreq。

第一个哈希表是 freq_table，它的key是访问的频次，它的value是一个双向链表，双向链表的每一个节点包含三个元素：key，value，以及count。

第二个哈希表是 key_table，它的key是双向链表中存储的key，value是对应节点的指针（这样查找的时间复杂度就是O(1)）。

类比LRU，LFU的步骤如下：

1.假设LFU缓存容量为3，且一开始初始化插入三个键值对（1，1），（2，2），（3，3）此时每个键值对的频次都是1，所以它们都在同一个双向链表上，如图四。
2.假设这时候查找key=1，由于key_table存储的是节点的指针，所以可以以O(1)的复杂度得到结果。
2.1 注意此时节点1的频次由1变为2，所以要将节点1移动到频次为2的链表，如图五
2.2 另外，minFreq也要记得同步更新，不过本次操作不用。
3.假设这时候插入一个新的键值对（4，4），由于它的频次为1，所以对应链表1，它会被插入到链表1的最前面，而由于这种操作，所以同链表的最后一个元素肯定是最晚插入的。
3.1 由于新加的元素导致容量溢出，所以我们要删除频次最少，插入时间最晚的，即图五的（3，3，1）