利用LinkedHashMap实现一个LRU缓存

一、什么是 LRU

LRU是 Least Recently Used 的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。

简单的说就是，对于一组数据，例如：int[] a = {1,2,3,4,5,6}，如果1,2这几个数字经常被使用，那么会排在3,4,5,6的后面，数组变成如下：int[] a = {3,4,5,6,1,2}，如果一个数字，经常不被使用，就会排在最前面！

LRU 算法，一般用于热点数据的查询，比如新闻信息，越是能被用户看得多的新闻，越有可能被别的用户所看到，对于那种基本没人访问的新闻，基本都类似存入大海！

在 Java 中，就有这么一个集合类实现了这个功能，它就是LinkedHashMap ！

二、LinkedHashMap 实现介绍

我们都知道，在java集合中，LinkedHashMap 继承自 HashMap，底层是一个双向链表的数据结构，与 HashMap 不同的是，LinkedHashMap 初始化阶段有个参数accessOrder ，默认是false。

public class LinkedHashMap<K,V>extends HashMap<K,V>implements Map<K,V>{/**双向链表的头节点*/transient LinkedHashMap.Entry<K,V> head;/**双向链表的尾节点*/transient LinkedHashMap.Entry<K,V> tail;/*** 1、如果accessOrder为true的话，则会把访问过的元素放在链表后面，放置顺序是访问的顺序* 2、如果accessOrder为false的话，则按插入顺序来遍历*/final boolean accessOrder;
}

如果传入的是true，则会把最近访问过的元素放在链表后面，放置顺序是访问的顺序，测试如下：

public static void main(String[] args) {//accessOrder默认为falseMap<String, String> accessOrderFalse = new LinkedHashMap<>();accessOrderFalse.put("1","1");accessOrderFalse.put("2","2");accessOrderFalse.put("3","3");accessOrderFalse.put("4","4");System.out.println("acessOrderFalse："+accessOrderFalse.toString());//accessOrder设置为trueMap<String, String> accessOrderTrue = new LinkedHashMap<>(16, 0.75f, true);accessOrderTrue.put("1","1");accessOrderTrue.put("2","2");accessOrderTrue.put("3","3");accessOrderTrue.put("4","4");accessOrderTrue.get("2");//获取键2accessOrderTrue.get("3");//获取键3System.out.println("accessOrderTrue："+accessOrderTrue.toString());
}

输出结果如下：

acessOrderFalse：{1=1, 2=2, 3=3, 4=4}
accessOrderTrue：{1=1, 4=4, 2=2, 3=3}

可以得知，当我们将accessOrder设置为true的时候，经常被访问的元素会放入前面！

我们利用这个特性，使用 LinkedHashMap 来实现一个 LRU 缓存，操作如下：

• 创建一个 LinkedHashMap 对象，将accessOrder设置为true；
• 设定 LinkedHashMap 的容量为n，超过这个值就删除多余的元素；
• 重写 LinkedHashMap 中removeEldestEntry()方法；

其中removeEldestEntry()表示，如果返回的是true，就会移除最近不被使用的元素，如果返回false，不做任何操作，这个方法每次在add()的时候就会调用。

创建一个 LRU 缓存类，内容如下：

public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {//创建一个容量为3的LinkedHashMapprivate static final int MAX_SIZE = 3;/*** 重写LinkedHashMap中removeEldestEntry方法* @param eldest* @return*/protected boolean removeEldestEntry(Map.Entry eldest) {//如果容器中的元素个数大于MAX_SIZE，在每次添加元素的时候，移除容器中最近不被使用的元素return size() > MAX_SIZE;}public LRULinkedHashMap() {//设置LinkedHashMap初始化容量，负载因子为0.75f，accessOrder设置为truesuper(MAX_SIZE, 0.75f, true);}
}

测试使用：

public static void main(String[] args) {LRULinkedHashMap<String,String> cache = new LRULinkedHashMap<String,String>();cache.put("1","a");cache.put("2","b");cache.put("3","c");System.out.println("初始cache内容：" + cache.toString());cache.get("2");System.out.println("查询key为2的元素之后，cache内容：" + cache.toString());cache.put("4","d");System.out.println("添加新的元素之后，cache内容：" + cache.toString());
}

输出结果如下：

初始cache内容：{1=a, 2=b, 3=c}
查询key为2的元素之后，cache内容：{1=a, 3=c, 2=b}
添加新的元素之后，cache内容：{3=c, 2=b, 4=d}

三、小结

在实际的业务开发过程中，LRU 算法应用比较广泛，比如热点排行榜，设置容量为3的时候，会将不常用的新闻移除，保留最新的热点信息。

写到最后

不会有人刷到这里还想白嫖吧？点赞对我真的非常重要！在线求赞。加个关注我会非常感激！

本文已整理到技术笔记中，此外，笔记内容还涵盖 Spring、Spring Boot/Cloud、Dubbo、JVM、集合、多线程、JPA、MyBatis、MySQL、微服务等技术栈。

需要的小伙伴可以点击 技术笔记 获取！