1什么是LRULRU（最近最少使用）？所以LRU算法会根据数据的历史访问记录进行排序。如果空间不足，则淘汰最近最少使用的数据。2LRU实现原理由于LRU算法会增加最近使用的数据的优先级，所以需要数据结构支持排序，链表就很适合。为什么不考虑数组？由于LRU算法一般应用于访问频繁的场景，数据的移动会很频繁，而数组一旦移动，就需要改变value位置后面的所有数据的位置。效率比较低，不推荐使用。3双向链表的LinkedHashMap前面我们分析了LRU算法的实现，可以使用链表来实现。java中的LinkedHashMap是一个双向链表。LinkedHashMap是HashMap的子类。基于HashMap数据结构，它还维护了一个链接所有条目的双向链表。这个链表定义了迭代顺序，通常是插入数据的顺序。我们看一下LinkedHashMap的源码：从源码中的定义可以看出accessOrder属性可以指定遍历LinkedHashMap的顺序，true表示按照访问顺序，false表示按照插入顺序，默认为假。由于LRU对访问顺序敏感，使用true简单验证：publicclassLRUTest{publicstaticvoidmain(String[]args){LinkedHashMapmap=newLinkedHashMap<>(16,0.75f,true);map.put("a",1);map.put("b",2);map.put("c",3);System.out.println("beforeget"+map);map.get("a");System.out.println("afterget"+map);}}结果如下：beforeget{a=1,b=2,c=3}afterget{b=2,c=3,a=1}即可可见通过accessOrder=true，LinkedHashMap可以按照访问顺序进行排序。那么LinkedHashMap是怎么做到的呢？我们看get方法publicVget(Objectkey){Nodee;//获取nodeif((e=getNode(hash(key),key))==null)returnnull;//如果accessOrder=true，则执行afterNodeAccess方法if(accessOrder)afterNodeAccess(e);returne.value;}再看afterNodeAccess方法，发现正在移动节点。至此我们了解了移动节点的原理p=(LinkedHashMap.Entry)e,b=p.before,a=p.after;p.after=null;if(b==null)head=a;elseb。after=a;if(a!=null)a.before=b;elselast=b;if(last==null)head=p;else{p.before=last;last.after=p;}tail=p;++modCount;}}目前，如果使用LinkedHashMap作为LRU，有一个问题困扰着我们，那就是在容量有限的情况下如何剔除旧数据？我们回过头来看一下put方法[]tab;Nodep;intn,i;if((tab=table)==null||(n=tab.length)==0)n=(tab=resize()).length;if((p=tab[i=(n-1)&hash])==null)tab[i]=newNode(hash,key,value,null);else{Nodee;Kk;if(p.hash==hash&&((k=p.key)==key||(key!=null&&key.equals(k))))e=p;elseif(pinstanceofTreeNode)e=((TreeNode)p).putTreeVal(this,tab,hash,key,value);else{for(intbinCount=0;;++binCount){if((e=p.next)==null){p.next=newNode(hash,key,value,null);if(binCount>=TREEIFY_THRESHOLD-1)//-1for1sttreeifyBin(tab,hash);break;}if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))break;p=e;}}if(e!=null){//existingmappingforkeyVoldValue=e.value;if(!onlyIfAbsent||oldValue==null)e.value=value;afterNodeAccess(e);returnoldValue;}}++modCount;if(++size>threshold)resize();afterNodeInsertion(evict);returnull;}voidafterNodeInsertion(booleanevict){//possiblyremoveeldestLinkedHashMap.Entryfirst;if(evict&&(first=head)!=null&&removeEldestEntry(first)){Kkey=first.key;removeNode(hash(key),key,null,false,true);}}从put方法一步一步看，最后发现，如果removeEldestEntry(first)方法返回true，就会去掉头部，这样最近没有使用的数据就完全符合LRU了。4最简单的LRU实现根据上面的分析，我们可以实现最简单的LRUpublicclassLRUCacheextendsLinkedHashMap{privateintcacheSize;publicLRUCache(intcacheSize){//注意：这里需要让accessOrder=truesuper(cacheSize,0.75f,true);this.cacheSize=cacheSize;}/***判断元素个数是否超过缓存的容量需要移除*/@OverrideprotectedbooleanremoveEldestEntry(Map.Entryeldest){returnsize()>cacheSize;}}
