下面说说如何实现LRU缓存算法_0

1。LRU缓存介绍LRU算法的全称是最近最少使用算法（LeastRecentlyUse），是一种简单的缓存策略。顾名思义，LRU算法就是选择最近最少使用的数据进行淘汰。那么什么是缓存？缓存的专业点可以称之为提高数据读取性能的技术，可以有效解决内存性能和容量之间的矛盾。是一种用空间换取时间的设计思路。比如我们常见的内存就是硬盘缓存，Cache就是内存缓存。、浏览器的本地存储是网络访问的缓存……LRU有很多应用场景，比如：操作系统底层的内存管理。缓存服务，比如Redis，会在数据满的时候淘汰掉那些长时间没有使用的key。Redis中使用了类似的LRU算法，而不是严格的LRU算法。MySQL的BufferPool，又称缓冲池，是为减少磁盘IO而设计的。它是一段连续的记忆。当BufferPool满了，长时间没有被访问的页面就会被淘汰。2.Leetcode真题146.LRU缓存，请设计实现一个满足LRU（最近最少使用）缓存约束的数据结构。实现LRUCache类：LRUCache(intcapacity)初始化LRU缓存，容量为正整数capacity。intget(intkey)如果键key存在于缓存中，则返回键的值，否则返回-1。voidput(intkey,intvalue)如果关键字key已经存在，改变其数据值value；如果不存在，则将组key-value插入缓存。如果插入操作导致关键字数量超过容量，则应逐出最旧的未使用关键字。函数get和put必须以O(1)的平均时间复杂度运行。示例：输入["LRUCache","put","put","get","put","get","put","get","get","get"][[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]输出[null,null,null,1,null,-1,null,-1,3,4]解释LRUCachelRUCache=newLRUCache(2);lRUCache.put(1,1);//缓存是{1=1}lRUCache.put(2,2);//缓存是{1=1,2=2}lRUCache.get(1);//返回1lRUCache.put(3,3);//该操作会使关键字2失效，缓存为{1=1,3=3}lRUCache.get(2);//返回-1（未找到）lRUCache.put(4,4);//该操作会使关键字1失效，缓存为{4=4,3=3}lRUCache.get(1);//返回-1（未找到）lRUCache.get(3);//返回3lRUCache.get(4);//Return43.题目分析(1)首先，题目中提到get和put函数必须以平均O(1)的时间复杂度运行，所以自然而然的我们可以想到应该使用哈希表。(2)其次，访问数据结构中的某个key时，需要将key更新为最近使用过的；另外，如果容量满了，需要删除访问时间最早的数据。这就要求数据是有序的，并且可以支持在任意位置快速插入和删除元素，链表可以满足这个要求。(3)结合第1点和第2点，我们可以使用哈希表+链表的结构来实现LRU缓存。如上图所示，是哈希表+链表实现的LRU缓存数据结构。有几个问题需要说明一下：（1）为什么要用双向链表而不是单向链表？当我们找到一个结点，需要删除该结点时，如果使用单向链表，可以直接获取后续结点的指针，但是这里要求时间复杂度为O(1)，而前驱节点必须直接获取指针，那么只能使用双向链表。(2)哈希表中已经保存了key，为什么还要将key和value保存在链表中呢？仅仅存储价值还不够吗？当我们删除节点时，除了删除链表中的节点外，还需要删除哈希表中的节点。删除哈希表中的一个节点，需要知道key，所以需要将key和value存储在链表的节点中。当删除链表中的节点时，得到key，然后根据key删除hash表中的节点。（3）虚拟头节点和虚拟尾节点有什么用？链表中广泛使用虚拟节点，也称为哨兵节点，通常不存储任何数据。使用虚拟节点，我们可以统一处理链表中所有节点的插入和删除操作，而不管头尾两个节点的特殊情况。4.代码实现（1）Golangpackagemainimport"fmt"//LRU数据结构类型LRUCachestruct{capacityint//capacitysizeint//已用空间head,tail*DLinkedNode//headnode,tailnodecachemap[int]*DLinkedNode//哈希表}//双向链表数据结构类型DLinkedNodestruct{key,valueintprev,next*DLinkedNode//前指针，后指针}//创建新节点funcinitDLinkedNode(key,valueint)*DLinkedNode{return&DLinkedNode{key:key,value:value,}}//初始化LRU结构funcConstructor(capacityint)LRUCache{l:=LRUCache{cache:map[int]*DLinkedNode{},//哈希表头：initDLinkedNode(0,0),//虚拟头节点tail:initDLinkedNode(0,0),//虚拟尾节点capacity:capacity,//capacity}//虚拟头节点和虚拟尾节点的互连l.head.next=l.taill.tail.prev=l.headreturnl}//获取元素func(this*LRUCache)Get(keyint)int{//如果在哈希表中找不到键if_,ok:=this.缓存[键]；!ok{return-1}//如果key存在，先通过哈希表定位，然后移动到头节点:=this.cache[key]this.mveToHead(node)returnnode.value}//插入元素func(this*LRUCache)Put(keyint,valueint){//先去哈希表查询//如果key不存在，则新建一个节点如果节点，ok:=this.cache[key];!ok{newNode:=initDLinkedNode(key,value)//如果达到容量限制，链表删除尾节点，哈希表删除元素this.size++ifthis.size>this.capacity{//获取删除的节点removed:=this.removeTail()//根据获取的key删除哈希表中的元素delete(this.cache,removed.key)//减少使用容量this.size--}//插入哈希表this.cache[key]=newNode//插入链表this.addToHead(newNode)}else{//如果key存在，先通过哈希表定位，然后修改value，移动到theheadSectionnode.value=valuethis.moveToHead(node)}}//添加节点到headfunc(this*LRUCache)addToHead(node*DLinkedNode){//新节点指向前后节点node.prev=this.headnode.next=this.head.next//前后节点指向新节点this.head.next.prev=nodethis.head.next=node}//删除节点func(this*LRUCache)removeNode(没有de*DLinkedNode){//修改节点前后节点的指针，不再指向节点node.next.prev=node.prevnode.prev.next=node.next}//移动到头部，即删除当前位置，然后添加到头部func(this*LRUCache)moveToHead(node*DLinkedNode){this.removeNode(node)this.addToHead(node)}//移除尾节点，剔除最长未使用的func(this*LRUCache)removeTail()*DLinkedNode{node:=this.tail.prev//之前的虚拟尾节点才是真正的尾节点this.removeNode(node)returnnode}//打印链表（解决问题不需要这个方法，只是为了显示效果）func(this*LRUCache)printDLinkedNode(){p:=this.headforp!=nil{fmt.Printf("key:%d,value:%d\n",p.key,p.value)p=p.next}}funcmain(){lru:=Constructor(3)fmt.Println("============================插入3个节点=============================")lru.Put(1,100)lru.Put(2,200)lru.Put(3,300)fmt.Println("============================打印当前链表=============================)lru.printDLinkedNode()fmt.Println("=============================插入4th节点，LRU缓存淘汰尾节点============================="lru.Put(4,400)lru.printDLinkedNode()fmt.Println("============================获取key2节点，更新LRU缓存，移至链表头=============================）lru.Get(2)lru.printDLinkedNode()}(2)Javaimportjava.util.HashMap;导入java.util.Map；publicclassLRUCache{//双向链表类DLinkedNode{intkey;整数值；DLinkedNode上一个；接下来是DLinkedNode；publicDLinkedNode(){}publicDLinkedNode(intkey,intvalue){this.key=key;this.value=值；}}//哈希表privateMapcache=newHashMap<>();//已用空间privateintsize;//容量privateint容量；//头节点、尾节点privateDLinkedNodehead,tail;publicLRUCache(intcapacity){this.size=0;this.capacity=容量；//使用虚拟头部和虚拟尾部节点head=newDLinkedNode();tail=newDLinkedNode();//虚拟头节点和虚拟尾节点相互连接head.next=tail;tail.prev=head;}//获取元素publicintget(intkey){DLinkedNodenode=cache.get(key);//如果在哈希表中没有找到keyif(node==null){return-1;}//如果key存在，先通过哈希表定位，然后移动到头部moveToHead(node);返回节点值；}//插入元素publicvoidput(intkey,intvalue){DLinkedNodenode=cache.get(key);if(node==null){//如果key不存在，创建一个新节点DLinkedNodenewNode=newDLinkedNode(key,value);//如果达到容量限制，链表删除尾节点，哈希表删除元素size++；if(size>capacity){//获取删除的节点DLinkedNoderemoved=removeTail();//根据获取的key删除哈希表中的元素cache.remove(removed.key);//减少已用容量size--;}//插入哈希表cache.put(key,newNode);//添加到双链表的头部addToHead(newNode);}else{//比如如果key存在，先通过hash表定位，然后修改value，移动到head节点。value=value;moveToHead（节点）；}}//将节点加入链表头部privatevoidaddToHead(DLinkedNodenode){//新节点指向前后节点node.prev=head;node.next=head.next;//前后节点指向新节点head.next.prev=node;head.next=节点；}//删除节点privatevoidremoveNode(DLinkedNodenode){//修改节点前后节点的指针，不再指向节点node.prev.next=node.next;node.next.prev=node.prev;}//移动到头部，即删除当前位置并添加到头部privatevoidmoveToHead(DLinkedNodenode){removeNode(node);添加到头（节点）；}//移除tail节点，剔除最长未使用的privateDLinkedNoderemoveTail(){DLinkedNoderes=tail.prev;//虚拟尾节点，prev此时是真正的尾节点removeNode(res);返回资源；}//打印链表（解题不需要这个方法，只是展示效果）privatevoidprintDLinkedNode(){DLinkedNodep=this.he广告;while(p!=null){System.out.printf("key:%d,value:%d\n",p.key,p.value);p=p.下一个；}}publicstaticvoidmain(String[]args){LRUCachelru=newLRUCache(3);System.out.println("============================插入3个节点============================");lru.put(1,100);lru.put(2,200);lru.put(3,300);System.out.println("===============================打印当前链表==============================");lru.printDLinkedNode();System.out.println("============================插入第四个节点，LRU缓存淘汰尾节点key1==============================”）；lru.put(4,400);lru.printDLinkedNode();System.out.println("===========================获取key2的节点，更新LRU缓存，移动到头部链表的============================");lru.get(2);lru.printDLinkedNode();}}(3)代码运行结果如下，其中key=0，value=0的第一个和最后一个节点为虚拟节点，请忽略=============================插入3个节点============================================================打印当前链表===========================键：0，值：0键：3，值：300键：2，值：200键：1，值：100键：0,value:0=============================插入第四个节点，LRU缓存淘汰尾节点============================键：0，值：0键：4，值：400键：3，值：300键：2，值：200键：0，value:0===========================获取key2节点，更新LRU缓存，移至链表头部============================键：0，值：0键：2，值：200键：4，值：400键：3，值:300key:0,value:05.测试用例示意图步骤一：初始化数据结构。第2步：插入节点key1。第三步：插入节点key2。此时key2被插入到链表的头部。第四步：插入节点key3。此时key3被插入到链表的头部。第五步：插入节点key4。当前容量capacity达到上限（3），分为2步：使用removeTail()方法删除链表尾部的节点key1，从removeTail()方法的返回值中获取节点，然后根据node.key得到key1，然后到哈希表中删除节点key1。然后插入节点key4，此时key4在链表的头部。第六步：读取key2的值，将key2移动到链表的头部。