相关历史文章（阅读本文之前，您可能需要先看下之前的系列👇）
色谈Java序列化：女孩子慎入 - 第280篇
烦不烦，别再问我时间复杂度了：这次不色，女孩子进来吧 - 第281篇
双向链表，比西天还远？ - 第282篇
「LRU算法在很多的框架中都有使用，如druid数据库连接池、spring框架、jdk、mysql的驱动」
悟纤：师傅，徒儿最近在研究Memcached的时候，发现Memcached的缓存淘汰机制是LRU，什么是LRU呐？
师傅：这个就有的说了，今天我们就来撸啊撸，好好的撸一下LRU。
一、算法
「百度百科」
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。
「学深悟透」
悟纤：师傅这描述的太抽象了，文字又多，理解不了，理解不了。
师傅：徒儿，莫慌，待为师用通俗易通的语言给你解释一下。
BTW：（1）算法是有顺序的运算步骤。（2）算法的目标是能够解决一类问题。
举例说明：有5个数[1，4，7，2，6]，要从中找到最大的的数是多少。第一步需要拿第一个数和第二个数对比，得到比较大的数；第二步在拿上一步得到的数和第三个数进行对比，得到比较大的数…类似类推，最终就可以获得最大的数。
我们会发现描述一个算法的时候，是有顺序的步骤，在每个步骤当中需要进行相应的运算。针对这种类似的问题，一旦算法写好了，那么这类问题都可以使用这个算法进行解决。
对于 计算机中算法 就是软件开发人员在软件中编写的代码逻辑。
马老师说：什么叫算法？算法就是你要比老公更懂得老公，你要比老婆更懂得老婆。但是真正的算法，婚姻的算法是什么？婚姻是算不清楚的。你对还是我对，我对你爱多一点，还是你对我爱多一点。婚姻的算法，最后就是“算了吧”，就是最好的算法。
二、缓存算法
2.1 基本概念
「百度百科：LINK」
缓存算法是指令的一个明细表，用于提示计算设备的缓存信息中哪些条目应该被删去。常见类型包括LFU、LRU、ARC、FIFO、MRU。
最不经常使用算法（LFU：LeastFrequently Used）：这个缓存算法使用一个计数器来记录条目被访问的频率。通过使用LFU缓存算法，最低访问数的条目首先被移除。这个方法并不经常使用，因为它无法对一个拥有最初高访问率之后长时间没有被访问的条目缓存负责。
最近最少使用算法（LRU：LeastRecently Used）：这个缓存算法将最近使用的条目存放到靠近缓存顶部的位置。当一个新条目被访问时，LRU将它放置到缓存的顶部。当缓存达到极限时，较早之前访问的条目将从缓存底部开始被移除。这里会使用到昂贵的算法，而且它需要记录“年龄位”来精确显示条目是何时被访问的。此外，当一个LRU缓存算法删除某个条目后，“年龄位”将随其他条目发生改变。
自适应缓存替换算法(ARC：AdaptiveReplacement Cache)：在IBM Almaden研究中心开发，这个缓存算法同时跟踪记录LFU和LRU，以及驱逐缓存条目，来获得可用缓存的最佳使用。
最近最常使用算法（MRU：Mostrecently used）：这个缓存算法最先移除最近最常使用的条目。一个MRU算法擅长处理一个条目越久，越容易被访问的情况。
先进先出算法（FIFO：First InFirst Out）：是一种先进先出的数据缓存器，他与普通存储器的区别是没有外部读写地址线，这样使用起来非常简单，但缺点就是只能顺序写入数据，顺序的读出数据，其数据地址由内部读写指针自动加1完成，不能像普通存储器那样可以由地址线决定读取或写入某个指定的地址。
2.2 举个栗子
「学深悟透」
悟纤：这描述看的让我的心都躁动不安了，师傅，能简单解释或者举些例子嘛。
师傅：那为师给你举例几个小栗子。
FIFO（First in First out）:
FIFO先进先出算法，这个最简单了，就是谁先进来，我们就把谁先淘汰掉。举例说明（我们假设缓存的大小设置为5）：
（1）首先插入ABC，那么内存里是ABC;
（2）再次插入DE，那么内存队列里是ABCDE；
（3）再次插入F，则最先进入的A被淘汰；
（4）再次插入G，则淘汰第二次进入队列的B。
这个算法有什么问题呢？那就众生平等，无论王侯将相，进来的，早晚得出去，而且是ONE BY ONE 排队出去。
LRU（Least Recently Used）:
LRU 最近最少使用算法，顾名思义，就是哪个是最近不用的，就把他淘汰掉。这是目前阶段最常用的缓存淘汰算法了。举例说明（假设我们缓存里面存放5个元素）：
（1）首先插入ABC，那么会把ABC放到对应的位置上；
（2）再次插入DE，这个时候元素的个数还没到元素的总个数，所以不用淘汰；
（3）插入F，发现元素个数大于缓存的上限，所以把最近没有使用的A淘汰掉。
（4）插入B，B已经在缓存里面了，所以把B的位置提到最新的位置；
（5）插入G，这个时候最旧的数据已经不是B，而是C，所以把C淘汰掉。
这种算法有什么问题呢？不凡假设有这么一种情况，可能有某个数据出现的频率很高，每隔一段时间就会出现，也避免不了被淘汰的命运，所以又有人提出了另外的淘汰算法。
LFU（least frequently used）：
LFU最近不常用算法，顾名思意，就是淘汰缓存里面用的最少的了。举例说明（我们同样假设缓存里面存放的元素是5个，我们对每一个元素都维护一个计数器，记录用了多少次）：
（1）依次插入ABC，每个的计数器上都是1：A(1)B(1)C(1)
（2）依次插入DE，ABCDE的计数器上也都是1：A(1)B(1)C(1)D(1)E(1)
（3）插入ABCE，除了D之外，其他的计数器都是2：A(2)B(2)C(2)D(1)E(2)
（4）再次插入F，发现D的计数器最小，于是淘汰掉D。A(2)B(2)C(2)F(1)E(2)
师傅：对于缓存算法，为师就说这么多了，还是来讲今天的重点LRU算法。
三、LRU算法
3.1 LRU概念
我们在回顾下LRU算法的概念：LFU最近最少使用算法，就是淘汰缓存里面用的最少的了。所以当缓存数据在内存越来越多，以至于无法存放即将到来的新缓存数据时，就必须扔掉最不常用的缓存数据。所以对于LRU的抽象总结如下：
（1）缓存的容量是有限的（可以使用一个常量标识缓存容器可以存放的大小）。
（2）当缓存容量不足以存放需要缓存的新数据时，必须丢掉最不常用的缓存数据。
3.2 LRU的实现
LRU的一种实现方式可以利用双向链表实现，双向链表有一个特点就是它的链表是双路的，我们定义好头节点和尾节点，然后利用先进先出（FIFO），最近被放入的数据会最早被获取。其中主要涉及到添加、访问、修改、删除操作。
3.2.1简单思路编码
理解了LRU的原理之后，想要将其转换为代码并不是一件很困难的事。我们访问缓存通常使用一个字符串（key）来定位缓存数据（value）（事实上其他数据形式也没有关系），这种场景我们反射性的想到HashMap，基于这个思路就有了如下的代码：
public class LRUCache { private HashMap<String, Object> caches; private int capacity; /**构造方法: 初始化储存容器map*/ public LRUCache(int capacity) { this.capacity = capacity; this.caches = new HashMap<String, Object>(); } /**get */ public Object get(String key) { return map.get(key); } /**set */ public void set(String key, Object value) { this.map.put(key, value); } }这样我们仅仅是定义了一个容量有限的LRUCache，可以存取数据，但并没有实现缓存容量不足时丢弃最不常用的数据的功能，而这件事做起来似乎显得稍微麻烦一些，问题在于我们如何找到最久没有用的缓存。
一个最容易想到的办法是我们在给这个缓存数据加一个时间戳，每次get缓存时就更新时间戳， 这样找到最久没有用的缓存数据问题就能够解决，但与之而来的会有两个新问题：
（1）虽然使用时间戳可以找到最久没用的数据，但我们最少的代价也要将这些缓存数据遍历一遍，除非我们维持一个按照时间戳排好序的SortedList。
（2）添加时间戳的方式为我们的数据带来了麻烦，我们并不太好在缓存数据中添加时间戳的标识，这可能需要引入新的包含时间戳的包装对象。
而且我们的需要只是找到最久没用使用的缓存数据，并不需要精确的时间。添加时间戳的方式显然没有利用这一特性，这就使得这个办法从逻辑上来讲可能不是最好的。
那么应该怎么办呢？还记得之前介绍的双向链表嘛？《双向链表，比西天还远？》
3.2.2 利用双向链表进行实现
我们可以维护一个链表，当数据每一次查询就将数据放到链表的head，当有新数据添加时也放到head上。这样链表的tail就是最久没用使用的缓存数据，每次容量不足的时候就可以删除tail，并将前一个元素设置为tail，显然这是一个双向链表结构，因此我们定义LRUNode如下：
public class LRUNode { String key; Object value; LRUNode pre;//指向上一个节点 LRUNode next;//指向下个节点 public LRUNode(String key, Object value) { this.key = key; this.value = value; } }这时候LRUCache改变为：
public class LRUCache { private HashMap<String, LRUNode> caches; private int capacity; private LRUNode head;//头节点 private LRUNode tail;//尾节点 /**构造方法: 初始化储存容器map*/ public LRUCache(int capacity) { this.capacity = capacity; this.caches = new HashMap<String, LRUNode>(); } }
说明：这里的map保存的不是单纯的Object对象，而是双向链表对象，另外记录head和tail节点，在缓存对象满的时候，要移除最后一个对象，使用tail.key可以获取到最近不使用的key，然后map.remove（key）。
3.2.3 添加元素
添加元素的时候首先判断是不是新的元素，如果是新元素，判断当前的大小是不是大于总容量了，防止超过总链表大小，如果大于的话直接抛弃最后一个节点，然后再以传入的key\value值创建新的节点。对于已经存在的元素，直接覆盖旧值，再将该元素移动到头部，然后保存在map中:
public void put(String key,Object value) { LRUNode node = caches.get(key); //新节点 if(node == null) { //如果超过元素容纳量，移除最后一个节点 if(caches.size()>=capacity) { caches.remove(tail.key); //移除最后一个节点: removeTail(); } //构建一个节点,节点的prev,next下面操作 node = new LRUNode(key, value); } //已经存在的元素覆盖旧值,新创建的节点,就是一样了。 node.value = value; //把元素移动到首部 moveToHead(node); caches.put(key, node); }在这上面牵涉到两个私有方法：removeTail()和moveToHead(node)，我们先来看下这两个方法。
3.2.4 移除最后一个元素
移除最后一个元素主要考虑：
（1）直接把tail节点的上一个节点(pre) ，指向当前的tail即可：tail = tail.pre。
（2）如果新的tail==null的话，说明已经没有节点了，需要设置：head=null。
（3）如果新的tail存在，那么这个新的下个节点需要指向null：tail.next = null。
具体代码如下：
private void removeTail() { if(tail != null) { //将最后一个节点的上一个节点设置为tail tail = tail.pre; if(tail == null) { //都移除没了 head = null; }else { //原本指向的是当前这个的节点的，移除掉了，那么此节点的next也没有了。 tail.next = null; } } }
3.2.5 移动元素到头节点
首先把当前节点移除，然后再将首节点设为当前节点的下一个,再把当前节点设为头节点的前一个节点，当前节点设为首节点，再把首节点的前一个节点设为null，这样就是间接替换了头节点为当前节点。
private void moveToHead(LRUNode node) { /* * 如果当前节点的引用，就是头部节点，无需处理，直接返回。 */ if(head == node) { //当前节点就在头位置，直接return return; } /* * 第一个节点的时候，head和tail都是不存在的，直接设置即可。 * 另外对于节点的node的pre和next也都不存在，处理直接结束. */ if (head == null || tail == null) { head = tail = node; return; } //当前节点的next存在的话,很明显是老节点 if (node.next != null) { //此节点要从当前位置直接移动到head,需要对于它的next进行处理。 //移走之后，next的pre就需要指向，node的pre node.next.pre = node.pre; } //当node的pre存在的时候，不是第一个节点. if (node.pre != null) { //此节点要从当前位置直接移动到head,需要对于它的pre进行处理。 //移走之后，pre的next就需要指向 ，node的next node.pre.next = node.next; } if (node == tail) { tail = tail.pre; } node.next = head;//head变为node的next节点。 head.pre = node; //头部移动到第二个节点，那么head.pre 就是当前节点了。 head = node; // 头部节点，直接指向新的节点。 head.pre = null;//由于是head 那么pre设置为null, next就是上一次head。 }BTW：每行代码上有详细解说，主要是先理清整体的思路。
3.2.6 访问元素
通过key值来访问元素，主要的做法就是先判断如果是不存在的，直接返回null。如果存在，把数据移动到首部头节点，然后再返回旧值。
/** * 通过key获取元素 * @param key * @return */ public Object get(String key) { LRUNode node = caches.get(key); if(node == null) { return null; } //把访问的节点移动到首部。 moveToHead(node); return node.value; }
3.2.7 节点删除操作
在根据key删除节点的操作中，我们需要做的是把节点的前一个节点的指针指向当前节点下一个位置，再把当前节点的下一个的节点的上一个指向当前节点的前一个:
public Object remove(String key) { LRUNode node = caches.get(key); if (node != null) { //当前节点存在上一个节点的指向，说明不是head if (node.pre != null) { //由于此节点被移走了，那么上一个节点的next原本指向当前节点的， //移走之后，需要指向当前节点的next. node.pre.next = node.next; } //当前节点存在下一个节点的指向，说明不是tail if (node.next != null) { //由于此节点被移走了，那么下个节点的pre原本指向是当前节点的， //移走之后，需要指向当前节点的pre. node.next.pre = node.pre; } //当前删除的就是头部节点.那么头部节点需要指向当前节点的next. if (node == head) { head = node.next; } //当前删除的就是尾部节点，那么尾部节点就需要指向当前节点的上一个节点。 if (node == tail) { tail = node.pre; } } return caches.remove(key); }
3.2.8 重写toString方法
为了打印，重写toString()方法，遍历思路就是获取到head节点，然后通过head.next不断循环，直接next为null结束循环：
@Override public String toString() { StringBuilder sb = new StringBuilder(); LRUNode node = head; sb.append("["); while (node != null) { sb.append(String.format("%s:%s ", node.key, node.value)); node = node.next; } sb.append("]"); return sb.toString(); }
3.2.9 全部代码
提供上面分析的全部代码：
LRUNode：
public class LRUNode { String key; Object value; LRUNode pre;//指向上一个节点 LRUNode next;//指向下个节点 public LRUNode(String key, Object value) { this.key = key; this.value = value; } }
LRUCache：
public class LRUCache { private HashMap<String, LRUNode> caches; private int capacity; private LRUNode head;//头节点 private LRUNode tail;//尾节点 /**构造方法: 初始化储存容器map*/ public LRUCache(int capacity) { this.capacity = capacity; this.caches = new HashMap<String, LRUNode>(); } /** * 添加元素的时候首先判断是不是新的元素，如果是新元素， * 判断当前的大小是不是大于总容量了，防止超过总链表大小， * 如果大于的话直接抛弃最后一个节点，然后再以传入的key\value值创建新的节点。 * 对于已经存在的元素，直接覆盖旧值，再将该元素移动到头部，然后保存在map中 * @param key * @param value */ public void put(String key,Object value) { LRUNode node = caches.get(key); //新节点 if(node == null) { //如果超过元素容纳量，移除最后一个节点 if(caches.size()>=capacity) { caches.remove(tail.key); //移除最后一个节点: removeTail(); } //构建一个节点,节点的prev,next下面操作 node = new LRUNode(key, value); } //已经存在的元素覆盖旧值,新创建的节点,就是一样了。 node.value = value; //把元素移动到首部 moveToHead(node); caches.put(key, node); } /** * 通过key获取元素 * @param key * @return */ public Object get(String key) { LRUNode node = caches.get(key); if(node == null) { return null; } //把访问的节点移动到首部。 moveToHead(node); return node.value; } /** * 根据key移除节点 * @param key * @return */ public Object remove(String key) { LRUNode node = caches.get(key); if (node != null) { //当前节点存在上一个节点的指向，说明不是head if (node.pre != null) { //由于此节点被移走了，那么上一个节点的next原本指向当前节点的， //移走之后，需要指向当前节点的next. node.pre.next = node.next; } //当前节点存在下一个节点的指向，说明不是tail if (node.next != null) { //由于此节点被移走了，那么下个节点的pre原本指向是当前节点的， //移走之后，需要指向当前节点的pre. node.next.pre = node.pre; } //当前删除的就是头部节点.那么头部节点需要指向当前节点的next. if (node == head) { head = node.next; } //当前删除的就是尾部节点，那么尾部节点就需要指向当前节点的上一个节点。 if (node == tail) { tail = node.pre; } } return caches.remove(key); } /** * 把当前节点移动到首部: * */ private void moveToHead(LRUNode node) { /* * 如果当前节点的引用，就是头部节点，无需处理，直接返回。 */ if(head == node) { //当前节点就在头位置，直接return return; } /* * 第一个节点的时候，head和tail都是不存在的，直接设置即可。 * 另外对于节点的node的pre和next也都不存在，处理直接结束. */ if (head == null || tail == null) { head = tail = node; return; } //当前节点的next存在的话,很明显是老节点 if (node.next != null) { //此节点要从当前位置直接移动到head,需要对于它的next进行处理。 //移走之后，next的pre就需要指向，node的pre node.next.pre = node.pre; } //当node的pre存在的时候，不是第一个节点. if (node.pre != null) { //此节点要从当前位置直接移动到head,需要对于它的pre进行处理。 //移走之后，pre的next就需要指向 ，node的next node.pre.next = node.next; } if (node == tail) { tail = tail.pre; } node.next = head;//head变为node的next节点。 head.pre = node; //头部移动到第二个节点，那么head.pre 就是当前节点了。 head = node; // 头部节点，直接指向新的节点。 head.pre = null;//由于是head 那么pre设置为null, next就是上一次head。 } /** * 移除最后一个节点 */ private void removeTail() { if(tail != null) { //将最后一个节点的上一个节点设置为tail tail = tail.pre; if(tail == null) { //都移除没了 head = null; }else { //原本指向的是当前这个的节点的，移除掉了，那么此节点的next也没有了。 tail.next = null; } } } @Override public String toString() { StringBuilder sb = new StringBuilder(); LRUNode node = head; sb.append("["); while (node != null) { sb.append(String.format("%s:%s ", node.key, node.value)); node = node.next; } sb.append("]"); return sb.toString(); } }
3.2.10 测试
来写个代码测试下吧：
public static void main(String[] args) { LRUCache lru = new LRUCache(5); //设置数据 lru.put("key1","1号技师"); lru.put("key2","2号技师"); lru.put("key3","3号技师"); lru.put("key4","4号技师"); lru.put("key5","5号技师"); System.out.println("原始链表："+lru.toString()); System.out.println("获取key为4的元素之后的链表:"+lru.toString()); lru.put("key6","6号技师"); System.out.println("新添加一个key为6之后的链表:"+lru.toString()); lru.remove("key3"); System.out.println("移除key=3的之后的链表:"+lru.toString()); }运行结果：
原始链表：[key5:5号技师 key4:4号技师 key3:3号技师key2:2号技师 key1:1号技师 ]
获取key为4的元素之后的链表:[key5:5号技师key4:4号技师 key3:3号技师 key2:2号技师 key1:1号技师 ]
新添加一个key为6之后的链表:[key6:6号技师key5:5号技师 key4:4号技师 key3:3号技师 key2:2号技师 ]
移除key=3的之后的链表:[key6:6号技师 key5:5号技师 key4:4号技师 key2:2号技师]
四、悟纤小结
悟纤：师傅这是静可以静的可怕，动可以动的吓人。不鸣则已，一鸣惊人，听的徒儿脑瓜都疼了。
师傅：今天为师是唠叨的有点多了，这次就让为师来总结一下。
（1）何为算法：有顺序的运算步骤。
（2）何为计算机算法：软件开发人员在软件中编写的代码逻辑。
（3）常用的缓存算法：FIFO、LFU、LRU。
（4）LRU：最近最少使用算法（LRU：Least Recently Used）哪个是最近不用的，就把他淘汰掉。
（5）LRU的实现：HashMap+双向链表。
师傅：悟纤，咱们今天就到到此为止，但是为师还有一个问题要考考你，看你有没有认真学习。
悟纤：师傅，你放马过来。
师傅：
问题：LRU（HashMap+双向链表的实现）的put/get/remove时间复杂度是多少？
悟纤：师傅，这个问题，我有好好听你将《烦不烦，别再问我时间复杂度了：这次不色，女孩子进来吧》，还是留给悟净吧。
师傅：为师相信你会了，但为师还有一点要说明的就是Redis的LRU还是有一些差距的：如果按照HashMap和双向链表实现，需要额外的存储存放 next 和 prev 指针，牺牲比较大的存储空间，显然是不划算的。所以Redis采用了一个近似的做法，就是随机取出若干个key，然后按照访问时间排序后，淘汰掉最不经常使用的。具体是怎么实现的，需要悟纤自己去研究了。
我就是我，是颜色不一样的烟火。 我就是我，是与众不同的小苹果。学院中有Spring Boot相关的课程：
à悟空学院：https://t.cn/Rg3fKJD
SpringBoot视频：http://t.cn/A6ZagYTi
Spring Cloud视频：http://t.cn/A6ZagxSR
SpringBoot Shiro视频：http://t.cn/A6Zag7IV
SpringBoot交流平台：https://t.cn/R3QDhU0
SpringData和JPA视频：http://t.cn/A6Zad1OH
SpringSecurity5.0视频：http://t.cn/A6ZadMBe
Sharding-JDBC分库分表实战：http://t.cn/A6ZarrqS
分布式事务解决方案「手写代码」：http://t.cn/A6ZaBnIr
悟纤 认证博客专家 知远公司创始人 架构师 访问1000万+ 「公众号SpringBoot」: ①阿里巴巴前高级研发工程师；②估值20亿美金的Blued架构师；③北京知远公司创始人；④浙江甄才公司架构师；⑤云课堂学员10000+；⑥博客访问量1000万+；⑦10年互联网行业从业；⑧360万的访问《从零开始学SprngBoot》作者；⑨技术加盟多个独立项目。