前言

在使用缓存时，由于缓存容量有限，当缓存容量到达上限，就需要删除部分数据挪出空间。但是缓存数据不能随机删除，一般情况下需要根据某种算法删除缓存数据。

常用的淘汰算法有LRU, LFU, FIFO，本篇介绍LRU算法并重点讲述LRU的实现。完整代码也是LeetCode 146. LRU缓存的答案。

LRU 简介

LRU是Least recently used的缩写，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。当缓存容量满的时候，优先淘汰最近最少被使用的数据。

根据以上策略，给出使用LRU淘汰算法时的示例。

LRU淘汰算法示例

通过上图可以看到LRU算法的具体步骤是：

新数据直接插入到列表头部
缓存数据被命中，将数据移动到链表头部
缓存已满，移除列表尾部数据。

LRU 算法实现

上面看到LRU算法需要添加头节点，删除尾节点。而链表添加/删除节点的时间复杂度为O(1)，但这里不能使用普通的单向链表，原因在于：

虽然单向链表添加/删除/移动元素比较方便，但是再查询元素时的时间复杂度为O(N)
移动中间节点到头节点需要知道前一个节点和后一个节点的信息，单向链表就不得不再次遍历获取信息。

针对以上问题的解决方案是：

使用散列表存储节点，获取节点的复杂度将为O(1)，
使用双向链表用来获得前驱节点的信息。

LRU数据结构

在这里，增加了两个【哨兵】节点，不用来存储任何数据，目的是再增加、删除结点的时候不用考虑节点不存在的情况。简化编程难度。

在算法实现的过程中，我发现LeetCode 146是类似的题目，故把该题直接拿来使用。

该题的算法签名是

class LRUCache {
    public int get(int key) {
    }

    public void put(int key, int value) {
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

通过调用put\get方法实现存取缓存的目的。下面是对代码的逐步分析。

双向链表数据结构

这里使用一个内部类作为双向链表的数据结构。比较简单，直接给出代码。

   //定义一个内部类，作为缓存列表
public static class Entry{
       public Entry pre; //指向前驱的指针
       public Entry next; //指向后继的指针
       public int key; //缓存的key
       public int value; //缓存的value

       public Entry(int key, int value) {
           this.key = key;
           this.value = value;
       }
       public Entry() {
       }
   }

定义成员变量和构造函数

private Entry head, tail; //头尾两个哨兵节点
private int capacity; // 容量
int size; //当前缓存大小
Map<Integer, Entry> cache; //缓存散列表

public LRUCache(int capacity) {
    this.capacity = capacity;
    //初始化操作
    initLinkedList();
    size = 0;
    cache = new HashMap<>();
}

初始化操作函数initLinkedList()的实现是将head和tail通过指针连接起来。

private void initLinkedList() {
       head = new Entry();
       tail = new Entry();

       head.next = tail;
       tail.pre = head;
   }

put操作

put操作可以分三种情况：

如果key已经存在与缓存中，则将key对应的节点移动到链表头部，并重设value
如果key在缓存中不存在，那么检查缓存是否已满
1. 如果未满，就直接将新节点加入到链表头部
2. 如果已满，就先删除尾节点，再将新节点加入到链表头部

public void put(int key, int value) {
    Entry node = cache.get(key);
    //如果key在缓存中已经存在，则移动到头部
    if(node != null) {
        node.value = value;
        move2Head(node);
        return ;
    }
    //容量已满先删除尾节点
    if(size == capacity) {
        Entry lastNode = tail.pre;
        deleteNode(lastNode);
        cache.remove(lastNode.key);
        size --;
    }

    //add new Node
    Entry newNode = new Entry();
    newNode.key = key;
    newNode.value = value;
    addNode(newNode);
    cache.put(key, newNode);
    size ++;
}

对于move2Head操作，无非是先删除原来的节点关系deleteNode，再添加到队列头部addNode

而deleteNode和addNode是比较基础的双向链表操作，这里就不再做过多解释。

private void addNode(Entry node) {
    head.next.pre = node;
    node.next = head.next;

    node.pre = head;
    head.next = node;
}

private void deleteNode(Entry node) {
    node.pre.next = node.next;
    node.next.pre = node.pre;
}

private void move2Head(Entry node) {
    //删除原来的节点关系
    deleteNode(node);
    addNode(node);
}

get 操作

当key不在缓存中，返回-1，当key存在于缓存时，就将该元素移动到链表头部，并返回对应的value。

public int get(int key) {
       Entry node = cache.get(key);
       if(node == null) {
           return -1;
       }
       move2Head(node);
       return node.value;
   }

完整代码

class LRUCache {
    private Entry head, tail;
    private int capacity; // 容量
    int size;
    Map<Integer, Entry> cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        //初始化操作
        initLinkedList();
        size = 0;
        cache = new HashMap<>(capacity + 2); //这里为什么要+2
    }

    private void initLinkedList() {
        head = new Entry();
        tail = new Entry();

        head.next = tail;
        tail.pre = head;
    }


    public int get(int key) {
        Entry node = cache.get(key);
        if(node == null) {
            return -1;
        }
        move2Head(node);
        return node.value;
    }

    /**
     * 将节点插入到头节点，如果容量已满，则会删除尾节点
     */
    public void put(int key, int value) {
        Entry node = cache.get(key);
        //如果key在缓存中已经存在，则移动到头部
        if(node != null) {
            node.value = value;
            move2Head(node);
            return ;
        }
        //容量已满先删除尾节点
        if(size == capacity) {
            Entry lastNode = tail.pre;
            deleteNode(lastNode);
            cache.remove(lastNode.key);
            size --;
        }

        //add new Node
        Entry newNode = new Entry();
        newNode.key = key;
        newNode.value = value;
        addNode(newNode);
        cache.put(key, newNode);
        size ++;
    }

    private void addNode(Entry node) {
        head.next.pre = node;
        node.next = head.next;

        node.pre = head;
        head.next = node;
    }

    private void deleteNode(Entry node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    private void move2Head(Entry node) {
        //删除原来的节点关系
        deleteNode(node);
        addNode(node);
    }

    //定义一个内部类，作为缓存链表
    public static class Entry{
        public Entry pre; //指向前驱的指针
        public Entry next; //指向后继的指针
        public int key; //缓存的key
        public int value; //缓存的value

        public Entry(int key, int value) {
            this.key = key;
            this.value = value;
        }
        public Entry() {
        }
    }
}