1. 定义

LRU是Least Recentily Used的缩写，即最近最少使用。是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。

2. 算法描述

借用LeetCode第146题的描述，该题就是让实现一个LRUCache类。

实现LRUCache类:

• LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1。
• void put(int key, int value)如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

要求在O(1)的时间复杂度内完成get和put操作。

示例:

LRUCache lRUCache = new LRUCache(2);
// 你可以把 lRUCache 理解成一个队列
// 假设左边是队头，右边是队尾
// 最近使用的排在队头，久未使用的排在队尾
// 圆括号表示键值对 (key, val)

lRUCache.put(1, 1);
//缓存是 {1=1}

lRUCache.put(2, 2);
//缓存是 {2=2, 1=1}

lRUCache.get(1)
// 返回 1

lRUCache.put(3, 3)
// 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}

lRUCache.get(2)
// 返回 -1 (未找到)

lRUCache.put(4, 4)
// 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}

lRUCache.get(1);
// 返回 -1 (未找到)

lRUCache.get(3);    
// 返回 3

lRUCache.get(4);    
// 返回 4

3. 算法设计

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

• lRUCache中的数据必须是有序的，最近使用的在队头，当队列满了之后，就删除队尾的元素。
• 在lRUCache中要根据指定key，得到对应的val。
• 每次调用lRUCache.get(key)方法时，要将查询到的元素，更新到队头。

首先要让元素有序，插入删除快的话，可以用链表，这里用双向链表，但是链表要查询某个值的话，就必须从头遍历，所以采用哈希链表的数据结构。

4. 代码实现

先总结下要实现哪些功能:

• 实现一个双向链表DoubleLinkedList,包括head、tail节点，长度size，addFirst(在链表头部添加节点)、remove(删除指定节点)、removeLast(删除链表中最后一个节点)以及size(返回链表长度方法)
• 实现链表中的节点Node,包括next、prev指针，一个构造方法
• 实现LRUCache类

Node类

package LeetCode.LRU;

public class Node {

    //节点的next指针
    public Node next;

    //节点的prev指针
    public Node prev;

    public int key,value;

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

DoubleLinkList类

package LeetCode.LRU;

/**
 * 双向链表
 */
public class DoubleLinkList {

    //头结点
    private Node head;
    //尾节点
    private Node tail;

    private int size;

    public DoubleLinkList() {
        head = new Node(0,0);
        tail = new Node(0,0);
        head.next = tail;
        tail.prev = head;
        this.size = 0;
    }

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

    //删除链表中指定节点，该节点一定存在
    public void remove(Node node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
        size--;
    }

    //删除链表中最后一个节点，并返回该节点，时间O(1)
    public Node removeLast(){
        if (head.next == tail){
            return null;
        }

        Node last = tail.prev;
        remove(last);
        return last;
    }

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

LRUCache类

package LeetCode.LRU;

import java.util.HashMap;

public class LRUCache {

    private HashMap<Integer, Node> hashMap;

    private DoubleLinkList cache;

    private int cap;

    public LRUCache(int capacity) {
        hashMap = new HashMap<>();
        cache = new DoubleLinkList();
        this.cap = capacity;
    }

    //将某个 key 提升为最近使用的
    private void makeRecently(int key){
        Node node = hashMap.get(key);
        //先删除该节点
        cache.remove(node);
        //将该节点添加到队头
        cache.addFirst(node);
    }

    //添加最近使用的元素
    private void addRecently(int key, int val){
        Node newNode = new Node(key,val);
        //在链表头部添加节点
        cache.addFirst(newNode);
        //在map里添加该节点
        hashMap.put(key,newNode);
    }

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

    //删除最久未使用的元素
    private void removeLeastRecently(){
        //链表的最后一个元素，就是最久未使用的
        Node node = cache.removeLast();
        hashMap.remove(node.key);
    }

    public int get(int key){
        if (!hashMap.containsKey(key)){
            return -1;
        }

        makeRecently(key);
        return hashMap.get(key).value;
    }

    public void put(int key, int val){
        //若key已存在
        if (hashMap.containsKey(key)){
            deleteKey(key);
            addRecently(key, val);
            return;
        }

        if (cap == cache.size()){
            removeLeastRecently();
        }

        addRecently(key, val);

    }

}

5. 测试类

package LeetCode.LRU;

public class TestLRU {

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(1,1);
        lruCache.put(2,2);
        lruCache.get(1);
        lruCache.put(3,3);
        lruCache.get(2);
        lruCache.put(4,4);
        lruCache.get(1);
        lruCache.get(3);
        lruCache.get(4);
    }
}

6. LeetCode

写完这个就可以拿下LeetCode第146题。