前言大家好，我是bigsai，好久不见，很想你们！最近有朋友向我抱怨说他没有遇到LRU。他说他知道很早以前就有人问过他关于LRU的事情，但他认为他不会遇到他，所以暂时没有准备。不幸的是，这真的通过了考试！他此刻的心情可以用一张图来证明：他说自己好不容易磕磕绊绊写了一个LRU，效率不是很高，面试官一脸不满意……后来，他真的GG了。为了不让大家以后遇到这个坑，今天就和大家一起把这个坑给踩了。这道题一开始我用了一个比较通用的方法，但是好的方法不难，只是我想了很久。虽然不值得花太多时间，但最后还是自己想通了，把这个过程分享给大家（仅从算法的角度，不从操作系统的角度）。要理解LRU并设计LRU，你必须知道LRU是什么，对吗？LRU，英文全称LeastRecentlyUsed，翻译过来就是最近最长时间没有被使用的算法，是一种常用的页面置换算法。说到页面置换算法，这跟操作系统有很大关系。我们都知道内存的速度是比较快的，但是内存的容量是非常有限的。不可能将所有页面加载到内存中，因此需要一种策略将经常使用的页面预加载到内存中。但是，没有人知道下一次进程会访问哪块内存，我们也不能很有效地知道（我们目前没有预测未来的功能），所以一些页面替换算法只是理想化而不能现实中实现了（是的，就是最优置换算法（Optimal）），那么常见的必须返回的算法就是FIFO（先进先出）和LRU（最近未使用）。LRU不难理解，就是维护一个固定大小的容器，核心就是get()和put()这两个操作。我们先看看LRU会有两个操作：初始化：LRUCache(intcapacity)，初始化LRU缓存，容量为正整数capacity。查询：get(intkey)，从自己设计的数据结构中查找当前key是否有对应的value，如果有则返回对应的value，并记录key更新为最近一次使用，如果没有则return-1。Insert/update：put(intkey,intvalue)，可以插入一个key-value，也可以更新一个key-value，如果容器中已经存入了key-value，那么只需要更新对应的value，并标记进入最新。如果容器中不存在该值，则考虑容器是否已满。如果已满，则删除最长时间未使用的键值对。这里的过程可以给你举个例子，比如容量是2：["put","put","get","put","get","put","get","get","get"][[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]这个流程如下：容易忽略的细节是：在put()中有一个update操作，比如put(3,3)，put(3,4)会更新key为3的操作。get()可能查询不到，但是也会更新最久未使用的sequence。如果容器未满，则put可能会更新或插入，但不会删除；如果容器已满，插入put，需要考虑删除最长时间未使用的key-value。对于上面这样一条规则，我们应该如何处理呢？如果只使用类似于List的列表，可以按顺序存储键值对。List之前我们认为是比较旧的（0下标是前面），List之后我们认为是比较新的。我们考虑到各种操作可能会这样设计：如果要获取操作：逐个遍历List，看key是否有键值对，如果有键值对，则返回直接取对应键的值，如果不是则返回-1。IfPut操作：遍历List，如果key存在键值对，则果断删除该键值，最后插入该键值对。如果没有对应的key，List容器已满，果断删除第一个位置的key-value。使用List可能需要两个（一个存key，一个存value），或者一个List存Node节点（key，value是属性）。考虑这个时间复杂度：put操作：O(n)，get操作：O(n)这两个操作都需要枚举列表的线性复杂度。效率真的是有点捉襟见肘，肯定不行。我不会写这样的代码。初始Hash优化从上面的分析来看，我们可以自信的写出LRU，但是我们现在需要考虑的是一个优化的东西。如果说我们在程序中引入哈希表，那肯定会有一些优化。使用哈希表存储key-value，查询是否存在的操作可以优化到O(1)，但是删除或插入或更新位置的复杂度可能仍然是O(n)。我们一起来分析一下：最长不用的一定是一个有序的序列存储的，要么是时序表（数组），要么是链表。如果是数组实现的ArrayList，那么这个序列最长时间没有被使用过。如果是ArrayList，删除最长未使用的（第一个）key-value，命中新的key，成为最新使用的（先删除，最后插入）操作是O(n)。同理，LinkedList的大部分操作也是O(n)的，比如删除第一个元素，因为数据结构的原因是O(1)。你发现你的优化空间其实非常非常小，但是还是有进步的，但是你卡住了，不知道怎么去优化双O(1)的操作。这里我把这个版本的代码放出来，大家可以参考一下（如果面试问不可能这样写）classLRUCache{Mapmap=newHashMap<>();Listlist=newArrayList<>();int最大尺寸；publicLRUCache(intcapacity){maxSize=capacity;}publicintget(intkey){if(!map.containsKey(key))//返回-1返回-1;intval=map.get(key);put(key,val);//更新位置成为最新的很重要！返回值；}publicvoidput(intkey,intvalue){//如果key存在，直接更新即可if(map.containsKey(key)){list.remove((Integer)key);list.add(键);}else{//如果不存在，则插入到最后，但是如果容量满了，需要删除第一个（最长的）if(!map.containsKey(key)){if(list.size()==maxSize){map.remove(list.get(0));列表.删除（0）；}list.add(键);}}map.put(key,value);}}Hash+双链表我们已经知道用hash可以直接查出是否有这样一个元素，但是很难删除！使用List非常费力。更详细的说，是因为List的删除操作，Map的删除插入效率还是很高的。上面的情况，我们想要的是能够快速的删除List中的任意一个元素，效率非常高。如果我们使用hash，最多只能定位，不能删除！我们对于它可以做些什么呢？哈希+双链表！我们把key-val数据存储在一个Node类中，然后每个Node都知道左右节点，在插入链表的时候直接存储在Map中，这样Map在查询的时候可以直接返回节点，而双链表知道左右节点可以直接删除双链表中的节点。当然，为了效率，这里实现的双链表有头节点（头指针指向空节点，防止删除等异常）和尾指针。对于这种情况，你需要能够手写链表和双链表。双链表的增删改查都写的很清楚了。.qq.com/s/Cq98GmXt61-2wFj4WWezSg双链表：https://mp.weixin.qq.com/s/h6s7lXt5G3JdkBZTi01G3A即可以直接通过HashMap获取双链表中对应的Node，以及然后根据前后节点的关系进行删除，期间要考虑一些特殊情况如null、尾指针删除等。具体实现代码为：classLRUCache{classNode{intkey;整数值；节点前；下一个节点；publicNode(){}publicNode(intkey,intvalue){this.key=key;this.value=值；}}classDoubleList{privateNodehead;//头节点privateNodetail;//尾节点privateintlength;publicDoubleList(){head=newNode(-1,-1);尾=头；长度=0；}voidadd(NodeteamNode)//默认尾节点插入{tail.next=teamNode;teamNode.pre=tail；尾=团队节点；长度++；}voiddeleteFirst(){if(head.next==null)返回;if(head.next==tail)//如果要删除的恰好是tail，注意tail指针移动到了tail=head的前面；head.next=head.next.next;如果（head.next！=null）头。下一个。前=头；长度-;}voiddeleteNode(节点团队){team.pre.next=team.next;if(team.next!=null)team.next.pre=team.pre;如果（团队==tail）tail=tail.pre；team.pre=null;team.next=null；长度-;}publicStringtoString(){节点团队=head.next;StringvaString="len:"+length+"";while(team!=null){vaString+="key:"+team.key+"val:"+team.value+"";team=team.next;}返回vaString;}}Mapmap=newHashMap<>();DoubleListdoubleList;//存储顺序intmaxSize;LinkedListlist2=newLinkedList<>();publicLRUCache(intcapacity){doubleList=newDoubleList();最大尺寸=容量；}publicvoidprint(){System.out.print("maplen:"+map.keySet().size()+"");对于（整数：地图.keySet()){System.out.print("key:"+in+"val:"+map.get(in).value+"");}System.out.print("");系统输出。println("listLen:"+doubleList.length+""+doubleList.toString()+"maxSize:"+maxSize);}publicintget(intkey){intval;如果（！map.containsKey（键））返回-1；val=map.get(key).value;节点team=map.get(key);doubleList.deleteNode(团队);doubleList.add（团队）；返回值；}publicvoidput(intkey,intvalue){if(map.containsKey(key)){//已经有这个key，不管长度删除，然后更新NodedeleteNode=map.get(key);doubleList.deleteNode(deleteNode);}elseif(doubleList.length==maxSize){//不包含且长度小于Nodefirst=doubleList.head.next;map.remove(first.key);doubleList.deleteFirst();}节点节点=新节点（键，值）；双列表。添加（节点）；地图。放（键，节点）；}}这样，一个get和put就写成了复杂度为O(1)的LRU！看完最后的解决方案，发现Java中的LinkedHashMap几乎是一样的数据结构！几行就解决了，一般面试官未必会同意，还是希望大家能写一个双链表类LRUCacheextendsLinkedHashMap{privateintcapacity;publicLRUCache(intcapacity){super(capacity,0.75F,true);this.capacity=容量；}publicintget(intkey){returnsuper.getOrDefault(key,-1);}publicvoidput(intkey,intvalue){super.put(key,value);}@OverrideprotectedbooleanremoveEldestEntry(Map.Entryeldest){returnsize()>capacity;}}Hashing+DoubleLinkedList虽然没看解法就想通了，但是真的是想了半天才想到这一点。以前还真是难得一见。高效手写LRU今天真的完全掌握了！不过，除了LRU，其他的页面置换算法无论是笔试还是面试，也都非常频繁出现。有时间请自行整理。首发公众号：bigsai转载请放置作者链接和原文（本文），定期分享。欢迎注册Link，学习交流！
