如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。
所以顾名思义，LRU算法会选出最近最少使用的数据进行淘汰。
当数据的总量达到上限后，则移除容器中优先级最低的数据。下图是一个简单的LRU原理示意图：
如果我们按照70120304的顺序来访问数据，且数据的总量上限为3，则如上图所示，LRU算法会依次淘汰712这三个数据。
那么我们现在就按照上面的原理，实现一个朴素的LRU算法。下面有三种方案：
下面我们就基于双向链表和哈希表实现一个LRU算法
其实我们可以直接根据JDK给我们提供的LinkedHashMap直接实现LRU。因为LinkedHashMap的底层即为双向链表和哈希表的组合，所以可以直接拿来使用。
publicclassLRUCacheextendsLinkedHashMap{privateintcapacity;publicLRUCache(intcapacity){//注意这里将LinkedHashMap的accessOrder设为truesuper(16,0.75f,true);this.capacity=capacity;}@OverrideprotectedbooleanremoveEldestEntry(Map.Entryeldest){returnsuper.size()>=capacity;}}默认LinkedHashMap并不会淘汰数据，所以我们重写了它的removeEldestEntry()方法，当数据数量达到预设上限后，淘汰数据，accessOrder设为true意为按照访问的顺序排序。整个实现的代码量并不大，主要都是应用LinkedHashMap的特性。
朴素的LRU算法已经能够满足缓存的要求了，但是还是有一些不足。当热点数据较多时，有较高的命中率，但是如果有偶发性的批量操作，会使得热点数据被非热点数据挤出容器，使得缓存受到了“污染”。所以为了消除这种影响，又衍生出了下面这些优化方法。
LRU-K算法是对LRU算法的改进，将原先进入缓存队列的评判标准从访问一次改为访问K次，可以说朴素的LRU算法为LRU-1。
LRU-K算法有两个队列，一个是缓存队列，一个是数据访问历史队列。当访问一个数据时，首先先在访问历史队列中累加访问次数，当历史访问记录超过K次后，才将数据缓存至缓存队列，从而避免缓存队列被污染。同时访问历史队列中的数据可以按照LRU的规则进行淘汰。具体如下图所示：
下面我们来实现一个LRU-K缓存：
//直接继承我们前面写好的LRUCachepublicclassLRUKCacheextendsLRUCache{privateintk;//进入缓存队列的评判标准privateLRUCachehistoryList;//访问数据历史记录publicLRUKCache(intcacheSize,inthistoryCapacity,intk){super(cacheSize);this.k=k;this.historyList=newLRUCache(historyCapacity);}@OverridepublicIntegerget(Integerkey){//记录数据访问次数IntegerhistoryCount=historyList.get(key);historyCount=historyCount==null0:historyCount;historyList.put(key,++historyCount);returnsuper.get(key);}@OverridepublicIntegerput(Integerkey,Integervalue){if(value==null){returnnull;}//如果已经在缓存里则直接返回缓存中的数据if(super.get(key)!=null){returnsuper.put(key,value);;}//如果数据历史访问次数达到上限，则加入缓存IntegerhistoryCount=historyList.get(key);historyCount=historyCount==null0:historyCount;if(historyCount>=k){//移除历史访问记录historyList.remove(key);returnsuper.put(key,value);}}}上面只是个简单的模型，并没有加上必要的并发控制。
一般来讲，当K的值越大，则缓存的命中率越高，但是也会使得缓存难以被淘汰。综合来说，使用LRU-2的性能最优。
TwoQueue可以说是LRU-2的一种变种，将数据访问历史改为FIFO队列。好处的明显的，FIFO更简易，耗用资源更少，但是相比LRU-2会降低缓存命中率。
相比于上面两种优化，MultiQueue的实现则复杂的多，顾名思义，MultiQueue是由多个LRU队列组成的。每一个LRU队列都有一个相应的优先级，数据会根据访问次数计算出相应的优先级，并放在该队列中。
MultiQueue也可以看做是LRU-K的变种，将原来两个队列扩展为多个队列，好处就是无论是加入缓存还是淘汰缓存数据都变得更加细腻，但是会带来额外开销。