LRU缓存算法设计

LRU 缓存算法的核⼼数据结构就是哈希链表，双向链表和哈希表的结合体。这个数据结构⻓这样：
在这里插入图片描述
创建的需要有两个方法，一个是get方法，一个是put方法。

在这里插入图片描述

一些问题：为什么需要使用双向链表呢？因为删除链表的本身，需要得到他的前一个节点。如果使用单链表，效率就会很低，这边是使用的空间换取效率。

//Node 节点类
public class Node {public  int key,val;public Node pre,next;public Node(int key,int val){this.key=key;this.val=val;}}

public class DoubleList {//头和尾public   Node head,tail;public int size;public DoubleList(){//两个哨兵head=new Node(0,0);tail=new Node(0,0);head.next=tail;tail.pre=head;size=0;}public  void addLast(Node x){//添加到末尾去//在tail之前插入一个 x.pre=tail.pre; //x.next=tail;tail.pre.next=x;tail.pre=x;size++;}public void remove(Node x) {//双链表删除一个节点  x.pre.next=x.next;x.pre.next = x.next;x.next.pre = x.pre;size--;}// 删除链表中第⼀个节点，并返回该节点，时间 O(1)public Node removeFirst() {if (head.next == tail)return null;Node first = head.next;remove(first);return first;}public int size() { return size; }
}

缓存设计的代码:


import java.util.HashMap;public class LRUCache {// key -> Node(key, val)private HashMap<Integer, Node> map;// Node(k1, v1) <-> Node(k2, v2)...private DoubleList cache;// 最⼤容量private int cap; //最大容量public LRUCache(int capacity) {this.cap = capacity;map = new HashMap<>();cache = new DoubleList();}private void makeRecently(int key) {Node x = map.get(key); //变为最近的    删除 然后添加进来// 先从链表中删除这个节点cache.remove(x);// 重新插到队尾cache.addLast(x);}private void addRecently(int key, int val) {Node x = new Node(key, val);// 链表尾部就是最近使⽤的元素cache.addLast(x);// 别忘了在 map 中添加 key 的映射map.put(key, x);}private void deleteKey(int key) {Node x = map.get(key);// 从链表中删除cache.remove(x);// 从 map 中删除map.remove(key);  //mp中也要删除}private void removeLeastRecently() {  //删除最久没有使用的// 链表头部的第⼀个元素就是最久未使⽤的Node deletedNode = cache.removeFirst();// 同时别忘了从 map 中删除它的 keyint deletedKey = deletedNode.key;map.remove(deletedKey);}public int get(int key) {if (!map.containsKey(key)) {return -1;}// 将该数据提升为最近使⽤的makeRecently(key); //修改return map.get(key).val;}public void put(int key, int val) {//如果之前含有  删除 并添加if (map.containsKey(key)) {// 删除旧的数据deleteKey(key);// 新插⼊的数据为最近使⽤的数据addRecently(key, val);return;}//如果慢了 那么删除if (cap == cache.size()) {// 删除最久未使⽤的元素removeLeastRecently();}// 添加为最近使⽤的元素addRecently(key, val);}
}