【死磕 Java 基础】 — 自己动手实现一个 LRU

LRU，即 Least Recently Use ，直译为 “最近最少使用”。它是根据数据的历史访问记录来进行数据淘汰的，淘汰掉最先访问的数据，其核心思想是 如果数据最近被访问过，那么将来被访问的几率也会更加高。

要实现 LRU，需要做到两点：

查询出最近最晚使用的项

给最近使用的项做一个标记

实现的方案有多种，这里小编主要介绍两种：

LinkedHashMap

双向链表 + HashMap

利用 LinkedHashMap 的原因就在于 LinkedHashMap 是有序的，默认情况下是按照元素的添加顺序存储的，也可以调整为根据访问顺序来调整内部顺序（设置参数 accessOrder 进行调整），即最近读取的数据放在最前面，我们就是利用 LinkedHashMap 的这个特性来实现 LRU。先来一个简单的例子吧：

运行结果：

更多关于 LinkedHashMap，请看这篇文章：图解集合6：LinkedHashMap

LinkedHashMap 实现 LRU 有两种方式，一种是继承 LinkedHashMap，一种是利用组合的方式，下面分别演示这两种情况。

采用继承的方式实现起来是非常简单的，因为 LinkedHashMap 本身就已经具备了 LRU 的特性，我们只需要实现一点：当容器中元素个数超过我们设定的容量后，删除第一个元素即可。同时由于 LinkedHashMap 本身不具备线程安全，我们需要确保他线程安全，这个也很简单，重写 LinkedHashMap 的 <code>get()</code> 和 <code>put()</code> 方法即可，或者使用 Collections.synchronizedMap() 方法也可以。实现如下：

验证

运行结果完全符合我们的预期

使用组合的方式可能会更加优雅些，但是由于没有实现 Map 接口，所以就不能使用 <code>Collections.synchronizedMap()</code> 方式来保证线程安全性了，所以需要在每个方法处增加 synchronized 来确保线程安全。实现方式如下：

验证：

运行结果如下：

组合的方式也显得非常简单，有两点需要注意：

保证每个方法的线程安全

put 时，需要查看当前容量是否超过设置的容量，超过则需要删除第一个元素。当然小编这种是实现方式不是很优雅，这么做知识为了能够更加好阐述 LRU 的实现。更好的方案是在构造 LinkedHashMap 时，重写 <code>removeEldestEntry()</code>，如下：

我们想想，在不利用现存数据结构的条件（如 LinkedHashMap）如何实现一个 LRU 呢？缓存部分容易实现，我们都知道利用 HashMap 即可，但是如何实现缓存容量不足时丢弃最不常用的数据的功能？

利用时间戳。每一个访问，增加的元素我们都给其更新一个时间戳，在 put 的时候，检查，删除时间戳最小的就可以了。这种方法可以实现，但是代价较高，就是我们需要遍历整个数据，得到最小的时间戳。

我们可以换位思考，我们其实不需要关注每个节点的增加或者遍历时间，我们只需要知道那个节点是最先访问就可以了，所以我们可以利用链表记录访问记录，有新数据加入时放在链表的 head 节点，每次访问也将该数据放在 head 节点，那么链表的 tail 一定是最早访问的节点，所以每次当容量不足的时候删除 tail 节点数据并将它的前驱节点设置为 tail 就可以了。注意，这个链表是一个双向链表。代码如下：

执行结果：

PS:如果你觉得文章对你有所帮助，别忘了推荐或者分享，因为有你的支持，才是我续写下篇的动力和源泉！

作者：chenssy。一个专注于【死磕 Java】系列创作的男人

出处：https://www.cnblogs.com/chenssy/p/15164873.html

作者个人网站：https://www.cmsblogs.com/。专注于 Java 优质系列文章分享，提供一站式 Java 学习资料

目前死磕系列包括：

    1. 【死磕 Java 并发】：https://www.cmsblogs.com/category/1391296887813967872（已完成）

    2.【死磕 Spring 之 IOC】：https://www.cmsblogs.com/category/1391374860344758272（已完成）

    3.【死磕 Redis】：https://www.cmsblogs.com/category/1391389927996002304（已完成）

    4.【死磕 Java 基础】：https://www.cmsblogs.com/category/1411518540095295488

    5.【死磕 NIO】：https://www.cmsblogs.com/article/1435620402348036096

本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。