1. LRU缓存机制

1.自己构建

力扣 146.LRU缓存机制, 题解参考资料 Dong哥 和 狗哥, 并转载了他们的图片

计算机的缓存容量有限，如果缓存满了就要删除一些内容，给新内容腾位置。但问题是，删除哪些内容呢？我们肯定希望删掉哪些没什么用的缓存，而把有用的数据继续留在缓存里，方便之后继续使用。那么，什么样的数据，我们判定为「有用的」的数据呢？

LRU 缓存淘汰算法就是一种常用策略。LRU 的全称是 Least Recently Used，也就是说我们认为最近使用过的数据应该是是「有用的」，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据。

题目要求:
设计一种缓存结构，该结构在构造时确定大小，假设大小为K，并有两个功能：set(key,value)：将记录(key,value)插入该结构。get(key)：返回key对应的value值。
【要求】
set和get方法的时间复杂度为O(1)。
某个key的set或get操作一旦发生，认为这个key的记录成了最经常使用的。
当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。
【举例】
假设缓存结构的实例是cache，大小为3，并依次发生如下行为：
cache.set(“A”,1)。最经常使用的记录为(“A”,1)。
cache.set(“B”,2)。最经常使用的记录为(“B”,2)，(“A”,1)变为最不经常的。
cache.set(“C”,3)。最经常使用的记录为(“C”,2)，(“A”,1)还是最不经常的。
cache.get(“A”)。最经常使用的记录为(“A”,1)，(“B”,2)变为最不经常的。
cache.set(“D”,4)。大小超过了3，所以移除此时最不经常使用的记录(“B”,2)，加入记录 (“D”,4)，并且为最经常使用的记录，然后(“C”,2)变为最不经常使用的记录

题解:
那么，什么数据结构同时符合上述条件呢？哈希表查找快，但是数据无固定顺序；链表有顺序之分，插入删除快，但是查找慢。所以结合一下，形成一种新的数据结构：哈希链表 LinkedHashMap。

LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体。这个数据结构长这样：

在哈希表中value存放的是节点的引用，通过key可以直接查询到某个节点，也可以直接在链表中定位！

1.设计好的Cache的上层结构

public static class MyCache<K>{
    // cache缓存包括，哈希表，双端链表 和 容量
    private HashMap<K, Node<K>> keyNodeMap;
    private NodeDoubleLinkedList<K> nodeList;
    private final int capacity;
    // 初始化结构体
    public MyCache(int capacity) {
        this.capacity = capacity;
        this.keyNodeMap = new HashMap<K, Node<K>>();
        this.nodeList = new NodeDoubleLinkedList<K>();
    }
    // get(key)：返回key对应的value值。
    public int get(K key){
        // 如果这个key还在缓存中
        if (keyNodeMap.containsKey(key)){
            int val = keyNodeMap.get(key).value;
            // 这个操作，会更新被操作的节点的顺序
            nodeList.moveNodeToTail(keyNodeMap.get(key));
            return val;
        }else{
            // 没有找到，它被移除了
            return -1;
        }
    }

    //set(key,value)：将记录(key,value)插入该结构。
    public void put(K key, int value){
        // 可能会是更新，也可能是插入新的点
        // 更新操作不会移除点
        if (keyNodeMap.containsKey(key)){
            Node<K> node = keyNodeMap.get(key);
            node.value = value;
            // 这个操作，会更新被操作的节点的顺序
            nodeList.moveNodeToTail(node);
        }else {// 插入新节点了，要先判断容量够么
            if (capacity == keyNodeMap.size()){
                // 也可以定义一个函数: removeMostUnusedCache()
                // 从链表中去除
                Node<K> node = nodeList.removeHead();
                // 在HashMap表中也清除它
                keyNodeMap.remove(node.key);

            }
            // 插入新的点
            Node<K> newNode = new Node<K>(key, value);
            keyNodeMap.put(key, newNode);
            nodeList.addNode(newNode);
        }
    }
}

2.实现其中的双端链表 和 基本的node类

// 定义包含 <key,value> 的Node节点
public static class Node<K>{
    public K key;
    public int value;
    public Node<K> pre;
    public Node<K> next;

    public Node(K key, int value){
        this.key = key;
        this.value = value;
        pre = null;
        next = null;
    }
}

// 在双端链表中要实现，三个功能
// void addNode(Node<K> node) : 添加新的节点，并放到链表尾部
// void moveNodeToTail(Node<K> node) : 把node放到链表尾部
// Node<K> removeHead() : 把头部节点从链表上移除，并返回它
public static class NodeDoubleLinkedList<K>{
    // 设置头尾指针
    public Node<K> head;
    public Node<K> tail;
    // 结构体初始化
    public NodeDoubleLinkedList(){
        head = null;
        tail = null;
    }
    // 添加新的节点，并放到链表尾部
    // 要分情况: 是空链表么
    public void addNode(Node<K> node){
        // 空链表
        if (head == null){
            head = node;
            tail = node;
        }else { // 非空链表
            this.tail.next = node;
            node.pre = this.tail;
            this.tail = node;
        }
    }
    // node 首先一定会存在
    public void moveNodeToTail(Node<K> node){
        // 本来就是尾巴
        if (node == tail){
            return;
        }
        // 本来是头部，就会给链表换头了
        if (node == head){
            node.next.pre = null;
            // 更换头节点
            head = node.next;
            node.next = null;
            // 拼接到尾节点上, 代码重复
        }else { // 中间节点
            // 连接好左右两边
            node.pre.next = node.next;
            node.next.pre = node.pre;
            node.next = null;
            node.pre = null;
            // 拼接到尾节点上, 代码重复
        }
        // 把node放在tail上
        tail.next = node;
        node.pre = tail;
        tail = node;
    }

    // 移除头节点，并把它返回
    public Node<K> removeHead(){
        // 压根没有头
        if (head == null){
            return null;
        }
        // 记录原来的头节点
        Node<K> res = head;
        // 只有一个节点
        if (head == tail){
            head = null;
            tail = null;
        }else{
            // 把head标志位，向后移动一位
            head = res.next;
            // 根据新的头节点，把以前的头节点左右设置为空
            res.next = null;
            // 彻底断开原来的头节点, 新头部pre置空
            head.pre = null;
        }
        return res;
    }
}

2.LinkedHashMap build-in

参考资料
LinkedHashMap保持HashMap的数据结构，但是自己也维护一个双向循环链表。

LinkedHashMap内部有accessOrder标记，为false时，双向链表按插入的顺序排列。因为新插入的元素都是尾插法，此时我们需要自己实现makeItAsRecentlyUsed()方法，其实就是删除它在插入。

accessOrder=true时，每次对元素进行增删改查，都会将该元素放到链表尾部。使这个链表将最新操作的元素放入链表尾，长时间未使用的放入头部。这种即是LRU算法。

1.accessOrder=false

public static class MyCache{
    int capacity;
    LinkedHashMap<Integer, Integer> linkedHashMap;

    // 结构体初始化
    public MyCache(int capacity){
        this.capacity = capacity;
        this.linkedHashMap = new LinkedHashMap<>();
    }

    public int get(int key){
        if (linkedHashMap.containsKey(key)){
            int val = linkedHashMap.get(key);
            // 因为get操作，把这个它更新了
            makeItAsRecentlyUsed(key);
            // 查询到了结果
            return val;
        }
        // 没有这个点
        return -1;
    }

    public void put(int key, int value){
        // 更新操作
        if (linkedHashMap.containsKey(key)){
            // map上的更新
            linkedHashMap.put(key, value);
            makeItAsRecentlyUsed(key);
        }else {
            if (linkedHashMap.size() >= capacity){
                // 移除链表的头部
                int oldestKey = linkedHashMap.keySet().iterator().next();
                linkedHashMap.remove(oldestKey);
            }
            // 腾出空间，添加新的节点
            linkedHashMap.put(key, value);
        }
    }

    private void makeItAsRecentlyUsed(int key){
        int value = linkedHashMap.get(key);
        linkedHashMap.remove(key);
        // 重新加入，就自动放到tail上了
        linkedHashMap.put(key, value);
    }

}

2.accessOrder=true

public static class MyCache{
    int capacity;
    LinkedHashMap<Integer, Integer> linkedHashMap;

    // 结构体初始化
    public MyCache(int capacity){
        this.capacity = capacity;
        // 0.65f是扩容因子，true是启用accessOrder
        this.linkedHashMap = new LinkedHashMap<>(capacity, 0.65f, true);
    }

    public int get(int key){
        if (linkedHashMap.containsKey(key)){
            int val = linkedHashMap.get(key);
            // 因为get操作，把这个它更新了
            // makeItAsRecentlyUsed(key);
            // 查询到了结果
            return val;
        }
        // 没有这个点
        return -1;
    }

    public void put(int key, int value){
        // 更新操作
        if (linkedHashMap.containsKey(key)){
            // map上的更新
            linkedHashMap.put(key, value);
            // makeItAsRecentlyUsed(key);
        }else {
            if (linkedHashMap.size() >= capacity){
                // 移除链表的头部
                int oldestKey = linkedHashMap.keySet().iterator().next();
                linkedHashMap.remove(oldestKey);
            }
            // 腾出空间，添加新的节点
            linkedHashMap.put(key, value);
        }
    }
}