计算机的缓存容量有限，如果缓存满了就要删除⼀些内容，给新内容腾位置。但问题是，删除哪些内容呢？
我们肯定希望删掉哪些没什么⽤的缓存，⽽把有⽤的数据继续留在缓存⾥，⽅便之后继续使⽤。那么，什么样的数据，我们判定为「有⽤的」的数据呢？
LRU 缓存淘汰算法就是⼀种常⽤策略。LRU 的全称是 Least Recently Used，也就是说我们认为最近使⽤过的 数据应该是是「有⽤的」，很久都没⽤过的数据应该是⽆⽤的，内存满了就优先删那些很久没⽤过的数据。

代码

public class Node {public int key, value;public Node pre, next; //双链表 前一个和后一个public Node(int key, int value) {this.value = value;this.key = key;}}

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) {//在末尾添x.pre = tail.pre;x.next = tail;tail.pre.next = x;tail.pre = x;size++;}// remove (x)public void remove(Node x) {x.pre.next = x.next;x.next.pre = x.pre;size--;}//删除 removeFirst  size(public Node removeFirst() {if (head.next == null) {return null;}Node first = head.next;remove(first);return first;}public int size() {return size;}@Overridepublic String toString() {return "DoubleList{" +"head=" + head +", tail=" + tail +", size=" + size +'}';}
}import java.util.HashMap;public class LRUCache {private HashMap<Integer, Node> map;private DoubleList cache;private int cap;public LRUCache(int capacity) {this.cap = capacity;map = new HashMap<>();cache = new DoubleList();}public int get(int key) {//查找一个值//如果不含有 直接返回if (!map.containsKey(key)) {return -1;}//将这个值变为最近使用的makeRecently(key);//返回map里面的值return map.get(key).value;}public void put(int key, int value) {//key已经存在   修改为最近使用if (map.containsKey(key)) {deleteKey(key);addRecently(key, value);return;}if (cap == cache.size) {removeLeastRecently();}//不存在  添加keyaddRecently(key, value);//容量慢了 淘汰头节点 也就是最久没有使用的key//容量没有慢  插入key和val为最近使用的数据}//删除最久的元素public void removeLeastRecently() {Node deleteNode = cache.removeFirst();map.remove(deleteNode.key);}public void makeRecently(int key) {Node x = map.get(key);//先删除cache.remove(x);//添加cache.addLast(x);}public void addRecently(int key, int value) {Node x = new Node(key, value);cache.addLast(x);map.put(key, x);}/*** 两个地方都要删** @param key*/public void deleteKey(int key) {Node x = map.get(key);cache.remove(x);map.remove(key);}@Overridepublic String toString() {return "LRUCache{" +"map=" + map +", cache=" + cache +", cap=" + cap +'}';}
}