参考https://zhuanlan.zhihu.com/p/75390654

LRU: Least Recently Used.最近最少使用(也有说最远最少使用或最久未使用，都对，看怎么理解。总而言之就是给元素一个“热度值”，对元素的操作会给其“添加热度”，在容器满了之后，再次添加时，删除掉“热度最低”的那个)

题目：

实现 LRUCache 类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key，value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

注意：get(key)操作会”使用key”，put()已经存在的key也会”使用key”。凡是“使用key”都会给key添加热度。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

  1. LRUCache lRUCache = new LRUCache(2);
  2. lRUCache.put(1, 1); // 缓存是 {1=1}
  3. lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
  4. lRUCache.get(1);    // 返回 1
  5. lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
  6. lRUCache.get(2);    // 返回 -1 (未找到)
  7. lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
  8. lRUCache.get(1);    // 返回 -1 (未找到)
  9. lRUCache.get(3);    // 返回 3
  10. lRUCache.get(4);    // 返回 4

来源：力扣（LeetCode）

实现1

分析：

要想O(1)时间复杂度存取元素，大概率是使用HashMap；而元素热度会变化，超出容量时低热度元素被挤掉，则可以使用链表来维护元素位置。

思路：

使用 双向链表 + HashMap实现。双向链表维护元素热度，HashMap储存元素。热度的维护靠移动元素到头部来实现，这样尾部自然就是热度最低的元素；那些会增加元素热度的操作，一律会将元素移动到头部；容量不够了，去尾部删除就行了。

代码：

  1. package com.example.demo.core.Leecode;
  3. import java.util.HashMap;
  6. /**
  7.  * https://leetcode-cn.com/problems/lru-cache/
  8.  *
  9.  * LRU: Least Recently Used.最近最少使用
  10.  * 双向链表 + HashMap，双向链表维护元素热度，HashMap储存元素
  11.  * 维护热度就需要有 添加元素到头部，移动元素到头部，移除尾部元素 的操作；其中，移动元素到头部可以使用删除元素和添加元素到头部两个方法实现。所以底层基本操作要有3个（添加元素到头部、删除当前元素、移除尾部元素）。
  12.  * @author hanxu03
  13.  */
  14. public class LRUCache {
  16.     /**
  17.      * 双向链表节点
  18.      */
  19.     class Node {
  20.         int key;
  21.         int value;
  22.         Node before;
  23.         Node after;
  25.         public Node() {
  26.         }
  28.         public Node(int key, int value) {
  29.             this.key = key;
  30.             this.value = value;
  31.         }
  32.     }
  34.     /**
  35.      * 真实储存数据的容器
  36.      */
  37.     private HashMap<Integer, Node> cache = new HashMap<>();
  39.     /**
  40.      * 容量
  41.      */
  42.     private int capacity;
  44.     /**
  45.      * 头尾指针，并不储存元素。第一个节点的前面是head，最后一个节点的后面是tail
  46.      */
  47.     private Node head, tail;
  50.     /**
  51.      * 初始化
  52.      * @param capacity
  53.      */
  54.     public LRUCache(int capacity) {
  55.         //赋值容量
  56.         this.capacity = capacity;
  57.         //创建头尾指针
  58.         head = new Node();
  59.         head.before = null;
  60.         tail = new Node();
  61.         tail.after = null;
  62.         //连接头尾结点
  63.         head.after = tail;
  64.         tail.before = head;
  65.     }
  67.     /**
  68.      * 插入节点到链表头部
  69.      * @return
  70.      */
  71.     private void addToHead(Node node) {
  72.         //只知道node应该在head后面，不知道node后面是啥，所以操作时只能使用head与node
  73.         node.before = head;
  74.         node.after = head.after;
  75.         //顺讯不能调换
  76.         head.after.before = node;
  77.         head.after = node;
  78.     }
  81.     /**
  82.      * 移除双向链表中的某个节点
  83.      * @param node
  84.      */
  85.     private void removeNode(Node node) {
  86.         Node before = node.before;
  87.         Node after = node.after;
  88.         before.after = after;
  89.         after.before = before;
  90.     }
  93.     /**
  94.      * 将某节点移动到双向链表头部（head后）
  95.      * @param node
  96.      */
  97.     private void moveToHead(Node node) {
  98.         //删除当前位置
  99.         removeNode(node);
  100.         //添加到head后
  101.         addToHead(node);
  102.     }
  105.     /**
  106.      * 删除尾部节点（tail前）
  107.      * @return
  108.      */
  109.     private Node delTail() {
  110.         //获取，删除，返回
  111.         Node node = tail.before;
  112.         removeNode(node);
  113.         return node;
  114.     }
  117.     public int get(int key) {
  118.         Node node = cache.get(key);
  119.         if (node == null) {
  120.             return -1;
  121.         }
  122.         //加热元素（移到头部）
  123.         moveToHead(node);
  124.         return node.value;
  125.     }
  128.     public void put(int key, int value) {
  129.         // (注意判定顺序不能弄混)
  130.         // 1、判断是不是新node：是就添加，不是就更新
  131.         //     2、判断添加后是否超出容量：是就移除尾部元素
  132.         Node node = cache.get(key);
  133.         //如果是新Node
  134.         if (node == null) {
  135.             Node newNode = new Node(key, value);
  136.             //新来的都是最热的（放在头部）
  137.             addToHead(newNode);
  138.             cache.put(key, newNode);
  139.             //如果添加后容量超出，则弹出尾部元素
  140.             if (cache.size() > capacity) {
  141.                 Node lastNode = delTail();
  142.                 cache.remove(lastNode.key);
  143.             }
  144.         } else {
  145.             //不是新Node就替换vale，并加热元素（放到链表前面）
  146.             node.value = value;
  147.             moveToHead(node);
  148.         }
  149.     }
  152.     public static void main(String[] args) {
  153.         LRUCache lruCache = new LRUCache(2);
  154.         lruCache.put(1, 1);
  155.         lruCache.put(2, 2);
  156.         System.out.println(lruCache.get(1)); // 1
  157.         lruCache.put(3, 3); //
  158.         System.out.println(lruCache.get(2)); // -1
  159.         lruCache.put(4, 4);
  160.         System.out.println(lruCache.get(1)); // -1
  161.         System.out.println(lruCache.get(3)); // 3
  162.         System.out.println(lruCache.get(4)); // 4
  163.     }
  164. }

实现2

思路：

JDK中的LinkedHashMap，可以实现元素按照访问顺序倒叙输出：（先访问的最后迭代出来，就是把先访问的放在后面）

注意，第三个入参accessOrder需要为true才能实现这个效果。

  1.     public static void main(String[] args) {
  2.         LinkedHashMap<Object, Object> linkedHashMap = new LinkedHashMap<>(2, 0.75F, true);
  3.         linkedHashMap.put(1, 1);
  4.         linkedHashMap.put(2, 2);
  5.         linkedHashMap.get(1);
  6.         linkedHashMap.put(3, 3);
  7.         linkedHashMap.put(4, 4);
  8.         System.out.println(linkedHashMap);
  9.         /*
  10.         头部  ---->  尾部
  11.         本来是 1,1 2,2
  12.         当get(1)时，会把1,1放在尾部
  13.         变成了 2,2 1,1   再放入3,3 4,4
  14.         变成了 2,2 1,1 3,3 4,4
  15.         输出时从头部到尾部输出
  16.          */
  17.         //{2=2, 1=1, 3=3, 4=4}
  18.     }

LinkedHashMap继承HashMap，HashMap的putVal方法在添加元素后，又会执行一个afterNodeInsertion(evict);方法，这个方法就是添加元素之后做的事情。它在HashMap中是一个空方法，子类可以实现它。

  1. void afterNodeInsertion(boolean evict) { }

而LinkedHashMap的实现是这样的：

  1.     void afterNodeInsertion(boolean evict) { // possibly remove eldest
  2.         LinkedHashMap.Entry<K,V> first;
  3.         if (evict && (first = head) != null && removeEldestEntry(first)) {
  4.             K key = first.key;
  5.             removeNode(hash(key), key, null, false, true);
  6.         }
  7.     }

当满足(evict && (first = head) != null && removeEldestEntry(first))这些条件时，会将头部元素删除（removeNode(hash(key), key, null, false, true)）。

我们想一下，尾部元素是最近常访问的，那头部元素自然就是最近不常访问的了，所以删除头部元素刚好能满足我们的诉求。

接下来的问题就是什么时候删，总不能每次添加元素都把尾部删除吧。我们来看这个条件：

evict传过来就是true，有元素时head!=null，剩下的就是removeEldestEntry(first)了。我们的诉求是当空间不够时删除尾部元素。所以我们只需要控制removeEldestEntry这个方法，当空间不够时返回true即可！

  1.     @Override
  2.     protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
  3.         return size() > capacity;
  4.     }

总结一下这个实现思路：LinkedHashMap可以控制元素按照访问顺序倒叙遍历（内部将常访问的元素放在尾部），又有一个方法afterNodeInsertion可以在添加元素后干一些事情，而LinkedHashMap的实现就是删除头部元素，所以我们可以自由定制我们要在什么条件下删除那些元素。

代码：

  1. package com.example.demo.core.Leecode;
  3. import java.util.LinkedHashMap;
  4. import java.util.Map;
  6. /**
  7.  * @author: HanXu
  8.  * on 2022/2/24
  9.  * Class description: JDK中的LinkedHashMap实现LRU
  10.  */
  11. public class LRUCache2 extends LinkedHashMap<Integer, Integer> {
  13.     private int capacity;
  15.     public LRUCache2(int capacity) {
  16.         //这里必须为true
  17.         super(capacity, 0.75F, true);
  18.         this.capacity = capacity;
  19.     }
  21.     public int get(int key) {
  22.         return super.getOrDefault(key, -1);
  23.     }
  25.     public void put(int key, int value) {
  26.         super.put(key, value);
  27.     }
  29.     /**
  30.      * 这个必须有，控制添加元素后，哪些情况下删除头部元素
  31.      * @param eldest
  32.      * @return
  33.      */
  34.     @Override
  35.     protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
  36.         return size() > capacity;
  37.     }
  39.     public static void main(String[] args) {
  40.         LRUCache2 lruCache2 = new LRUCache2(2);
  41.         lruCache2.put(1, 1);
  42.         lruCache2.put(2, 2);
  43.         System.out.println(lruCache2.get(1)); // 1
  44.         lruCache2.put(3, 3); //
  45.         System.out.println(lruCache2.get(2)); // -1
  46.         lruCache2.put(4, 4);
  47.         System.out.println(lruCache2.get(1)); // -1
  48.         System.out.println(lruCache2.get(3)); // 3
  49.         System.out.println(lruCache2.get(4)); // 4
  50.     }
  51. }

为什么需要双向链表+hashMap？

使用其他数据结构能实现吗？可以。只不过双向链表+hasMap是相对最优解。
这里的双向链表能换成单向链表吗？能，就算只使用单向链表也是可以的。
但如果换成单向链表，删除node节点时，就需要从前向后遍历，拿到node的前驱节点，才能删除；而双向链表，则可以直接获得node的前驱节点。双向链表+hashMap，所有操作时间复杂度都趋向于O(1)。