146.LRU缓存

题目描述什么是LRU?LRU 是 Least Recently Used 的缩写翻译过来就是“最近最少使用”。它是一种常用的缓存淘汰策略LRU 策略的核心思想就是如果一个数据在最近一段时间没有被访问到那么在将来它被访问的可能性也很小。 因此当空间不足时最先被淘汰踢出的就是那个最长时间没有被使用过的数据LRU 缓存的“官方开挂”解法代码classLRUCacheextendsLinkedHashMapInteger,Integer{privateintcapacity;publicLRUCache(intcapacity){//知识点1:super与this//知识点2:super(capacity,0.75F,ture)解析super(capacity,0.75F,true);this.capacitycapacity;}publicintget(intkey){returnsuper.getOrDefault(key,-1);}publicvoidput(intkey,intvalue){super.put(key,value);}Override//问题1:protected作用?这里为什么用protected?换成public或private行不行?//知识点3:removeEldestEntry(Map.EntryInteger, Integer eldest)protectedbooleanremoveEldestEntry(Map.EntryInteger,Integereldest){returnsize()capacity;}}知识点1:super与thissuper翻译过来是“超级的”但在面向对象编程的语境下它的准确称呼是“超类”Superclass也就是我们常说的“父类”this代表“我自己”指向当前对象本身this.capacity capacity; 把我自己的成员变量 capacity 赋值this.doSomething(); 调用我自己的其他方法知识点2:super(capacity,0.75F,ture)解析super(…) 调用了父类 LinkedHashMap 的构造方法capacity: 初始容量0.75F: 负载因子哈希表的常规扩容阈值保持默认的 0.75 即可0.75表示当数据量达到(capacity∗0.75capacity*0.75capacity∗0.75)时触发扩容F表示这是一个float 类型的数据F或f都可以若不加则默认是double类型数据LinkedHashMap以及它的父类 HashMap的构造函数中接收这个参数的类型是单精度浮点数float。如果直接把精度更高的 double 传给 floatJava 编译器会报错认为可能会丢失精度true: 这是最关键的参数 这个布尔值代表 accessOrder访问顺序如果传 false默认值链表会按照元素的插入顺序维护如果传 true链表就会按照元素的访问顺序维护。这就意味着只要你 get 或 put 了一个元素LinkedHashMap 就会自动把这个元素移动到双向链表的尾部代表最近使用。这完美的契合了 LRU 的需求知识点3:removeEldestEntry(Map.EntryInteger, Integer eldest)Map.Entry 指的是哈希表里的一个“键值对节点”eldest 翻译过来是“最老的”也就是那个“最久没有被访问过的数据”问题1:protected作用?这里为什么用protected?换成public或private行不行?正式题解(哈希表 双向链表)思路代码classLRUCache{// 1. 定义双向链表节点classDLinkedNode{intkey;intvalue;DLinkedNodeprev;DLinkedNodenext;publicDLinkedNode(){}publicDLinkedNode(intkey,intvalue){this.keykey;this.valuevalue;}}// 核心数据结构privateMapInteger,DLinkedNodecachenewHashMap();privateintcapacity;// 虚拟头尾节点privateDLinkedNodehead,tail;publicLRUCache(intcapacity){this.capacitycapacity;// 初始化双向链表建立虚拟头尾的连接headnewDLinkedNode();tailnewDLinkedNode();head.nexttail;tail.prevhead;}publicintget(intkey){DLinkedNodenodecache.get(key);// 如果哈希表中找不到直接返回 -1if(nodenull){return-1;}// 如果找到了不仅要返回值还要把这个节点移动到链表头部标记为最近使用moveToHead(node);returnnode.value;}publicvoidput(intkey,intvalue){DLinkedNodenodecache.get(key);if(nodenull){// 情况 A新数据// 1. 创建新节点DLinkedNodenewNodenewDLinkedNode(key,value);// 2. 添加进哈希表cache.put(key,newNode);// 3. 添加至双向链表头部addToHead(newNode);// 4. 判断是否超容if(cache.size()capacity){// 如果超容删除双向链表的尾部节点最久未使用DLinkedNodetailNoderemoveTail();// 也要把哈希表里的对应项删掉cache.remove(tailNode.key);}}else{// 情况 B数据已存在// 1. 更新值node.valuevalue;// 2. 移动到头部标记为最近使用moveToHead(node);}}// // 下面是双向链表的底层原子操作辅助函数抽离出来让逻辑更清晰// // 在虚拟头节点之后插入新节点最新使用的数据放最前面privatevoidaddToHead(DLinkedNodenode){node.prevhead;node.nexthead.next;head.next.prevnode;head.nextnode;}// 从双向链表中删除一个既有节点privatevoidremoveNode(DLinkedNodenode){node.prev.nextnode.next;node.next.prevnode.prev;}// 将一个既有节点移动到头部组合技先删除再插到头部privatevoidmoveToHead(DLinkedNodenode){removeNode(node);addToHead(node);}// 删除链表真正的尾节点最久未使用的节点并返回该节点以便哈希表同步删除privateDLinkedNoderemoveTail(){DLinkedNoderestail.prev;removeNode(res);returnres;}}复杂度分析时间复杂度对于 put 和 get 都是 O(1)空间复杂度O(capacity)因为哈希表和双向链表最多存储 capacity1 个元素