【redis前传】自己手写一个LRU策略 | redis淘汰策略

妖狐艹你老母 2022-10-09 14:27 172阅读 0赞

# 一、题目描述 #

#### [146. LRU 缓存机制][146. LRU] ####

> 运用你所掌握的数据结构，设计和实现一个 `LRU` (最近最少使用) 缓存机制 。  
> 实现`LRUCache` 类：
> 
> `LRUCache(int capacity)` 以正整数作为容量 capacity 初始化`LRU`缓存  
> int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。  
> void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
> 
> 进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？
> 
> ![image-20210611091820720][]

# 二、思路分析 #

## 第一想法 ##

*  刚看到本题时没有多想就觉得会用到队列，因为队列FIFO可以做到淘汰末尾数据，但是仔细一想本题是需要淘汰*最近最少使用*数据，如果仅仅是最近的数据那么队列很容易实现。加上使用频率就涉及到数据的频繁挪动。很明显队列是无法完成的。
 *  那么有没有一种顺序添加的数据，每次在获取之后就会将数据前移至一端呢？答案是有的！`LinkedHashMap`
 *  `LinkedHashMap` 不熟悉的朋友们可以简单的将它理解成`HashMap` 。 下图展示了`HashMap`的存储结构

![image-20210611091747182][]

*  上述的元素我这里做了个动画演示全过程！！！

![动画演示][f6b0d894a57406aeb7d02d5d9b3c26ef.gif]

*  而`LinkedHashMap`只是多了一条链表串起里面的元素

![f14be693022af46db0324f027f634027.png][]

*  这也是为什么`LinkedHashMap`是按照顺序存储的。但是`LinkedHahsMap`也无法做到按照使用频率进行排序啊？大家都知道他是按照添加顺序排序的！！！

## \*`LinkedHashMap`\*改造 ##

*  原生的`LinkedHashMap`的确无法满足情况，但是我们稍微看下源码能够发现在put之后都会执行下`afterNodeInsertion` 这个方法。这也是`HashMap`留给`LinkedHashMap`做的扩展！

![image-20210611095540549][]

![image-20210611100631032][]

*  `removeNode` 就是将最前面的数据。想要进入这个方法就需要`removeEldestEntry`判断。`LinkedHashMap`默认是false . 所以我们只需要重写他就行了。但是还是在get值的时候如何保值在最后面呢？我们仔细看下源码就能够发现在`get`中有这个一个方法`afterNodeAccess` 。他的作用就是将get的元素移位值后面。正好符合我们`LRU`的策略特征

![image-20210611101435521][]

*  综上！我们借助`LinkedHashMap`就非常容易的实现了LRU策略！

![image-20210611101819720][]

## 自己实现 ##

*  但是本题的意思是想考察我们自己是如何实现的，而不是巧妙对现有的工具改造的！不过上面对`LinkedHashMap`的确改造的很巧这是不可否认的！下面我们就尝试自己来实现下这种方式！
 *  首先我们需要确定需要用到Hash结合链表来实现。Hash我们自然使用`HashMap`来存储数据为的就是方便定位数据。定位到数据就需要操作链表将数据实时移位值链表尾部，每次淘汰是将链表首位移除既可。为了方便我们操作链表这里的链表肯定是双链表的！

### 链表单元 ###

![image-20210611104201991][]

*  首先我们定义一个内部类！用于链表的基本单元。里面存储了key,value方便根据Hash中存储的内容找到节点！`preNode`，`nextNode`分别指向前后节点

![image-20210611105808351][]

*  在构建器中初始化容量和链表大小，并初始化边界节点方便我们操作节点中移位和删除。

![image-20210611105924364][]

*  在获取数据时没有添加就返回-1 ， 已经添加的数据则将该数据对应的node节点移动到链表的尾部。

![image-20210611110148633][]

*  在put中当第一次添加我们需要维护链表大小并进行检测是否需要进行淘汰数据，如果不是第一次添加我们只需奥更新值和对应node在链表中的位置即可

![image-20210611110255277][]

<table> 
 <thead> 
  <tr> 
   <th>方法名</th> 
   <th>作用</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>addToTail</td> 
   <td>将节点添加值链表尾部</td> 
  </tr> 
  <tr> 
   <td>moveToTail</td> 
   <td>将已经存在于链表中的节点移动到链表的尾部</td> 
  </tr> 
  <tr> 
   <td>removeHeadNode</td> 
   <td>删除链表中第一个节点，注意是边界节点后第一个节点</td> 
  </tr> 
 </tbody> 
</table>

![image-20210611110451514][]

# 四、总结 #

*  虽然执行时间和内存消耗有点高！但是我就是不优化。
 *  本题主要就是在链表的移动上面会复杂点。我们需要按照添加顺序和使用频率两个维度进行维护他们之间的顺序。只要这个顺序维护好，就没啥问题了！

[146. LRU]: https://leetcode-cn.com/problems/lru-cache/
[image-20210611091820720]: /images/20221005/e341c55fd2a4459c99cd0f780c3e72e5.png
[image-20210611091747182]: /images/20221005/6d5ce9de1363412c8b523fda046366db.png
[f6b0d894a57406aeb7d02d5d9b3c26ef.gif]: /images/20221005/45834bfd39c24cf9b7e4675f62776f18.png
[f14be693022af46db0324f027f634027.png]: /images/20221005/78810cacf7244863b4afbb803ee4464f.png
[image-20210611095540549]: /images/20221005/b7d842bb82e542b088cf7c84b0718f04.png
[image-20210611100631032]: /images/20221005/bdb7009addf241d48c895642a9f169dc.png
[image-20210611101435521]: /images/20221005/7fe5aa2058cd438aa005ccd2f4f7f2a6.png
[image-20210611101819720]: /images/20221005/5bd1de6db610420bbe8561481db0be21.png
[image-20210611104201991]: /images/20221005/96cfa37eb69b4f6db36b127178339aea.png
[image-20210611105808351]: /images/20221005/21f289fbccdd44acbdc8a7fc9c1b8d03.png
[image-20210611105924364]: /images/20221005/2f1055b527f64bedb987c9db36ced731.png
[image-20210611110148633]: /images/20221005/bb34a3ca675c4d15ba058b101fc5c4a3.png
[image-20210611110255277]: /images/20221005/cb827d4b662a49b08df2105058a165dd.png
[image-20210611110451514]: /images/20221005/41240f7ee19c4fc6883e359c0b1510f2.png