电邮注册网站,网站丢失怎么解决,上海的设计网站有哪些,淘宝建设网站图解LRU缓存
OJ链接
介绍
LRU 缓存机制可以通过哈希表辅以双向链表实现#xff0c;我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。 双向链表按照被使用的顺序存储了这些键值对#xff0c;靠近尾部的键值对是最近使用的#xff0c;而靠近头部的键值对是最久未…图解LRU缓存
OJ链接
介绍
LRU 缓存机制可以通过哈希表辅以双向链表实现我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。 双向链表按照被使用的顺序存储了这些键值对靠近尾部的键值对是最近使用的而靠近头部的键值对是最久未使用的。 哈希表即为普通的哈希映射HashMap通过缓存数据的键映射到其在双向链表中的位置。
这样一来我们首先使用哈希表进行定位找出缓存项在双向链表中的位置随后将其移动到双向链表的尾部即可在O(1)的时间内完成 get 或者 put 操作。 先介绍两个常用函数removeToTail(node)和add(node)removeToTail(node)是在双向链表中将使用过的node移到链表尾部add(node)是往双向链表增加一个节点。
removeToTail(node) add(node) 下面就是主要函数的介绍
get()
对于 get 操作首先判断 key 是否存在 如果 key 不存在则返回 −1 如果 key 存在则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置并将其移动到双向链表的尾部最后返回该节点的值。
put()
对于 put 操作首先判断 key 是否存在 如果 key 不存在使用 key 和 value 创建一个新的节点将 key 和该节点添加进哈希表中并在双向链表的尾部添加该节点。然后判断哈希表的节点数是否超出容量如果超出容量则删除哈希表中对应的项并删除双向链表的头部节点 如果 key 存在则与 get 操作类似先通过哈希表定位再将该节点移到双向链表的尾部并将对应的节点的值更新为 value。
复杂度分析
上述各项操作中访问哈希表的时间复杂度为 O(1)在双向链表的尾部添加节点、在双向链表的头部删除节点的复杂度也为 O(1)。
代码
import java.util.HashMap;public class $146 {class Node {int key;int value;Node prev;Node next;public Node(int key, int value) {this.key key;this.value value;}}HashMapInteger, Node hashMap new HashMap();Node head null;Node tail null;int capacity;public $146(int capacity) {this.capacity capacity;}//双向链表将节点移动到tail后面表示该节点是最近使用的public void removeToTail(Node node) {if (node tail) {} else if (node head) {tail.next node;node.prev tail;tail tail.next;head head.next;} else {node.prev.next node.next;node.next.prev node.prev;tail.next node;node.prev tail;tail tail.next;}}//双向链表增加某节点public void add(Node node) {if (tail null) {head node;tail node;} else {tail.next node;node.prev tail;tail tail.next;}}public int get(int key) {//1.哈希表不存在key返回-1if (!hashMap.containsKey(key)) {return -1;} else { //2.哈希表存在key从哈希表中获得value将key移到链表尾部int res hashMap.get(key).value;removeToTail(hashMap.get(key));return res;}}public void put(int key, int value) {//1.哈希表不存在keyif (!hashMap.containsKey(key)) {//1.1创建新节点Node node new Node(key, value);//1.2插入//插入到哈希表hashMap.put(key, node);//插入到链表add(node);//1.3判断哈希表容量if (hashMap.size() capacity) {//1.3.1删除//哈希表删除链表头元素hashMap.remove(head.key);//链表删除头元素// remove(head);head head.next;}} else { //2.哈希表存在key//2.1更新//更新链表将key移到链表尾部removeToTail(hashMap.get(key));//更新哈希表key对应的valuehashMap.get(key).value value;}}public static void main(String[] args) {$146 a new $146(4);a.put(8,80);a.put(9,90);a.put(7,70);a.put(6,60);a.get(8);a.get(7);a.put(5,50);}// //双向链表删除某节点
// public void remove(Node node) {
// // head head.next;
// if (node tail) {
// tail tail.prev;
// } else if (node head) { //均是头结点
// head head.next;
// } else {
// node.prev.next node.next;
// node.next.prev node.prev;
// }
// }
}
