LRU缓存

LRU

LRU（Least Recently Used，最近最少使用）是一种经典的缓存淘汰算法。

它的核心思想是基于局部性原理：“如果数据最近被访问过，那么将来被访问的几率也更高”。当缓存容量达到上限，必须清理空间来存放新数据时，LRU 会优先淘汰距离当前时间最久没有被访问过的数据。

底层实现逻辑

标准的 LRU 缓存通常通过 哈希表（Hash Map） + 双向链表（Doubly Linked List） 来实现，以保证所有操作的时间复杂度都是 O(1)：

• 哈希表：键指向链表中的节点，用于快速定位数据。
• 双向链表：用于维护数据的访问顺序。每次新插入或被访问的数据，都会被移动到链表头部（代表最新访问）。当缓存满时，直接删除链表尾部的节点（代表最久未访问）。

https://leetcode.cn/problems/lru-cache/description/

请你设计并实现一个满足 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) 的平均时间复杂度运行。

import java.util.HashMap;

class LRUCache {
    //双向链表节点
    static class DLinkedNode{
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode(int key, int value){
            this.key = key;
            this.value = value;
        }
    }

    private HashMap<Integer,DLinkedNode> cache;
    private DLinkedNode dummyHead;
    private DLinkedNode dummyTail;
    private int capacity;
    private int size;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        size = 0;
        cache = new HashMap<>();
        //初始化虚拟头尾
        dummyHead = new DLinkedNode(-1,-1);
        dummyTail = new DLinkedNode(-1,-1);
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }

    //将node加到虚拟头后面
    private void addToHead(DLinkedNode node){
        node.prev = dummyHead;
        node.next = dummyHead.next;
        dummyHead.next.prev = node;
        dummyHead.next = node;
    }

    //摘除某个节点
    private void removeNode(DLinkedNode node){
        DLinkedNode pre = node.prev;
        DLinkedNode nex = node.next;
        pre.next = nex;
        nex.prev = pre;
    }

    //移动到头部
    private void moveToHead(DLinkedNode node){
        removeNode(node);
        addToHead(node);
    }

    //删除尾部节点，返回被删节点
    private DLinkedNode removeTail(){
        DLinkedNode tail = dummyTail.prev;
        removeNode(tail);
        return tail;
    }

    public int get(int key) {
        if(!cache.containsKey(key)){
            return -1;
        }
        DLinkedNode node = cache.get(key);
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        if(cache.containsKey(key)){
            //已存在，更新值+挪到头部
            DLinkedNode node = cache.get(key);
            node.value = value;
            moveToHead(node);
        }else{
            DLinkedNode newNode = new DLinkedNode(key,value);
            cache.put(key,newNode);
            addToHead(newNode);
            size++;
            
            if(size > capacity){
                //淘汰尾结点
                DLinkedNode remove = removeTail();
                cache.remove(remove.key);
                size--;
            }
        }
    }
}