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); } }}
评论