博客

开篇

接下来的文章我们会介绍有关各种数据结构应用的文章，毕竟数据结构与算法才是

算法

这个概念的完全体，二者搭配才能解决更多问题。比如今天要说的LRU算法。

LRU算法是一种缓存淘汰策略。

计算机的缓存容量有限，如果缓存满了就要删除一些内容，给新内容腾位置。但问题是，我们应该删除哪些内容呢？我们肯定希望删掉那些没什么用处的缓存，而把有用的数据继续留在缓存中，方便之后继续使用。但是判断有用数据的标准是什么呢？

LRU的全称是Least Recently Used，也就是说我们认为最近使用过的数据应该是有用的，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据。

举个例子(

labuladong大佬文章中的原图

)，比如我们先后打开了

设置、手机管家和日历

，那么现在他们在后台排列的顺序应该是这样的：



但是这个时候如果我访问了一下

设置

界面，那么

设置

就会被提前到第一个，变成这样：



假设我的手机只允许我打开3个应用程序，现在已经满了，那么如果我新开了一个应用

时钟

，就必须关闭一个应用，为

时钟

腾地方，但是我们应该关闭哪个呢？

按照LRU策略，我们应该关闭最下面的应用程序，即最久未使用过的程序，如上图的

手机管家

，然后把新开的应用放到最上面。：

这就是LRU策略，我们总是会找到最久没有使用过的应用将其剔除，将刚刚打开的应用放在最上面。

这也有点像操作系统中优先级的分配，一般较长时间没有使用的任务，我们会将其放到最底层，最后来了新任务，它将“石沉大海”。

还有其他的淘汰策略，例如LFU策略，它是按照访问频率而不是访问顺序来淘汰的，各有应用场景。本文我们主要讲解LRU算法。

LRU算法

LRU算法实际上是让你设计数据结构：首先要接收一个capacity参数作为缓存的最大容量，然后实现两个API，一个是put(key,val)方法存入键值对，另一个是get(key)方法获取key对应的val,如果key不存在则返回-1.

看到这里相信很多人都已经意识到了，键值对？那这个数据结构不就是哈希表吗。是的，没错，这个数据结构的确包含哈希表，但不是仅含哈希表，我们继续往下看。

注意一下，这里我们的get和put必须都是时间复杂度为O(1)的，下面我们来举个具体的例子。

LRUCache cache = new LRUCache(2);
 // 你可以把 cache 理解成⼀个队列 
 // 假设左边是队头，右边是队尾 
 // 最近使⽤的排在队头，久未使⽤的排在队尾 
 // 圆括号表⽰键值对 (key, val) 
 cache.put(1, 1); 
 // cache = [(1, 1)] 
 cache.put(2, 2); 
 // cache = [(2, 2), (1, 1)] c
 ache.get(1);
  // 返回 1 
 // cache = [(1, 1), (2, 2)] 
 // 解释：因为最近访问了键 1，所以提前⾄队头 
 // 返回键 1 对应的值 1 
 cache.put(3, 3); 
 // cache = [(3, 3), (1, 1)] 
 // 解释：缓存容量已满，需要删除内容空出位置 
 // 优先删除久未使⽤的数据，也就是队尾的数据 
 // 然后把新的数据插⼊队头 cache.get(2); 
 // 返回 -1 (未找到) 
 // cache = [(3, 3), (1, 1)] 
 // 解释：cache 中不存在键为 2 的数据 
 cache.put(1, 4); 
 // cache = [(1, 4), (3, 3)] 
 //解释:键1已经存在了，把原始值1覆盖为4
 //不要忘了要将简直提前到队头

设计算法

通过分析我们知道，要让put和get方法的时间复杂度为O(1)，要做到这两点，需要满足的条件是：查找快，插入快，删除快，有顺序之分。

因为显然cache必须有顺序之分，以区分最近使用的和很久未使用的数据；而且我们要在cache中查找键值是否存在，如果存在的话我们插入相同键时，应该将值覆盖并且提前；如果容量满了要删除最后一个数据；每次访问还要把数据插入到队头。

下面思考使用什么数据结构。刚才我们提到了，哈希表是需要使用的，因为它查找速度快；那什么数据结构插入删除快呢？答案是双向链表，由于有前后指针，所以链表的删除和插入操作的时间复杂度都为O(1)，并且双向链表在顺序的移动方面也是非常容易的，但是其查找速度慢。于是我们将

哈希表和链表结合

就满足了我们前面所说的要求了。



我知道，到了现在大家一定有很多疑问，为什么双链表可以单链表不行？为什么我们已经使用了hash来存key，还要在链表的结点上存key-val？这些在我们做代码设计的时候都会得到解答。

代码

//定义双链表的结点类
class Node
{
    public:
        int key,val;//键值对
        Node next,prev;//前后指针
        Node(int k,int v)
        {
            this.key = k;
            this.val = v;
        }
};
//依靠结点类型建立一个双链表
class DoubleList
{
    
    public:
        //在链表头部添加结点x,时间为O(1)
        void addFirst(Node x);
        //删除链表中的结点x(x一定存在)
        //由于是双链表且给的是目标Node结点,时间O(1)
        void remove(Node x);
        //删除链表中最后一个结点,并返回该节点，时间复杂度为O(1)
        Node removeLast();
        //返回链表长度,时间O(1)
        int size()
}

这里我们就可以回答为什么使用双向链表而不是单向的链表了，因为我们删除结点的时候，如果是最后一个结点被删除还好说，但如果删除的结点是某一个中间结点，我们就不光要操作它的next指针了，我们还需要获得它的prev指针，才能快速将其删除，所以我们使用双向链表。这样才能保证时间复杂度为O(1)。

我们先来写一下伪代码：

//key映射到Node(key,val)
map<int,Node>hashmap;
//Node(k1,v1)->Node(k2,v2)
DoubleList cache;//把这里想象成一个队列,我们将结点的键值对存入队列
int get(int key)
{
    if(key不存在)
        return -1
    else
    {
        将数据(key,val)提到开头
        return val;
    }
}
void put(int key,int val)
{
    Node x = new Node(key,val);
    if(key已经存在)
    {
        将旧的val删除
        将新结点x放入开头
    }
    else
    {
        if(队列已经满了)
            删除链表的最后一个数据腾位置
            删除map中映射到该数据的键
        将新结点x放入开头
        map中新建key对新结点x的映射
    }  
}

这就是我们各个功能的基本逻辑，下面把它翻译成代码：

//定义双链表的结点类
class Node
{
    public:
        int key,val;//键值对
        Node next,prev;//前后指针
        Node(int k,int v)
        {
            this.key = k;
            this.val = v;
        }
};
//依靠结点类型建立一个双链表
class DoubleList
{
    
    public:
        //在链表头部添加结点x,时间为O(1)
        void addFirst(Node x);
        //删除链表中的结点x(x一定存在)
        //由于是双链表且给的是目标Node结点,时间O(1)
        void remove(Node x);
        //删除链表中最后一个结点,并返回该节点，时间复杂度为O(1)
        Node removeLast();
        //返回链表长度,时间O(1)
        int size()
}
class LRUCache
{
    private:
        //key映射到Node(key,val)
        map<int,Node>hashmap;
        //Node(k1,v1)->Node(k2,v2)
        DoubleList cache;//把这里想象成一个队列,我们将结点的键值对存入队列
        int cap;//最大容量
    public:
        LRUCache(int capacity)
        {
            this.cap = capacity;
            hashmap = new map<>();//定义一个新的哈希表
            cache = new DoubleList();//定义新的队列
        }
        int get(int key)
        {
            if(hashmap.find(key) == hashmap.end())//找不到key值
                return -1
            int val = hashmap[key].val;
            //put函数把键值对提前
            put(key,val);
            return val;
        }
        void put(int key,int val)
        {
            //先把新结点x做出来
            Node x = new Node(key,val);
            if(hashmap.find(key)!=hashmap.end())
            {
                cache.remove(hashmap[key]);
                cache.addFirst(x);
                hashmap.put(key,x);
            }
            else
            {
                if(cap == cache.size())
                    //删除链表的最后一个数据腾位置
                    Node last = cache.removeLast();
                //将新结点x放入开头
                cache.addFirst(x);
                //map中新建key对新结点x的映射
                hashmap.put(key,x);
            }  
        }
}

看完代码我们就可以解决前面的问题了，为什么要在链表中同时存储key和val，而不是只存储val？

回想一下，当我们的内存满了，现在又有新结点加入的时候我们做了什么？

我们先把最后的节点删除，又把hashmap中最后结点的key删除，不占用过多的内存空间。但是我们应该如何知道删除hashmap中的哪个key呢？这就需要从最后一个结点获得了，因为最后一个结点存储的是键值对，所以我们可以获得key并将其删除。所以我们双向链表的结点

数据必须是键值对。

总结

LRU算法到此我们就说完了，其实只是两种数据结构的混合使用而已，但是我们需要自己造轮子，自己定义双向链表的结点类，双向链表类。最后自己定义这个缓存队列类(这个类就包含双向链表+哈希表)。然后就是一些基本的删除、添加、提高优先级(放队首)等操作，这一部分逻辑也都很清晰，自己看着注释捋一遍就好。