LRU算法就是一种缓存淘汰策略，全称为Least Recently Used。

算法描述

力扣第 146 题「LRU缓存机制」就是让你设计数据结构：

首先要接收一个 capacity 参数作为缓存的最大容量，然后实现两个 API，一个是 put(key, val) 方法存入键值对，另一个是 get(key) 方法获取 key 对应的 val，如果 key 不存在则返回 -1。

注意：get 和 put 方法必须都是 O(1) 的时间复杂度，我们举个具体例子来看看 LRU 算法怎么工作。

/* 缓存容量为2 */
     LRUCache cache = new LRUCache(2);
     // 将cache理解为一个队列，假设左边是队头，右边是队尾
     //最近使用的排在队头，久未使用的排在队尾
     //圆括号表示键值对（key，value）
     
     cache.put(1, 1);
     // cache = [(1,1)]
     
     cache.put(2, 2);
     // cache = [(2,2),(1,1)]
     
     cache.get(1);
     // 返回1
     // cache = [(1,1),(2,2)]
     
     cache.put(3, 3);
     //cache = [(3,3),(1,1)]
     //缓存容量已满，需要删除队尾的元素，然后把新的数据插入队头
     
     cache.get(2);
     //返回-1
     
     cache.put(1, 4);
     // cache = [(1,4),(3,3)]
     
     cache.get(1);
     //返回4

LRU算法设计

分析上面的操作过程，要让 put 和 get 方法的时间复杂度为 O(1)，我们可以总结出 cache 这个数据结构必要的条件：

1. cache中的元素必然有时序，以区分最近使用和久未使用的数据，当容量满了之后要删除最久未使用的那个元素；
2. 我们要在cache中快速找某个key是否已存在，并得到对应的val；
3. 每次访问 cache 中的某个 key，需要将这个元素变为最近使用的，也就是说 cache 要支持在任意位置快速插入和删除元素；

综上所述，哈希表查找速度快，但是数据无固定顺序；链表有顺序之分，插入删除快，但是查找慢，两者结合形成一种新的数据结构：哈希链表LinkedHashMap。

LRU缓存算法的核心数据结构就是哈希链表，如下所示：

借助这个结构，我们来逐一分析上面的 3 个条件：

1、如果我们每次默认从链表尾部添加元素，那么显然越靠尾部的元素就是最近使用的，越靠头部的元素就是最久未使用的。

2、对于某一个 key，我们可以通过哈希表快速定位到链表中的节点，从而取得对应 val。

3、链表显然是支持在任意位置快速插入和删除的，改改指针就行。只不过传统的链表无法按照索引快速访问某一个位置的元素，而这里借助哈希表，可以通过 key 快速映射到任意一个链表节点，然后进行插入和删除。

代码实现

首先，把双链表的节点类写出来，为了简化，key 和 val 都认为是 int 类型：

class Node {
    public int key, val;
    public Node next, prev;
    public Node(int k, int v) {
        this.key = k;
        this.val = v;
    }
}

然后依靠我们的Node类型构建一个双链表，实现几个LRU算法必须的API：

private class DoubleList {
       /**
        *头尾虚节点
        */
       private Node head,tail;

       /**
        * 链表元素数
        */
       private int size;

       public DoubleList() {
           // 初始化双向链表的数据
           head = new Node(0,0);
           tail = new Node(0,0);
           head.next = tail;
           tail.prev = head;
           size = 0;
       }

       /**
        * 在链表头部添加节点x
        */
       public void addFirst(Node x){
           x.next = head.next;
           x.prev = head;
           head.next.prev = x;
           head.next = x;
           size++;
       }

       /**
        * 删除链表中的x节点(x一定存在)
        */
       public void remove(Node x){
           x.next.prev = x.prev;
           x.prev.next = x.next;
           size--;
       }

       /**
        * 删除链表中最后一个节点，并返回该节点
        */
       public Node removeLast(){
           if(tail.prev == head){
               return null;
           }
           Node last = tail.prev;
           remove(last);
           return last;
       }

       /**
        * 返回链表长度
        */
       public int size(){
           return size;
       }
   }

为什么需要双向链表？

因为我们需要删除操作，删除一个节点不光要得到该节点本身的指针，也需要操作其前驱节点的指针，而双向链表才能支持查找前驱，保证操作的时间复杂度O(1)。

注意：我们实现的双链表API只能从头部插入，也就是说靠头部的数据是最近使用的，靠尾部的数据是最久未使用的。

有了双向链表的实现，我们只需要在LRU算法中把它和哈希表结合起来即可，先搭出代码框架：

public class LRUCache{
   private HashMap<Integer, Node> map;
   private DoubleList cache;
    /**
     * 容量
     */
   private int cap;

    public LRUCache(int cap) {
        this.cap = cap;
        map = new HashMap<>();
        cache = new DoubleList();
    }

先不着急去实现LRU算法的get和put方法，由于我们要同时维护一个双链表cache和一个哈希表map，很容易漏掉一些操作，比如说删除某个key时，在cache中删除了对应的Node，但是却忘记在map中删除key。

解决这种问题最好的办法是：在这两种数据结构之上提供一层抽象API。

/** 将某个key提升为最近使用的 */
    private void makeRecently(int key){
       Node r = map.get(key);
       //先从链表中删除该节点
       cache.remove(r);
       //然后在链表头部添加该节点
       cache.addFirst(r);
    }

    /** 添加最近使用的元素 */
    private void addRecently(int key,int val){
        Node r = new Node(key,val);
        cache.addFirst(r);
        //在map中添加映射关系
        map.put(key,r);
    }

    /** 删除某一个key */
    private void deleteKey(int key){
        Node r = map.get(key);
        cache.remove(r);
        map.remove(r);
    }

    /** 删除最久未使用的元素 */
    private void removeLeastRecently(){
        Node r = cache.removeLast();
        //删除map中的对应关系
        int key = r.key;
        map.remove(key);
    }

当缓存容量满时，我们除了要删除最后一个Node节点外，还要把map中映射到该节点的key同时删除，而这个key只能由Node得到。

下面实现get和put方法。

public int get(int key){
     if(!map.containsKey(key)){
         return -1;
     }
     //将该数据提升为最近使用的
     makeRecently(key);
     return map.get(key).val;
 }
 
 public void put(int key,int val){
     if(map.containsKey(key)){
         //先删除掉旧的数据
         deleteKey(key);
     }
     if(cap == cache.size){
         //删除最久未使用的数据
         removeLeastRecently();
     }
     //新插入的数据为最近使用的数据
     addRecently(key,val);
 }