LRU缓存-LeetCode146_请你设计并实现一个满lru缓存约束的数据结构,实现lrucache类

（一）题目描述

请你设计并实现一个满足  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）LRU：Least Recently Used ：最近最少使用算法（操作系统中一种常用页面置换算法）。

（2）如何控制最近最少使用的键值对在内存达到最大时被删除？每次在访问完键值对后都将其移到链表头部，在内存达到最大时删除链表尾部的节点即可。

（3）该题相当于是手写LinkedHashMap实现的底层源码。

（三）代码实现

package promble;
 
import java.util.HashMap;
import java.util.LinkedHashMap;
 
/**
 * @author 一休
 * @version 1.0
 * @create 2022-04-11 16:59
 */
//相当于实现一个LRUcache类(也相当于自己实现了LinkedHashMap)
//自己定义一个双向链表
    //手写实现LinkedHashMap
class LinkedNode {
    int key;
    int value;
    LinkedNode prev;
    LinkedNode next;
 
    public LinkedNode() {
    }
 
    public LinkedNode(int key, int value) {
        this.key = key;
        this.value = value;
    }
 
}
 
class LRUCache {
    //hashMap中的value为自己定义的一个class节点，该节点有key,value,指向前后的指针
    HashMap<Integer, LinkedNode> hashMap;
    int size;
    int capacity;
    LinkedNode head;
    LinkedNode tail;
 
    public LRUCache(int capacity) {
        hashMap = new HashMap<>(capacity);
        size=0;
        this.capacity = capacity;
        head = new LinkedNode();
        tail = new LinkedNode();
        head.next = tail;
        tail.prev = head;
    }
 
    public int get(int key) {
        //如果获取到当前元素
        LinkedNode node = hashMap.get(key);
        if (node != null) {
            //去除当前元素
            remove(node);
            //添加到头部
            add(node);
            //返回index;
            return node.value;
        }
        return -1;
        //添加到头部
        //返回-1
    }
 
    public void put(int key, int value) {
        LinkedNode node = hashMap.get(key);
        if (node != null) {
            node.value = value;
            //删除当前节点
            remove(node);
            //移至头部
            add(node);
        } else {
            LinkedNode newNode = new LinkedNode(key, value);
            hashMap.put(key, newNode);
            add(newNode);
            size++;
            if (size > capacity) {
                LinkedNode removedNode = removeTail();
                hashMap.remove(removedNode.key);
            }
        }
    }
 
    private void add(LinkedNode node) {
        node.next = head.next;
        head.next = node;
        node.next.prev = node;
        node.prev = head;
    }
 
    private void remove(LinkedNode node) {
        node.prev.next = node.next;
        node.next.prev=node.prev;
    }
 
    private LinkedNode removeTail() {
        LinkedNode prev = tail.prev;
        remove(prev);
        return prev;
    }
}

（四）小tips：设置伪头结点和伪尾结点，使所有节点都是进行同样的处理