一、什么是LRU算法?

LRU 全称Least Recently Used, LRU算法是一种操作系统层面上的页面置换算法，将最近最久未使用的页面进行淘汰。

二、基于双向链表+Map实现LRU算法

为什么选用双向链表做cache?

思想: 将多次访问的节点移到头节点，将少访问的节点移到尾节点。

由于双向链表的自身特性，它能够很方便地找到上一个节点和下一个节点，对节点的操作相对来说比较容易。单向的不能找到上一个节点，在操作时不能提供当前节点的上一个节点遍历。

1. 用双向链表看成cache缓存, 数据存放在链表上的每个节点上。

在使用cache时，主要有2种操作，一种是向cache里添加数据, 另一种是从cache里获取数据。

对于get操作:

1) 如果map 里不存在，那么直接返回null。

2) 如果map里存在，找到将该节点移到到双向链表的表头。

对于put操作:

1) 先判断用上述的get操作获取到node, 如果node不存在，接着通过 history.size()==capcity 判断容量是否已满，如果满了，就将尾节点从map 中移除，同时清除掉双向链表中的尾节点，如果没有满，那么插入到Head节点和Head的next节点之间，Head节点不存储元素。

2) 如果node存在，那么就cache(双向链表) 中的对应的node移到链表头。

2. 用Map记录访问cache的历史, 只要访问了 cache就将节点放置Map里。

3. 图解移动节点和淘汰策略过程

断掉node节点：

node.pre.next=node.next

node.next.pre=node.pre

将node插入链表头, 因为head节点不存元素，所以是插入到head和head.next节点之间。

node.next=head.next

node.pre=head

head.next=node

head.next.pre=node

画一下图，我们就会发现双向链表的优点体现出来了

三、完整代码

package sort;import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;/*** @author bingbing* @date 2021/5/7 0007 9:58*/
public class LRUCache<V> {private int capacity = 1024;private static Map<String, Node> history = new ConcurrentHashMap<>();Node head;Node tail;public LRUCache(int capacity) {this();this.capacity = capacity;}public LRUCache() {head = new Node();tail = new Node();head.next = tail;head.pre = null;tail.pre = head;tail.next = null;}private V get(String key) {Node node = history.get(key);if (null == node) {return null;}// 将节点移动表头node.pre.next = node.next;node.next.pre = node.pre;node.next=head.next;head.next.pre=node;head.next=node;node.pre=head;return (V) node;}private void put(String key, V value) {Node node = history.get(key);if (null == node) {// 判断容量是否已满if (history.size() == capacity) {history.remove(tail.pre.key);tail.pre = tail.next;tail.next = null;tail = tail.pre;}}// 插入到表头node = (Node) value;history.put(key, node);node.next = head.next;head.next.pre = node;head.next = node;node.pre = head;}static class Node<k, v> {private k key;private v value;Node<k, v> pre;Node<k, v> next;public Node(k key, v value) {this.key = key;this.value = value;}public Node() {}}public static void main(String[] args) {LRUCache<Node> cache = new LRUCache<>(4);Node<String, Integer> node1 = new Node<String, Integer>("k1", 1);Node<String, Integer> node2 = new Node<String, Integer>("k2", 2);Node<String, Integer> node3 = new Node<String, Integer>("k3", 3);Node<String, Integer> node4 = new Node<String, Integer>("k4", 4);Node<String, Integer> node5 = new Node<String, Integer>("k5", 5);cache.put("k1", node1);cache.put("k2", node2);cache.put("k3", node3);cache.put("k4", node4);
//        cache.get("k1");cache.put("k5", node5);Node node = cache.get("k1");System.out.println(node);}}

效果演示:

1) 注释掉 cache.get("k1"), 从cache中拿k1, 查看结果

null

2) 放开 cache.get("k1"), 从cache中拿k1, 查看结果

sort.LRUCache$Node@14ae5a5

第一次的容量只有4，按照最少使用规则，那么就会淘汰k1, 因此第一次测试结果为null, 第二次测试因为重新获取了k1, k1被移到了头节点，淘汰的是k2, 因此能够拿到k1。

四、借助LinkedHashMap实现

LinkedHashMap有一个参数为acessOrder, 如果为true时，表示的是访问的时候，链表里的节点会重新排序。

    public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {super(initialCapacity, loadFactor);this.accessOrder = accessOrder;}

设置accessOrder参数为true，

      LinkedHashMap  lruItem = new LinkedHashMap<String, String>(16, 0.75f, true);

使用get方法先访问1，观察打印结果:

package com.bing.sh.cache;import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;import java.util.LinkedHashMap;public class LRUTest {Logger logger = LoggerFactory.getLogger(LRUTest.class);@Testpublic void testLRUCache() {LinkedHashMap<Integer, Integer> linkedHashMap = new LinkedHashMap<Integer, Integer>(16, 0.75F, true);linkedHashMap.put(1, 1);linkedHashMap.put(2, 2);linkedHashMap.put(3, 3);logger.info(linkedHashMap.get(1).toString());linkedHashMap.entrySet().forEach((key) -> {System.out.println(key);});}
}

1 放入到了末尾，我们可以将其倒置使用，就是一个LRU的实例了！

LRU的实现交给LinkedHashMap，LRU淘汰策略需要根据removeEldestEntry()方法为true时触发，LinkedHashMap的removeEledstEntry方法返回为False，因此我们只需要重写removeEldestEntry()方法，自定义剔除的条件，即可触发LRU策略。

    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {return false;}

我们在初始化的时候指定size 为capacity+1，size为map的实际初始化大小，如果 size> capacity 表示map已经放满了，需要开始触发LRU淘汰策略。

package com.bing.sh.core.collection.map;import java.util.LinkedHashMap;
import java.util.Map;public class FixedLinkedHashMap<K, V> extends LinkedHashMap<K, V> {/*** 容量，超过容量则自动删除末尾元素*/private int capacity;private static final long serialVersionUID = -1246833412990782934L;public FixedLinkedHashMap(int capacity) {super(capacity + 1, 1.0F, true);this.capacity = capacity;}public void setCapacity(int capacity) {this.capacity = capacity;}public int getCapacity() {return capacity;}@Overrideprotected boolean removeEldestEntry(Map.Entry<K, V> eldest) {return size() > this.capacity;}
}

触发的时候是在put()方法之后，可以跟踪源码, put 后会调用一个afterNodeInsertion方法:

    void afterNodeInsertion(boolean evict) { // possibly remove eldestLinkedHashMap.Entry<K,V> first;if (evict && (first = head) != null && removeEldestEntry(first)) {K key = first.key;removeNode(hash(key), key, null, false, true);}}

removeNode()方法，是先通过key和hash找到目标的node:

    final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {Node<K,V>[] tab; Node<K,V> p; int n, index;if ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {Node<K,V> node = null, e; K k; V v;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))node = p;else if ((e = p.next) != null) {if (p instanceof TreeNode)node = ((TreeNode<K,V>)p).getTreeNode(hash, key);else {do {if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {node = e;break;}p = e;} while ((e = e.next) != null);}}if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {if (node instanceof TreeNode)((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);else if (node == p)tab[index] = node.next;elsep.next = node.next;++modCount;--size;afterNodeRemoval(node);return node;}}return null;}

最终移除掉淘汰的节点node: