双向链表+Map实现LRU

LRU:

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。

核心思想：

基于Map实现k-v存储，双向链表中使用一个虚拟头部和虚拟尾部，虚拟头部的下一个结点是链表第一个结点，虚拟尾部的前一个结点是链表最后一个结点。每次查询、新增、修改某个Key时，将key在链表中的位置移动到头部，这样尾部结点就是最近最少使用的，每次容量超限时从尾部删除。get缓存和put缓存操作的时间复杂度都为O(1)

链表结点结构：

class Node{int key;int value;Node next;Node prev;public Node(){next=null;prev=null;}public Node(int key,int value){this.key=key;this.value=value;next=null;prev=null;}}

代码：

假设缓存的kv都为int类型

public class LRUCache {class Node{int key;int value;Node next;Node prev;public Node(){next=null;prev=null;}public Node(int key,int value){this.key=key;this.value=value;next=null;prev=null;}}private int capacity;private HashMap<Integer,Node> cache=new HashMap<>();private Node head,tail;public LRUCache(int capacity) {this.capacity=capacity;head=new Node();tail=new Node();head.next=tail;tail.prev=head;}public int get(int key) {Node node= cache.get(key);if(node==null)return -1;//删除key在链表中的noderemoveNode(node);//将key在链表中的node放到队头addToHead(node);return node.value;}public void put(int key, int value) {Node node =cache.get(key);if(node!=null){//更新valuenode.value=value;//删除key在链表中的noderemoveNode(node);//将key在链表中的node放到队头addToHead(node);}else{Node newNode=new Node(key,value);cache.put(key,newNode);//将key在链表中的node放到队头addToHead(newNode);if(cache.size()>capacity){//容量超过capacityNode remo =tail.prev;cache.remove(remo.key);removeNode(remo);}}}private void removeNode(Node node){node.prev.next=node.next;node.next.prev=node.prev;}private void addToHead(Node node){node.next=head.next;node.prev=head;head.next.prev=node;head.next=node;}public static void main(String[] args) {LRUCache lRUCache = new LRUCache(2);lRUCache.put(1, 1); // 缓存是 {1=1}lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}System.out.println(lRUCache.get(1));    // 返回 1lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}System.out.println(lRUCache.get(2));    // 返回 -1 (未找到)lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}System.out.println(lRUCache.get(1));    // 返回 -1 (未找到)System.out.println(lRUCache.get(3));    // 返回 3System.out.println(lRUCache.get(4));    // 返回 4}
}

 运行结果：

注：

为什么用双向链表而不是单向链表？

在删除链表操作中，单链表要找到要删除结点的前驱结点时间复杂度就为O(n)了，而用双链表可以在O(1)复杂度上删除结点。

为什么链表节点需要同时存储 key 和 value，而不是仅仅只存储 value

（容量超限）删除缓存时，要根据node的key从Map中找到node，从而将缓存删除。