什么是LRU？LRU是什么？

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

当你看到这篇文章我就当你有了一定的基础，看过其他LRU的介绍博客了

网友：想了半天终于想明白了为啥要用hashmap和双向链表，

<1>首先我想的是用队列不行吗？

不行，队列只能做到先进先出，但是重复用到中间的数据时无法把中间的数据移动到顶端。

<2> 就用单链表不行吗？

单链表能实现新来的放头部，最久不用的在尾部删除，但删除的时候需要遍历到尾部，因为单链表只有头指针。在用到已经用到过的数据时，还要遍历整合链表，来确定是否用过，然后再遍历到响应位置来剔除的节点，并重新放在头部。这效率可想而知。

这时hashmap的作用就出来了， 它可以在单位的时间判断value的值是否存在，key直接存储节点对象，能直接定位删除对应的节点(将比节点的父节点指向子节点)。要通过一个节点直接获得父节点的话，通过单链表是不行的。
这时双向链表的作用也提现出来了。能直接定位到父节点。 这效率就很高了。而且由于双向链表有尾指针，所以剔除最后的尾节点也十分方便，快捷。

下面的代码就是双向链表和HashMap实现的：

  1. package com.company.test01;
  3. import java.util.Map;
  4. import java.util.concurrent.ConcurrentHashMap;
  6. /**
  7.  * @ClassName : LRUCache  //类名
  8.  * @Description : LRU  //描述
  9.  * @Author : Mr.Duan  //作者
  10.  * @Date: 2020-08-13 08:57  //时间
  11.  */
  12. public class LRUCache<V> {
  14.     private int capacity=1024;//容量
  15.     private final Map<String, ListNode<String, V>> table = new ConcurrentHashMap<>();//记录Node
  16.     private final ListNode<String, V> head;
  17.     private final ListNode<String, V> tail;
  18.     public LRUCache(int capacity) {
  19.         this();
  20.         this.capacity = capacity;
  21.     }
  22.     public LRUCache() {
  23.         head = new ListNode<>();
  24.         tail = new ListNode<>();
  25.         head.next = tail;
  26.         head.prev = null;
  27.         tail.prev = head;
  28.         tail.next = null;
  29.     }
  30.     public void get(String key) {
  32.         ListNode<String, V> node = table.get(key);
  33.         //如果Node不在表中，代表缓存中并没有
  34.         if (node == null) {
  35.             return;
  36.         }
  37.         //如果存在，则需要移动Node节点到表头
  40.         //截断链表，node.prev -> node  -> node.next ====> node.prev -> node.next
  41.         //         node.prev <- node <- node.next  ====>  node.prev <- node.next
  42.         node.prev.next = node.next;
  43.         node.next.prev = node.prev;
  45.         //移动节点到表头
  46.         node.next = head.next;
  47.         head.next.prev = node;
  48.         node.prev = head;
  49.         head.next = node;
  50.         //存在缓存表
  51.         table.put(key, node);
  52.     }
  54.     @Override
  55.     public String toString() {
  56.         return "{" +
  57.                 "capacity=" + capacity +
  58.                 ", table=" + table +
  59.                 '}'+"\n";
  60.     }
  62.     public void put(String key, V value) {
  63.         ListNode<String, V> node = table.get(key);
  64.         //如果Node不在表中，代表缓存中并没有
  65.         if (node == null) {
  66.             if (table.size() == capacity) {
  67.                 //超过容量了 ,首先移除尾部的节点
  68.                 table.remove(tail.prev.key);//移除尾节点的上一个节点
  69.                 tail.prev.prev.next = tail;//尾部的上上个节点的下个节点设置为尾节点
  70.                 tail.prev = tail.prev.prev;//尾部的上个节点设置为尾部的上上个节点
  71.             }
  72.             node = new ListNode<>();
  73.             node.key = key;
  74.             node.value = value;
  75.             table.put(key, node);
  76.         }
  77.         //如果存在，则需要移动Node节点到表头
  78.         node.next = head.next;
  79.         head.next.prev = node;
  80.         node.prev = head;
  81.         head.next = node;
  84.     }
  85.     /**
  86.      * 双向链表内部类
  87.      */
  88.     public static class ListNode<K, V> {
  89.         private K key;
  90.         private V value;
  91.         ListNode<K, V> prev;
  92.         ListNode<K, V> next;
  94.         public ListNode(K key, V value) {
  95.             this.key = key;
  96.             this.value = value;
  97.         }
  100.         public ListNode() {
  102.         }
  104.         @Override
  105.         public String toString() {
  106.             return "{" +
  107.                     "key=" + key +
  108.                     ", value=" + value +
  109.                     '}'+"\n";
  110.         }
  111.     }
  112.     public static void main(String[] args) {
  113.         LRUCache<ListNode> cache = new LRUCache<>(4);
  114.         ListNode<String, Integer> node1 = new ListNode<>("key1", 1);
  115.         ListNode<String, Integer> node2 = new ListNode<>("key2", 2);
  116.         ListNode<String, Integer> node3 = new ListNode<>("key3", 3);
  117.         ListNode<String, Integer> node4 = new ListNode<>("key4", 4);
  118.         ListNode<String, Integer> node5 = new ListNode<>("key5", 5);
  119.         cache.put("key1", node1);
  120.         System.out.println("插入了："+node1);
  121.         System.out.println(cache);
  122.         cache.put("key2", node2);
  123.         System.out.println("插入了："+node2);
  124.         System.out.println(cache);
  125.         cache.put("key3", node3);
  126.         System.out.println("插入了："+node3);
  127.         System.out.println(cache);
  128.         cache.put("key4", node4);
  129.         System.out.println("插入了："+node4);
  130.         System.out.println(cache);
  131.         cache.get("key2");
  132.         System.out.println("获取了："+node2);
  133.         System.out.println(cache);
  134.         cache.put("key5", node5);
  135.         System.out.println("插入了："+node5);
  136.         System.out.println(cache);
  137.         cache.get("key2");
  138.         System.out.println("获取了："+node2);
  139.         System.out.println(cache);
  140.     }
  141. }

（注意：上面代码为了方便观察表的变化重写了类中的toString（）方法和main中的打印语句，正常状况下是没有的）代码运行结果如下：

  1. "D:\Program Files\Java\jdk1.8.0_144\bin\java.exe" "-javaagent:D:\IntelliJ IDEA 2020.1\lib\idea_rt.jar=52888:D:\IntelliJ IDEA 2020.1\bin" -Dfile.encoding=UTF-8 -classpath "D:\Program Files\Java\jdk1.8.0_144\jre\lib\charsets.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\deploy.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\ext\access-bridge-64.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\ext\cldrdata.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\ext\dnsns.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\ext\jaccess.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\ext\jfxrt.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\ext\localedata.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\ext\nashorn.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\ext\sunec.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\ext\sunjce_provider.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\ext\sunmscapi.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\ext\sunpkcs11.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\ext\zipfs.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\javaws.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\jce.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\jfr.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\jfxswt.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\jsse.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\management-agent.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\plugin.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\resources.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\rt.jar;E:\IdeaProjects\20200813\ClassDome\out\production\ClassDome" com.company.test01.LRUCache
  2. 插入了：{key=key1, value=1}
  4. {capacity=4, table={key1={key=key1, value={key=key1, value=1}
  5. }
  6. }}
  8. 插入了：{key=key2, value=2}
  10. {capacity=4, table={key1={key=key1, value={key=key1, value=1}
  11. }
  12. , key2={key=key2, value={key=key2, value=2}
  13. }
  14. }}
  16. 插入了：{key=key3, value=3}
  18. {capacity=4, table={key1={key=key1, value={key=key1, value=1}
  19. }
  20. , key2={key=key2, value={key=key2, value=2}
  21. }
  22. , key3={key=key3, value={key=key3, value=3}
  23. }
  24. }}
  26. 插入了：{key=key4, value=4}
  28. {capacity=4, table={key1={key=key1, value={key=key1, value=1}
  29. }
  30. , key2={key=key2, value={key=key2, value=2}
  31. }
  32. , key3={key=key3, value={key=key3, value=3}
  33. }
  34. , key4={key=key4, value={key=key4, value=4}
  35. }
  36. }}
  38. 获取了：{key=key2, value=2}
  40. {capacity=4, table={key1={key=key1, value={key=key1, value=1}
  41. }
  42. , key2={key=key2, value={key=key2, value=2}
  43. }
  44. , key3={key=key3, value={key=key3, value=3}
  45. }
  46. , key4={key=key4, value={key=key4, value=4}
  47. }
  48. }}
  50. 插入了：{key=key5, value=5}
  52. {capacity=4, table={key2={key=key2, value={key=key2, value=2}
  53. }
  54. , key5={key=key5, value={key=key5, value=5}
  55. }
  56. , key3={key=key3, value={key=key3, value=3}
  57. }
  58. , key4={key=key4, value={key=key4, value=4}
  59. }
  60. }}
  62. 获取了：{key=key2, value=2}
  64. {capacity=4, table={key2={key=key2, value={key=key2, value=2}
  65. }
  66. , key5={key=key5, value={key=key5, value=5}
  67. }
  68. , key3={key=key3, value={key=key3, value=3}
  69. }
  70. , key4={key=key4, value={key=key4, value=4}
  71. }
  72. }}
  75. Process finished with exit code 0