0。初步总结面试官：你会手写一个LRU缓存吗？你：什么是LRU？(疑惑)面试官：LRU的全称是LeastRecentlyUsed（最近最少使用），用来剔除不经常使用的数据，保留热点数据。你写了5分钟，但是你只写了一个get和put的方法体，你真的不知道里面的逻辑怎么写。面试官：今天的面试先过来，有其他面试的时候再联系你。我信你是鬼，你是坏老头，你很坏，怎么还联系我，爽。别着急，如果有人再问你LRU，直接把这篇文章扔给他，并保证当场发offer。1、实现思路的目的是剔除最不常用的数据，所以需要记录每个元素的访问次数。最简单的方法是按使用情况、最近使用情况对所有元素进行排序，然后移至末尾。当缓存已满时，它会从标头中删除。2.使用哪种数据结构实现？常用的数据结构包括数组、链表、栈和队列。考虑到需要从两端操作元素，不能使用栈和队列。每次使用一个元素，都要将该元素移动到末尾，包括一次删除和一次添加操作。使用数组会涉及到大量的拷贝操作，不适合。考虑到删除一个元素，使用双链接将这个元素的前一个节点指向下一个节点是最合适的。链表不适合查询，因为每次都需要遍历所有元素，可以和HashMap结合使用。双链表+HashMap3。代码实现importjava.util.HashMap;importjava.util.Map;/***@authoryideng*/publicclassLRUCache{/***双链表元素节点*/privateclassEntry{Entry之前；条目之后；私钥；私有V值；}/***缓存容量*/privateIntegercapacity;/***头节点*/privateEntryhead;/***尾节点*/privateEntrytail;/***用于存储所有元素*/privateMap>caches=newHashMap<>();publicLRUCache(intcapacity){this.capacity=capacity;}publicVget(Kkey){finalEntrynode=caches.get(key);if(node!=null){//如果有访问，则移动到链表的末尾afterNodeAccess(node);返回节点值；}返回空值；}/***将元素移动到末尾*/privatevoidafterNodeAccess(Entrye){Entrylast=tail;//如果e不是尾节点，则需要移动null){head=e.after;}else{e.before.after=e.after;}//删除本节点与下一个节点的连接if(e.after==null){last=e.before;}else{e.after.before=e.before;}//添加节点到尾节点判断尾节点是否为空if(last==null){head=e;}else{e.before=last;last.after=e;}e.after=null;尾巴=e；}}publicVput(Kkey,Vvalue){Entryentry=caches.get(key);if(entry==null){entry=newEntry<>();entry.key=键；entry.value=值；//新节点添加到末尾linkNodeLast(ent里）；caches.put（键，条目）；//如果节点数大于容量，删除头节点if(this.caches.size()>this.capacity){this.caches.remove(head.key);节点移除后（头）；}返回空值；}entry.value=值；//如果节点有更新，会移动到非节点afterNodeAccess(entry);caches.put（键，条目）；返回条目。值；}/***把这个节点添加到尾节点*/privatevoidlinkNodeLast(Entrye){finalEntrylast=this.tail;如果(head==null){head=e;}else{e.before=last;last.after=e;}尾=e;}/***移除节点*/voidafterNodeRemoval(Entrye){if(e.before==null){head=e.after;}else{e.before.after=e.after;}if(e.after==null){tail=e.before;}别的{e.after.before=e.before;}}}4。其实还有更简单的实现importjava.util.LinkedHashMap;importjava.util.Map;/***@authoryideng*/publicclassLRUCacheextendsLinkedHashMap{//maximum容量privatefinalintmaximumSize；publicLRUCache(finalintmaximumSize){//true表示按访问顺序排序，false表示按插入顺序排序super(maximumSize,0.75f,true);this.maximumSize=maximumSize;}/***当节点数大于最大容量时，删除最旧的元素*/@OverrideprotectedbooleanremoveEldestEntry(finalMap.Entryoldest){returnsize()>this.maximumSize;}}
