小议LRU算法的实现

雨点打透心脏的1/2处 2022-11-03 00:47 136阅读 0赞

*  ## LRU原理 ##

**LRU**（Least Recently Used）是一种常见的[页面置换算法][Link 1]，原理就是，当数据在最近一段时间经常被访问，那么它在以后也会经常被访问。这就意味着，如果经常访问的数据，我们需要然其能够快速命中，而不常访问的数据，我们在容量超出限制内，要将其淘汰。

*  ## **LRU的思路** ##

对于这种类似序列的结构我们一般可以选择链表或者是数组来构建。

1. 数组 查询比较快，但是对于增删来说是一个不是一个好的选择。  
2. 链表 查询比较慢，但是对于增删来说十分方便O(1)时间复杂度内搞定。  
我们可以选择 **链表 + hash表**，hash表的搜索可以达到0(1)时间复杂度。说一句，JDK中的 **LinkedHashMap **底层就是用的HashMap加双链表实现的。

具体思路如下：

1.  构建双向链表节点ListNode，应包含`key,value,prev,next`这几个基本属性
2.  对于Cache对象来说，我们需要规定缓存的容量，所以在初始化时，设置容量大小，然后实例化双向链表的head,tail，并让head.next->tail tail.prev->head，这样我们的双向链表构建完成。
3.  对于get操作,我们首先查阅hashmap，如果存在的话，直接将Node从当前位置移除，然后插入到链表的首部，在链表中实现删除直接让node的前驱节点指向后继节点，很方便.如果不存在，那么直接返回Null。

*  ## **LRU例子代码** ##

首先，我们把双链表的节点类写出来，为了简化，key 和 val 都认为是 int 类型：

class Node {
        public int key, val;
        public Node next, prev;
        public Node(int k, int v) {
            this.key = k;
            this.val = v;
        }
    }

然后依靠我们的 Node 类型构建一个双链表，实现几个要用到的 API，这些操作的时间复杂度均为 *O*(1) ：

class DoubleList {  
        // 在链表头部添加节点 x
        public void addFirst(Node x);
    
        // 删除链表中的 x 节点（x 一定存在）
        public void remove(Node x);
    
        // 删除链表中最后一个节点，并返回该节点
        public Node removeLast();
    
        // 返回链表长度
        public int size();
    }

为了让读者集中精力理解 LRU 算法的逻辑，就省略链表的具体代码。

到这里就能回答刚才“为什么必须要用双向链表”的问题了，因为我们需要删除操作。删除一个链表节点不光要得到该节点本身的指针，也需要操作其前驱节点的指针，

而双向链表才能支持直接查找前驱，保证操作的时间复杂度 *O*(1)。有了双向链表的实现，我们只需要在 LRU 算法中把它和哈希表结合起来即可。我们先把逻辑理清楚。

![603933c028c45619f0688272ee25aedd.png][]

![d3069aadf3479025b0e481b763c36fa3.png][]

[Link 1]: https://baike.baidu.com/item/%E9%A1%B5%E9%9D%A2%E7%BD%AE%E6%8D%A2%E7%AE%97%E6%B3%95/7626091
[603933c028c45619f0688272ee25aedd.png]: /images/20221024/e7369f8e28ec445782af8189d0e12fd9.png
[d3069aadf3479025b0e481b763c36fa3.png]: /images/20221024/f43af1f5248141ec9f65ba309296f067.png