人生有涯，学海无涯。
《Java 极客技术》公众号已经有很多优质的原创文章了，但是纵观公号的历史文章总感觉少了点啥，那就是算法相关的内容。算法可以说是编程人员不可避免的一个难题，而且算法也是一个非常难的课题，很多人一提到数据结构与算法都会瑟瑟发抖。学算法是一个持久战，后续我们会慢慢增加算法相关的文章，尽量的为大家提供一些帮助，今天让我们来看一个经典的算法 LRU(最近最少使用)算法。
LRU 简介
Least Recently Used的缩写，即最近最少使用，可以用来作为路由或者淘汰算法。很多开源的框架或者一些第三方的项目都会采用到这个算法，比如 Redis 的 key 的缓存失效，比如一些路由功能。
算法的思想是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。正是由于这个特性，所以我们可以将使用不到的数据淘汰，或者如果是路由，我们就可以将数据路由到这台机器，实现负载。
这里我们以淘汰数据为例，提供两种实现方式。
算法实现
基于链表的 LRU 实现
思路：每次新插入数据的时候将新数据插到链表的头部；每次缓存命中（即数据被访问），则将数据移到链表头部；那么当链表满的时候，就将链表尾部的数据淘汰。
代码实现
package com.silence.arts.leetcode; import java.util.LinkedList; /** * <br> * <b>Function：</b><br> * <b>Author：</b>@author ziyou<br> * <b>Date：</b>2019-07-30 23:27<br> * <b>Desc：</b>无<br> */ public class LruCacheDemo { /** * 定义链表的大小 */ private int capacity; /** * 初始化链表 */ private LinkedList<User> cacheList = new LinkedList<>(); public LruCacheDemo(int capacity) { this.capacity = capacity; } /** * 根据名称获取数据，如果名称相同则返回用户实体，并且将该用户移动到链表头部 * * @param username 名称 * @return 用户 */ public User get(String username) { User u = null; for (User user : cacheList) { if (user.getUsername().equals(username)) { cacheList.remove(user); cacheList.add(0, user); u = user; } } return u; } public void put(User user) { //判断链表长度是否达到最大 if (cacheList.size() == capacity) { cacheList.remove(capacity - 1); } cacheList.add(0, user); } public static void main(String[] args) { LruCacheDemo cacheDemo = new LruCacheDemo(5); User user1 = new User("a1", 1); cacheDemo.put(user1); User user2 = new User("a2", 2); cacheDemo.put(user2); System.out.println(cacheDemo.get("a1")); User user3 = new User("a3", 3); cacheDemo.put(user3); User user4 = new User("a4", 4); cacheDemo.put(user4); System.out.println(cacheDemo.get("a4")); System.out.println(cacheDemo.get("a2")); User user5 = new User("a5", 5); cacheDemo.put(user5); User user6 = new User("a6", 6); cacheDemo.put(user6); System.out.println(cacheDemo.get("a1")); } static class User { public User(String username, int age) { this.username = username; this.age = age; } private String username; private int age; public String getUsername() { return username; } public void setUsername(String username) { this.username = username; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } } }
基于 HashMap 和 Linkedlist 的 LRU 实现
这种实现方式其他跟上面的实现方式类似，区别的地方是在这种方式采用的是 JDK 封装好的，给大家参考如下
package com.silence.arts.leetcode; import java.util.ArrayList; import java.util.Collection; import java.util.LinkedHashMap; import java.util.Map; /** * <br> * <b>Function：</b><br> * <b>Author：</b>@author ziyou<br> * <b>Date：</b>2019-07-30 23:35<br> * <b>Desc：</b>无<br> */ public class LRULinkedMap<K, V> { /** * 最大缓存大小 */ private int cacheSize; private LinkedHashMap<K, V> cacheMap; public LRULinkedMap(int cacheSize) { this.cacheSize = cacheSize; cacheMap = new LinkedHashMap(16, 0.75F, true) { @Override protected boolean removeEldestEntry(Map.Entry eldest) { if (cacheSize + 1 == cacheMap.size()) { return true; } else { return false; } } }; } public void put(K key, V value) { cacheMap.put(key, value); } public V get(K key) { return cacheMap.get(key); } }
总结
今天给大家介绍了一下 LRU 算法的两种实现，还有很多变种的实现方式大家可以自行的搜索学习。
我们只要记住 LRU 的核心思想：新增和最近被访问的数据需要移到到链表前，淘汰的是链表最后的一个数据。
在算法的道路上还有很多路要走，大家一起加油。
欢迎加入我的知识星球，一起成长，交流经验。加入方式，长按下方二维码噢
最后，我想重复一句话：选择和一群优秀的人一起成长，你成长的速度绝对会不一样！
