LRU 介绍
    LRU 是 Least Recently Used 的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。

    面试中常考的题目，运用你所掌握的数据结构，自己设计手写 LRU 算法。

    相关题目可参考 LeetCode146 题

    一。使用 LinkedHashMap 实现
    在 Java 中，其实 LinkedHashMap 已经实现了 LRU 缓存淘汰算法，需要在构造函数第三个参数传入 true，表示按照时间顺序访问。可以直接继承 LinkedHashMap 来实现。

    但是 LinkedHashMap 会自动扩容，如果想实现限制容量删除队列顶端元素，需要重写 removeEldestEntry () 方法，当 map 里面的元素个数大于了缓存最大容量，删除链表的顶端元素。

    public class LRULinkedHashMap extends LinkedHashMap {

    1. private int capacity;
    3. LRULinkedHashMap(int capacity) {
    4.     // 初始大小，0.75是装载因子，true是表示按照访问时间排序
    5.     super(capacity, 0.75f, true);
    6.     //传入指定的缓存最大容量
    7.     this.capacity = capacity;
    8. }
    10. /**
    11.  * 实现LRU的关键方法，如果map里面的元素个数大于了缓存最大容量，则删除链表的顶端元素
    12.  */
    13. @Override
    14. protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
    15.     return size() > capacity;
    16. }

    }
    二。使用 LinkedList+HashMap 实现
    也可以使用 LinkedList 和 HashMap 实现，但时间复杂度较高。使用 HashMap 可以通过 O (1) 时间拿到元素，但是无法在 O (1) 时间定位它在链表中的位置，在 LinkedList 里访问元素仍然是顺序遍历，所以删除元素的时间复杂度仍然是 O (n)。并不是高效的 Lru 算法。

    因为从 HashMap 中删除元素需要 Key，所以这里在链表中存放 Key 而不是 Value。

    public class LRUCacheBeta {
    int capacity;
    Map map;
    LinkedList list;

    1. public LRUCacheBeta(int capacity) {
    2.     this.capacity = capacity;
    3.     this.map = new HashMap<>();
    4.     this.list = new LinkedList<>();
    5. }
    7. /**
    8.  * 添加元素
    9.  * 1.元素存在，放到队尾
    10.  * 2.不存在，判断链表是否满。
    11.  * 如果满，则删除队首元素，放入队尾元素，删除更新哈希表
    12.  * 如果不满，放入队尾元素，更新哈希表
    13.  */
    14. public void put(K key, V value) {
    15.     V v = map.get(key);
    16.     if (v != null) {
    17.         list.remove(key);
    18.         list.addLast(key);
    19.         map.put(key, value);
    20.         return;
    21.     }
    23.     //队列未满，添加到尾部
    24.     if (list.size() < capacity) {
    25.         list.addLast(key);
    26.         map.put(key, value);
    27.     } else {
    28.         //队列已满，移除队首
    29.         K firstKey = list.removeFirst();
    30.         map.remove(firstKey);
    31.         list.addLast(key);
    32.         map.put(key, value);
    33.     }
    34. }
    36. /**
    37.  * 访问元素
    38.  * 元素存在，放到队尾
    39.  */
    40. public V get(K key) {
    41.     V v = map.get(key);
    42.     if (v != null) {
    43.         list.remove(key);
    44.         list.addLast(key);
    45.         return v;
    46.     }
    47.     return null;
    48. }

    }
    三。使用双向链表结构 + HashMap 实现
    在方法二中，删除操作的时间复杂度仍是 O (n)，那么如何使其复杂度降为 O (1)？我们可以自定义双向链表的结构，这里定义了内部类 Node，存放 KV 以及前后指针。这样我们通过 hashmap 找到对应 Node，然后根据其前驱节点进行指针的操作，就可以实现复杂度 O (1) 的删除操作。

    同样因为访问 HashMap 需要 key，所以定义 Node 节点存放了 K 和 V，而不是只存放 V。保存队列的头节点和尾节点。

    在代码中，我们通过调整指针，定义了三个方法，分别是添加元素到队尾，将队列中元素移动到队尾，删除队列头节点并返回，因为是双向链表，特别注意指针变换的顺序以及不要遗漏前驱和后继指针。

    public class LRUCache {
    private int size;
    private HashMap map;
    private Node head;
    private Node tail;

    1. LRUCache(int size) {
    2.     this.size = size;
    3.     map = new HashMap<>();
    4. }
    6. /**
    7.  * 添加元素
    8.  * 1.元素存在，将元素移动到队尾
    9.  * 2.不存在，判断链表是否满。
    10.  * 如果满，则删除队首元素，放入队尾元素，删除更新哈希表
    11.  * 如果不满，放入队尾元素，更新哈希表
    12.  */
    13. public void put(K key, V value) {
    14.     Node node = map.get(key);
    15.     if (node != null) {
    16.         //更新值
    17.         node.v = value;
    18.         moveNodeToTail(node);
    19.     } else {
    20.         Node newNode = new Node(key, value);
    21.         //链表满，需要删除首节点
    22.         if (map.size() == size) {
    23.             Node delHead = removeHead();
    24.             map.remove(delHead.k);
    25.         }

    作者：icecrea
    链接：https://leetcode-cn.com/problems/lru-cache/solution/san-chong-fang-fa-dai-ni-shou-si-lrusuan-fa-javaba/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。