本文转载自微信公众号《小浪密码问答》，作者西门朗。转载本文请联系小浪码答公众号。背景在我们日益高效的世界中，我们非常浮躁地等待任何事情。网页无法刷新，很烦人，电脑打开运行程序很慢，很烦人！那怎么办，一代技术不就是我们服务的吗？今天我们就来聊聊缓存技术，用一个我们熟悉的数据结构——用链表来实现LRU缓存淘汰算法。在学习如何使用链表实现LRU缓存淘汰算法之前，我们先问几个问题。我们仔细想想。问题如下：什么是缓存及其作用？缓存消除策略有哪些？如何使用链表实现LRU缓存淘汰算法，有什么特点，如何优化？好了，下面我们就带着上面的问题来学习，进行下面的学习。1、什么是缓存，缓存的作用是什么？缓存可以简单理解为保存一份数据，方便以后快速访问。以电脑的使用场景为例。当CPU要访问内存中的一段数据时，会先到缓存中查找。如果它能找到它，它将直接使用它。在接入场景下，当项目系统需要查询数据库中的一条数据时，可以先提出查询缓存的请求。如果命中，则直接返回缓存的结果。如果没有命中，则查询数据库，并将查询结果放入缓存，查询缓存在下次请求命中，直接返回结果，不需要再次查询数据库。通过上面两个例子，我们发现无论在哪种场景下，都有这样一个顺序：先缓存，后内存；先缓存，后数据库。但是缓存的存在也占用了一部分内存空间，所以缓存是典型的以空间换时间，牺牲了数据的实时性，却满足了计算机运行的效率。仔细想想，我们日常开发中遇到的缓存的例子还是不少的。操作系统的缓存减少了与磁盘的交互。数据库缓存减少了对数据库的查询。Web服务器缓存减少了对应用程序服务器的请求。客户端浏览器缓存减少了对网站的访问。2、缓存的淘汰策略有哪些？时间的话，缓存的容量肯定是有限的。当缓存满了，缓存中哪些数据应该清空，哪些数据应该保留？这需要一个缓存淘汰策略来决定。其实常用的缓存淘汰策略有3种：先进先出算法（FirstinFirstoutFIFO）；剔除一定时间内访问次数最少的页面（LeastFrequentlyUsedLFU）；最长时间未使用页面淘汰（LeastRecentlyUsedLRU）这些算法在不同级别的缓存上执行时效率不同，需要结合具体场景进行选择。2.1FIFO算法FIFO算法是一种先进先出的算法，通常用队列来实现。在缓存中，它的设计原则是：如果一条数据先进入缓存，就应该先淘汰。FIFO算法新访问的数据被插入到FIFO队列的尾部，队列中的数据依次从队列移动到队列头部。当队列满时，删除队列头部的数据。2.2LRU算法LRU算法根据历史访问数据的次数来剔除数据，通常使用链表实现。在缓存中，它的设计原则是，如果最近访问过数据，则将来访问它的机会也很高。LRU算法新增的数据插入到链表的头部。每当缓存命中（即缓存数据被访问），数据就被移到链表的头部。当链表满时，链表尾部的数据被丢弃。2.3LFU算法LFU算法根据数据的历史访问频率来剔除数据。因此，LFU算法中的每个数据块都有一个引用计数。所有数据块按引用计数排序，引用计数相同的数据块按时间排序。在缓存中，它的设计原则是如果数据被多次访问，那么以后访问的频率就会更高。LFU算法新增数据插入队列尾部（引用计数为1；访问队列中数据后，引用计数增加，对队列重新排序；需要淘汰数据时，sortedlist的最后一个数据块被删除3.如何使用链表实现缓存淘汰，它有什么特点，如何优化？在上面的文章中，我们了解了缓存的概念和淘汰策略.其中LRU算法在笔试/面试中被考察的比较频繁，我秋招的时候，很多公司让我手写这个算法，为了避免坑，我们会手写一个LRU缓存淘汰算法。都知道链表的形式不止一种，我们应该选择哪一种呢？思考三分钟…………好吧，公布答案！其实链表可以分为单向链表，循环链表链表和双linkedlists根据不同的连接结构。单向链表的每个节点只包含一个指针，即后继指针。单向链表有两个特殊节点，即首节点和尾节点。第一个节点的地址用来表示整个链表，尾节点的后继指针指向空地址null。性能特点：插入和删除节点的时间复杂度为O(1)，查找的时间复杂度为O(n)。循环链表与单向链表一致，只是尾节点的后继指针指向首节点的地址。适合存储具有循环特性的数据，比如约瑟夫问题。双向链表节点除了存储数据外，还有两个指针分别指向前一个节点地址（precursorpointerprev）和下一个节点地址（successorpointernext）。首节点的前驱指针prev和尾节点的后继指针都指向空地址。双向链表相对于单链表的一大优势是寻找前驱节点的时间复杂度为O(1)，而单链表只能从头节点开始慢慢寻找，所以还是O(n).而且，对于插入和删除也进行了优化。我们可能会有疑问：单向链表的插入和删除不就是O(1)吗？是的，但是一般情况下，如果我们要进行插入和删除操作，还是要先查找，再插入或删除。可以看出其实是先O(n)，再O(1)。因为我们要删除一个节点，删除一个节点不仅需要获取节点本身的指针，还需要操作其他前驱节点的指针，而双向链表可以直接找到前驱，保证了运算时间复杂度为O(1)，所以使用双向链表作为实现LRU缓存淘汰算法的结构效率更高。算法思想是维护一个双向链表，保存所有缓存的值，把最早的值放在链表的末尾。当访问的值在链表中时：找到链表中的值并删除，重新添加链表头部的值（保证链表中值的顺序listisfromnewtoold)当访问的值不在链表中时：当链表已经Full时：删除链表的最后一个值，并将要添加的值放在链表的头部当链表未满：直接在链表头部添加LRU缓存淘汰算法，代码如下：publicclassLRUBaseLinkedList{/***defaultlinkedlistcapacity*/privatefinalstaticIntegerDEFAULT_CAPACITY=10;/***头节点*/privateSNodeheadNode;/***链表长度*/privateIntegerlength;/***链表容量*/privateIntegercapacity;publicLRUBaseLinkedList(){this.headNode=newSNode<>();this.capacity=DEFAULT_CAPACITY;this.length=0;}publicLRUBaseLinkedList(Integercapacity){this.headNode=newSNode<>();this.capacity=capacity;this.length=0;}publicvoidadd(Tdata){SNodepreNode=findPreNode(data);//存在于链表中，删除原来的数据，然后插入链表头部if(preNode!=null){deleteElemOptim(preNode);intsertElemAtBegin(data);}else{if(length>=this.capacity){//删除结束节点deleteElemAtEnd();}intsertElemAtBegin(data);}}/***删除preNode节点下一个元素**@parampreNode*/privatevoiddeleteElemOptim(SNodepreNode){SNodetemp=preNode.getNext();preNode.setNext(temp.getNext());temp=null;length--;}/***在链表头部插入节点**@paramdata*/privatevoidintsertElemAtBegin(Tdata){SNodeext=headNode.getNext();headNode.setNext(newSNode(data,next));length++;}/***Get查找元素的前一个节点**@paramdata*@return*/privateSNodefindPreNode(Tdata){SNodenode=headNode;while(node.getNext()!=null){if(data.equals(node.getNext().getElement())){returnnode;}node=node.getNext();}returnnull;}/***删除尾节点*/privatevoiddeleteElemAtEnd(){SNodeptr=headNode;//空链表如果直接返回(ptr.getNext()==null){return;}//倒数第二个节点while(ptr.getNext().getNext()!=null){ptr=ptr.getNext();}SNodetmp=ptr.getNext();ptr.setNext(null);tmp=null;length--;}privatevoidprintAll(){SNodenode=headNode.getNext();while(node!=null){System.out.print(node.getElement()+",");node=node.getNext();}System.out.println();}publicclassSNode{privateTelement;privateSNodeext;publicSNode(Telement){this.element=element;}publicSNode(Telement,SNodeext){this.element=元素;this.next=next;}publicSNode(){this.next=null;}publicTgetElement(){returnelement;}publicvoidsetElement(Telement){this.element=element;}publicSNodegetNext(){returnext;}publicvoidsetNext(SNodeext){this.next=next;}}publicstaticvoidmain(String[]args){LRUBaseLinkedListlist=newLRUBaseLinkedList();Scannersc=newScanner(System.in);while(true){list.add(sc.nextInt());list.printAll();}}}这段代码无论缓存是否满，都需要遍历链表，所以这是一个基于链表的实现思路，缓存访问的时间复杂度为O(n)3.2使用哈希表优化LRU其实这个思路还可以进一步优化，我们可以将单链表换成双链表，引入哈希表。双向链表支持查找前驱，确保操作的时间复杂度为O(1)。引入哈希表记录每条数据的位置，将访问缓存的时间复杂度降低到O(1)。哈希表搜索速度更快，但数据不可用。固定顺序；链表有顺序。插入和删除速度更快，但查找速度更慢。将它们结合起来，可以形成一个新的数据结构——哈希链表（LinkedHashMap）哈希表+双向链表。146题-LRU缓存机制可以用来练习。题图如下：题目：利用你掌握的数据结构，设计并实现一个LRU（最近最少使用）缓存机制。实现LRUCache类：LRUCache(intcapacity)使用正整数作为初始化LRU缓存的容量intget(intkey)如果缓存中存在关键字key，则返回key的值，否则返回-1。voidput(intkey,intvalue)如果关键字已经存在，改变它的数据值；如果关键字不存在，则插入“keyword-value”的集合。当缓存容量达到上限时，它应该在写入新数据之前删除最旧的未使用数据值，从而为新数据值腾出空间。思路：我们的思路是哈希表+双向链表哈希表是为了满足题目的时间复杂度O(1)的要求，双向链表是用来存储顺序的哈希表key值类型：在doubly的节点中linkedlist除了value还需要包含key，因为在删除最长时间没有被使用的数据时，需要通过链表在hashmap中定位到应该删除的key-value对。最后addNodeToLast(node)如果容量达到上限则移除最长未使用的数据，removeNode(head.next)如果数据是新访问的，比如被get或放一个新值，moveNodeToLast(node)为了操作方便，在双向链表的头尾分别定义了一个头节点和一个尾节点。代码classLRUCache{privateintcapacity;privateHashMaphashmap;privateListNodehead;privateListNodetail;privateclassListNode{intkey;intval;ListNodeprev;ListNodeext;publicListNode(){}publicListNode(intkey,intval){this.key=key;this.val=val;}}publicLRUCache(intcapacity){this.capacity=capacity;hashmap=newHashMap<>();head=newListNode();tail=newListNode();head.next=tail;tail.prev=head;}??privatevoidremoveNode(ListNodenode){node.prev.next=node.next;node.next.prev=node.prev;}privatevoidaddNodeToLast(ListNodenode){node.prev=tail.prev;node.prev.next=node;node.next=tail;tail.prev=node;}privatevoidmoveNodeToLast(ListNodenode){removeNode(node);addNodeToLast(node);}publicintget(intkey){if(hashmap.containsKey(key)){ListNodenode=hashmap.get(key);moveNodeToLast(node);returnnode.val;}else{return-1;}}publicvoidput(intkey,intvalue){if(hashmap.containsKey(key)){ListNodenode=hashmap.get(key);node.val=value;moveNodeToLast(node);返回;}如果(哈希图。size()==capacity){hashmap.remove(head.next.key);removeNode(head.next);}ListNodenode=newListNode(key,value);hashmap.put(key,node);addNodeToLast(node);}}巨人的肩膀：[1]数据结构与算法之美-王征[2]力口-LRU缓存机制（146题）[3]https://blog.csdn.net/yangpl_tale/article/详情/44998423[4]https://leetcode-cn.com/problems/lru-cache/solution/146-lru-huan-cun-ji-zhi-ha-xi-biao-shuan-l3um/
