南山网站制作,如何免费制作二维码,品牌营销传播,网站ssl证书怎么做设计LRU(最近最少使用)缓存结构#xff0c;该结构在构造时确定大小#xff0c;假设大小为K#xff0c;并有如下两个功能
put(key, value)#xff1a;将记录(key, value)插入该结构get(key)#xff1a;返回key对应的value值
对于put(key, value)来说#xff0c;我们需要…设计LRU(最近最少使用)缓存结构该结构在构造时确定大小假设大小为K并有如下两个功能
put(key, value)将记录(key, value)插入该结构get(key)返回key对应的value值
对于put(key, value)来说我们需要考虑两部分
如果缓存中存在那么直接将缓存中对应的元素移动到缓存头部如果缓存中不存在那么把元素添加到缓存头部如果此时缓存的大小超出了预先设定的值那么则将缓存尾部的元素删除
对于get(key)来说我们还是需要考虑两部分
如果缓存中存在那么返回该值并且将这个值移动到缓存头部如果缓存中不存在那么返回-1
综上所述对于一个LRU缓存来说主要包含以下三种操作。
查找一个元素。在缓存末尾删除一个元素。在缓存头部添加一个元素。
所以我们最容易想到的实现方式就是通过双端链表哈希表来实现这个问题最终实现代码如下
class LRUCache {private HashMapInteger,ListNode cache;private int capacity;private ListNode head,tail;class ListNode{int key;int value;ListNode prev;ListNode next;public ListNode(){}public ListNode(int key,int value){this.keykey;this.valuevalue;}}public LRUCache(int capacity) {this.capacity capacity;cache new HashMap();head new ListNode();tail new ListNode();head.next tail;tail.prev head;}public int get(int key) {//首先判断一下是否存在keyListNode node cache.get(key);if(nodenull){return -1;}//如果存在把缓存移动到头部返回valuemoveToHead(node);return node.value;}public void put(int key, int value) {//判断是否存在ListNode node cache.get(key);//如果不存在添加到头部,如果容量到达上限则删除队尾的元素,如果存在直接移动到头部if(nodenull){ListNode newNode new ListNode(key,value);cache.put(key,newNode);addNode(newNode);if(cache.size()capacity){ListNode last popTail();cache.remove(last.key);}}else{node.valuevalue;moveToHead(node);}}public void addNode(ListNode node){node.prev head;node.next head.next;head.next.prev node;head.next node;}public void removeNode(ListNode node){ListNode prevNode node.prev;ListNode NextNode node.next;prevNode.next NextNode;NextNode.prev prevNode;}public void moveToHead(ListNode node){removeNode(node);addNode(node);}public ListNode popTail(){ListNode lastNode tail.prev;removeNode(lastNode);return lastNode;}
}
