缓存数据的淘汰之路（下）
作者：卢卡多多
- 2021 年 12 月 09 日
本文字数：4314 字
阅读完需：约 14 分钟
背景
数据在经过上次 LRU 大师兄的专业解读， 很清晰的明白了 LRU(最近最少淘汰算法)的底层，需要有顺序和查询插入数据去支持做出操作，而且要比较高效的进行数据的筛选，虽然大师兄 LRU 的武功很强， 数据心里也是强忍着一口气，非得让老头把看家的底层本领教教他，这不，又开始试探 LRU 底层的逻辑了；
虽然 可以用 java 集合中的 LinkedHashMap 来整理个容器，做出合格的 LRU 的实现，但是底层还是封装了很多东西。所以数据感觉要自己来搞定
开始干活。。
LRU 底层实现：
其中 HASHMAP 是保证键值对，查找，双向链表保证，键值对的队列中的位置；
1.对于自己手动写出一个 LRU 的算法，需要确定两点：
需要一个节点 NODE，确定前后指针，保证顺序
Map,作为节点数据的存储集合，做到查询和插入
2.为什么需要一个节点 Node 作为一个数据载体呢？
我们来用 hashmap 这个集合容器的底层实现做类比：它的底层存储是 put 方法；依次是
确定好可以作为数据载体，我们需要创建 node 节点数据；
创建出一个双向的队列，保证顺序；
进过删除，添加表头的操作进行调整顺序，使得每次进入的数据都可以动态的调整；真正做到顺序的有效淘汰；
我们最后做的结构就是在双端的队列中，创建出一个集合 map
3.创建一个 Node 节点存储数据
//创建存储节点类，类似于节点node的数据载体，存储键值对
class Node<k, v> { k keys; v values; Node<k, v> prev; //前指针 Node<k, v> next; //后指针
public Node() { this.prev = null; this.next = null; }
//初始化指针 public Node(k keys, v values) { this.keys = keys; this.values = values; this.prev = this.next = null; } }
复制代码
4.创建一个双向的队列
class DoubleLinkedList<k, v> {
Node<k, v> head; Node<k, v> tail;
//双端队列的构造方法 public DoubleLinkedList() { this.head = new Node<k, v>(); this.tail = new Node<k, v>(); //头节点的下一个是尾节点，尾节点的前一个是头节点 head.next = tail; tail.prev = head; }
复制代码
添加表头
//添加到表头 public void addHeader(Node<k, v> node) {
/** * 将node放入表头 * 当前节点node的前节点-是当前节点(一个节点进入之后，新节点的下一个节点，head的下一个的位置) * 当前节点的前一个节点是头节点 */ node.next = head.next; node.prev = head;
/** * 头节点的下一个是尾节点，尾节点的前一个是node * 头节点的下一个是当前节点 */ head.next.prev = node; head.next = node;
}
复制代码
删除操作
//3删除node节点 public void removeNode(Node<k, v> node) {
/** * 删除当前节点 * 节点node的下一个节点是tail,之前节点，（删除前此节点的前一个节点） * 节点node的前一个节点head，之后的节点tail(删除前此节点的下一个节点) */ node.next.prev = node.prev; //head node.prev.next = node.next;
node.prev = null; node.next = null;
} //获取尾节点数据 public Node getLast() { return tail.prev; }
复制代码
5.代码实现：
package com.lru;
import java.util.HashMap;import java.util.Map;
/** * @author lucas * @create 2021-08-11 20:14 * @description 手写lru算法的实现 */public class LRUCache {
//创建存储节点类，类似于节点node的数据载体，存储键值对
class Node<k, v> { k keys; v values; Node<k, v> prev; //前指针 Node<k, v> next; //后指针
public Node() { this.prev = null; this.next = null; }
//初始化指针 public Node(k keys, v values) { this.keys = keys; this.values = values; this.prev = this.next = null; } }
//2.创建一个双向的队列，存储一个个node节点，组成一个数据结构
class DoubleLinkedList<k, v> {
Node<k, v> head; Node<k, v> tail;
//双端队列的构造方法 public DoubleLinkedList() { this.head = new Node<k, v>(); this.tail = new Node<k, v>(); //头节点的下一个是尾节点，尾节点的前一个是头节点 head.next = tail; tail.prev = head; }
//添加到表头 public void addHeader(Node<k, v> node) {
/** * 将node放入表头 * 当前节点node的前节点-是当前节点(一个节点进入之后，新节点的下一个节点，head的下一个的位置) * 当前节点的前一个节点是头节点 */ node.next = head.next; node.prev = head;
/** * 头节点的下一个是尾节点，尾节点的前一个是node * 头节点的下一个是当前节点 */ head.next.prev = node; head.next = node;
}
//3删除node节点 public void removeNode(Node<k, v> node) {
/** * 删除当前节点 * 节点node的下一个节点是tail,之前节点，（删除前此节点的前一个节点） * 节点node的前一个节点head，之后的节点tail(删除前此节点的下一个节点) */ node.next.prev = node.prev; //head node.prev.next = node.next;
node.prev = null; node.next = null;
}
//获取尾节点数据 public Node getLast() { return tail.prev; }
}
private int cacheSize;
Map<Integer, Node<Integer, Integer>> dateMap;
DoubleLinkedList<Integer, Integer> doubleLinkedList;
//构造方法 public LRUCache(int cacheSize) { this.cacheSize = cacheSize; //查找 dateMap = new HashMap<>(); //排序，交换位置 doubleLinkedList = new DoubleLinkedList<>(); }
//缓存获取value值
public int get(int key) {
/** * 1.从map中取出数据，交换位置到表头，然后返回 * 2.取不到返回-1/ */ if (!dateMap.containsKey(key)) { return -1; } Node<Integer, Integer> dataNode = dateMap.get(key);
/** * 将队列中顺序，删除之前的位置node，添加到表头 */ doubleLinkedList.removeNode(dataNode); //将node添加到表头 doubleLinkedList.addHeader(dataNode);
return dataNode.values; }
//写操作或者是更新操作key public void put(int key, int value) {
/** * 三种情况： * 1.如果key存在，就更新操作 * 2.key不存在， 新增节点信息 * */
if (dateMap.containsKey(key)) { //更新节点的信息数据 Node<Integer, Integer> node = dateMap.get(key); node.values = value; dateMap.put(key, node); //加入队列表头 doubleLinkedList.removeNode(node); doubleLinkedList.addHeader(node);
} else { //是否达到最大容量了 if (dateMap.size() == cacheSize) {
Node lastNode = doubleLinkedList.getLast();
//获取到最末尾的节点数据，然后剔除map集合，剔除队列 dateMap.remove(lastNode.keys); doubleLinkedList.removeNode(lastNode); } /** * 新增操作 */ //重新加入node Node dateNode = new Node(key, value); dateMap.put(key, dateNode); //加入队列表头 doubleLinkedList.addHeader(dateNode); } }}
复制代码
6.代码测试：
public static void main(String[] args) { LRUCache lruCacheDemo = new LRUCache(3);
lruCacheDemo.put(1, 1); lruCacheDemo.put(2, 1); lruCacheDemo.put(3, 1); System.out.println(lruCacheDemo.dateMap.keySet()); lruCacheDemo.put(4, 1); System.out.println("增加第四个后，列表是"+lruCacheDemo.dateMap.keySet());
System.out.println("--------------------------------------------"); lruCacheDemo.put(3, 1); System.out.println(lruCacheDemo.dateMap.keySet()); lruCacheDemo.put(3, 1); System.out.println(lruCacheDemo.dateMap.keySet()); lruCacheDemo.put(3, 1); System.out.println(lruCacheDemo.dateMap.keySet());
System.out.println("--------------------------------------------"); lruCacheDemo.put(5, 1); System.out.println(lruCacheDemo.dateMap.keySet());
/** * [1, 2, 3] * 增加第四个后，列表是[2, 3, 4] * -------------------------------------------- * [2, 3, 4] * [2, 3, 4] * [2, 3, 4] * -------------------------------------------- * [3, 4, 5] */ }
复制代码
7.卢卡总结：
经过代码测试。可以实现淘汰 LRU 机制的效果，其中对于插入顺序，和节点 node 的删除和添加，细节中，要注意， 根据步骤完成具体实现；
LRU 数据缓存历险记就告一段落了，希望这次数据的历险记可以帮助到你获取不一样的缓存视角，记得点赞哦
划线
评论
复制
发布于: 5 小时前阅读数: 7
版权声明: 本文为 InfoQ 作者【卢卡多多】的原创文章。
原文链接:【http://xie.infoq.cn/article/9b9030b1b460a3b4ad3968f57】。文章转载请联系作者。
卢卡多多
关注
努力寻找生活答案的旅途者 2020.04.12 加入
公众号：卢卡多多，欢迎一起交流学习
评论