数据缓存历险记（五）--LRU缓存算法的最终篇
LRU要被按在地上摩擦了
数据在经过上次LRU大师兄的专业解读， 很清晰的明白了LRU(最近最少淘汰算法)的底层，需要有顺序和查询插入数据去支持做出操作，而且要比较高效的进行数据的筛选，虽然大师兄LRU的武功很强， 数据心里也是强忍着一口气，非得让老头把看家的底层本领教教他，这不，又开始试探LRU底层的逻辑了；
虽然 可以用java集合中的LinkedHashMap来整理个容器，做出合格的LRU的实现，但是底层还是封装了很多东西。所以数据感觉要自己来搞定
开始干活。。
LRU底层实现：
其中HASHMAP是保证键值对，查找，双向链表保证，键值对的队列中的位置；
对于自己手动写出一个LRU的算法，需要确定两点：
为什么需要一个节点Node作为一个数据载体呢？
我们来用hashmap这个集合容器的底层实现做类比：它的底层存储是put方法；依次是
确定好可以作为数据载体，我们需要创建 node节点数据；
创建出一个双向的队列，保证顺序；
进过删除，添加表头的操作进行调整顺序，使得每次进入的数据都可以动态的调整；真正做到顺序的有效淘汰；
我们最后做的结构就是在双端的队列中，创建出一个集合map
创建一个Node节点存储数据
//创建存储节点类，类似于节点node的数据载体，存储键值对
class Node {
k keys;
v values;
Node prev; //前指针
Node 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;
}
}
创建一个双向的队列
class DoubleLinkedList {
Node head;
Node tail;
//双端队列的构造方法
public DoubleLinkedList() {
this.head = new Node();
this.tail = new Node();
//头节点的下一个是尾节点，尾节点的前一个是头节点
head.next = tail;
tail.prev = head;
}
添加表头
//添加到表头
public void addHeader(Node 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 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;
}
代码实现：
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 keys;
v values;
Node prev; //前指针
Node 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 {
Node head;
Node tail;
//双端队列的构造方法
public DoubleLinkedList() {
this.head = new Node();
this.tail = new Node();
//头节点的下一个是尾节点，尾节点的前一个是头节点
head.next = tail;
tail.prev = head;
}
//添加到表头
public void addHeader(Node 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 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> dateMap;
DoubleLinkedList 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 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 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);
}
}
}
代码测试：
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]
*/
}
卢卡总结：
经过代码测试。可以实现淘汰LRU机制的效果，其中对于插入顺序，和节点node的删除和添加，细节中，要注意， 根据步骤完成具体实现；
LRU数据缓存历险记就告一段落了，希望这次数据的历险记可以帮助到你获取不一样的缓存视角，记得点赞哦，晚安；