今天这篇文章的目的是理解LRU消除策略并实现一个LRU算法。
文章会用插图一步步讲解，你可以用我的思路慢慢理解。我们开始吧。
文章导读
LRU
Redis的淘汰策略
为什么有淘汰策略？因为内存的存储空间有限，所以要有淘汰的策略。
Redis清理内存消除的策略有哪些？
Redis内存消除策略
LRU算法简介
LRU是最近最少使用的缩写，即最近最少使用，是常用的页面替换算法。在我们手机的后台窗口(苹果手机双击Home的效果)，他总是把最常用的窗口放在最眯眼的店员，而最不常用的应用窗口则安排在后面。如果加上只能放置N个应用窗口的限制，去掉最近使用最少的应用窗口，就是活生生的LRU。
手机后台应用窗口
实现思想推导
手机应用案例
从上图中，我们可以分析出以下几点：
有序；如果有三个应用满了，要剔除最不常用的应用，需要在每次新访问一个应用时将数据插入到队列头(根据业务，可以设置哪边是队列头)；O(1)复杂性是我们搜索数据的追求。什么结构可以实现快速O(1)搜索？
推导图
通过以上推导，我们可以得出结论，LRU算法的核心是HashMap DoubleLinkedList。
想法很清楚，接下来我们将对其进行编码。
00-1010让我们查看使用Java的LinkedHashMap的说明。
LinkedHashMap的用户说明
这种地图结构非常适合构建LRU缓存。
继承LinkedHashMap实现LRU算法；
公共类LRUDemoK，V扩展了LinkedHashMapK，V {
私人国际能力；
公共LRUDemo(int capacity){ 0
超级(容量，0.75F，真)；
this.capacity=容量；
}
@覆盖
受保护的布尔值
removeEldestEntry(Map.Entry<K, V> eldest) { return super.size() > capacity; } public static void main(String[] args) { LRUDemo lruDemo = new LRUDemo(3); lruDemo.put(1, "a"); lruDemo.put(2, "b"); lruDemo.put(3, "c"); System.out.println(lruDemo.keySet()); lruDemo.put(4, "d"); lruDemo.put(5, "e"); System.out.println(lruDemo.keySet()); } }重点讲解：
构造方法：super(capacity, 0.75F, true)，主要看第三个参数：order参数true -> access-order // false -> insertion-order即按照访问时间排序，还是按照插入的时间来排序// 构造方法改成falsesuper(capacity, 0.75F, false);// 使用示例public static void main(String[] args) {LRUDemo lruDemo = new LRUDemo(3);lruDemo.put(1, "a");lruDemo.put(2, "b");lruDemo.put(3, "c");System.out.println(lruDemo.keySet());lruDemo.put(1, "y");// 构造方法order=true，输出：[2,3,1]，// 构造方法order=false，输出：[1,2,3]，System.out.println(lruDemo.keySet());}removeEldestEntry方法：什么时候移除最年长的元素。通过上面，相信大家对LRU算法有所理解了，接下来我们不依赖JDK的LinkedHashMap，通过我们自己的理解，动手实现一个LRU算法，让我们的LRU算法刻入我们的大脑。
手写LRU
上边的推导图中可以看出，我们用HashMap来做具体的数据储存，但是我们还需要构造一个DoubleLinkedList对象（结构体）来储存HashMap的具体key顺序关系。
第一步：构建DoubleLinkedList对象
所以我们现在第一步，就是构建一个DoubleLinkedList对象：
DoubleLinkedList示意图
我们可以从HashMap源码中找一些灵感，他们都是使用一个Node静态内部类来储存节点的值。
第二步：构建节点
通过上边的示意图，我们可以得知节点应该要储存的内容：
keyvalueprev节点next节点翻译成代码：
class Node<K, V> { K key; V value; Node<K, V> prev; Node<K, V> next; public Node() { this.prev = this.next = null; } public Node(K key, V value) { this.key = key; this.value = value; this.prev = this.next = null; } }第三步：初始化DoubleLinkedList对象
DoubleLinkedList初始化示意图
还是通过上边的示意图，我们可以得知DoubleLinkedList对象应该要储存的内容：
头节点尾节点翻译成代码：
class DoubleLinkedList<K, V> { Node<K, V> head; Node<K, V> tail; // 构造方法 public DoubleLinkedList(){ head = new Node<>(); tail = new Node<>(); head.next = tail; tail.prev = head; } }从头添加节点
从头添加节点
翻译成代码：
public void addHead(Node<K, V> node) { node.next = head.next; node.prev = head; head.next.prev = node; head.next = node; }删除节点
删除节点
翻译成代码：
public void removeNode(Node<K, V> node) { node.next.prev = node.prev; node.prev.next = node.next; node.prev = null; node.next = null; }获取最后一个节点
public Node getLast() { return tail.prev; }第四步：LRU对象属性
cacheSize
private int cacheSize;map
Map<Integer, Node<Integer, String>> map;doubleLinkedList
DoubleLinkedList<Integer, String> doubleLinkedList;第五步：LRU对象的方法
构造方法
public LRUDemo(int cacheSize) { this.cacheSize = cacheSize; map = new HashMap<>(); doubleLinkedList = new DoubleLinkedList<>(); }refreshNode刷新节点
public void refreshNode(Node node) { doubleLinkedList.removeNode(node); doubleLinkedList.addHead(node); }get节点
public String get(int key) { if (!map.containsKey(key)) { return ""; } Node<Integer, String> node = map.get(key); refreshNode(node); return node.value; }put节点
public void put(int key, String value) { if (map.containsKey(key)) { Node<Integer, String> node = map.get(key); node.value = value; map.put(key, node); refreshNode(node); } else { if (map.size() == cacheSize) { Node lastNode = doubleLinkedList.getLast(); map.remove(lastNode.key); doubleLinkedList.removeNode(lastNode); } Node<Integer, String> newNode = new Node<>(key, value); map.put(key, newNode); doubleLinkedList.addHead(newNode); } }第六步：测试
public static void main(String[] args) { LRUDemo lruDemo = new LRUDemo(3); lruDemo.put(1, "美团"); lruDemo.put(2, "微信"); lruDemo.put(3, "抖音"); lruDemo.put(4, "微博"); System.out.println(lruDemo.map.keySet()); System.out.println(lruDemo.get(2)); }原文链接：https://mp.weixin.qq.com/s/0U2Oq4IWPKrZRFX40uPQow