建网站做淘宝客可以吗,大型网站 开发语言,升级不了wordpress,皮肤自做头像的网站LRU:
LRU是Least Recently Used的缩写#xff0c;即最近最少使用#xff0c;是一种常用的页面置换算法#xff0c;选择最近最久未使用的页面予以淘汰。
核心思想#xff1a;
基于Map实现k-v存储#xff0c;双向链表中使用一个虚拟头部和虚拟尾部#xff0c;虚拟头部的…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(){nextnull;prevnull;}public Node(int key,int value){this.keykey;this.valuevalue;nextnull;prevnull;}}
代码
假设缓存的kv都为int类型
public class LRUCache {class Node{int key;int value;Node next;Node prev;public Node(){nextnull;prevnull;}public Node(int key,int value){this.keykey;this.valuevalue;nextnull;prevnull;}}private int capacity;private HashMapInteger,Node cachenew HashMap();private Node head,tail;public LRUCache(int capacity) {this.capacitycapacity;headnew Node();tailnew Node();head.nexttail;tail.prevhead;}public int get(int key) {Node node cache.get(key);if(nodenull)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.valuevalue;//删除key在链表中的noderemoveNode(node);//将key在链表中的node放到队头addToHead(node);}else{Node newNodenew 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.nextnode.next;node.next.prevnode.prev;}private void addToHead(Node node){node.nexthead.next;node.prevhead;head.next.prevnode;head.nextnode;}public static void main(String[] args) {LRUCache lRUCache new LRUCache(2);lRUCache.put(1, 1); // 缓存是 {11}lRUCache.put(2, 2); // 缓存是 {11, 22}System.out.println(lRUCache.get(1)); // 返回 1lRUCache.put(3, 3); // 该操作会使得关键字 2 作废缓存是 {11, 33}System.out.println(lRUCache.get(2)); // 返回 -1 (未找到)lRUCache.put(4, 4); // 该操作会使得关键字 1 作废缓存是 {44, 33}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从而将缓存删除。
