Leecode 146 LRU缓存

146. LRU 缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
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

提示：

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 105
• 最多调用 2 * 105 次 get 和 put

算法思路：

使用哈希表＋双向链表进行实现

代码实现：

import java.util.HashMap;

public class LRUCache {
    //将哈希表和链表中的节点产生对应关系
    private HashMap<Integer, Node> map;

    //双向链表存储数据
    private DoubleList cache;
    //容量
    private int capacity;

    //初始化
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }

    /**
     * 根据key获取元素，如果不存在返回-1
     * 如果存在就将其设置为最近使用的元素
     * @param key
     * @return
     */
    public int get(int key) {

        if (!map.containsKey(key)){
            return -1;
        }
        //将其设置为最近使用的元素
        makeRecently(key);
        return map.get(key).val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)){
            //删除旧数据
            deleteKey(key);
            //添加新数据,新数据即为最近使用的数据
            addRecently(key,value);
            return;
        }
        //如果容量已满，则将最近最少使用的元素弹出，然后将新数据插入
        if (capacity == cache.getSize()){
            removeLeastRecently();
        }
        addRecently(key,value);
    }


    /**
     * 将某个key提升为最近使用的
     * 将该节点从链表中删除并添加至链表末尾即可
     *
     * @param key
     */
    private void makeRecently(int key) {
        Node node = map.get(key);
        //将该节点从链表中删除
        cache.remove(node);
        //添加至链表末尾即可
        cache.addLast(node);
    }

    /**
     * 添加最近使用元素
     * @param key
     * @param val
     */
    private void addRecently(int key,int val){

        Node node = new Node(key, val);
        //链表尾部节点即为最近使用元素
        cache.addLast(node);

        //在map中添加key和node的映射
        map.put(key,node);

    }

    /**
     * 删除某个key
     * @param key
     */
    private void deleteKey(int key){
        Node node = map.get(key);
        //从链表中删除
        cache.remove(node);
        //从哈希表中删除
        map.remove(key);
    }

    /**
     * 删除最近最少使用的节点，即链表的第一个元素
     */
    private void removeLeastRecently(){
        //从链表中删除
        Node deleteNode = cache.removeFirst();
        //从哈希表中删除
        int deleteKey = deleteNode.key;
        map.remove(deleteKey);

    }

}

//自定义节点类型
class Node {
    public int key, val;
    public Node pre, next;

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

//双链表 只能从尾部插入，靠尾部的数据是最近使用的，靠头部的数据是最久未使用的。
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.pre = head;
        size = 0;
    }

    /**
     * 在链表尾部插入节点，时间复杂度O(1)
     *
     * @param node
     */
    public void addLast(Node node) {
        //尾插
        node.pre = tail.pre;
        node.next = tail;
        tail.pre.next = node;
        tail.pre = node;
        size++;
    }

    /**
     * 删除node节点,node结点是给定的，时间复杂度O(1)
     *
     * @param node
     */
    public void remove(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
        size--;
    }

    /**
     * 删除链表中第一个节点并返回，时间复杂度O(1)
     *
     * @return
     */
    public Node removeFirst() {
        if (head.next == tail) {
            return null;
        }

        Node node = head.next;
        //删除节点
        remove(node);
        //将节点返回
        return node;
    }

    /**
     * 返回链表长度，时间复杂度O(1)
     *
     * @return
     */
    public int getSize() {
        return size;
    }


}