LRU缓存淘汰策略如何用O(1)时间完成get与put操作从双向链表到HashMap的精妙结合

// 初始化
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.prev = head;

// 错误示例：无法从HashMap中删除
Node lru = tail.prev;
removeNode(lru);
// map.remove(???)  // 不知道key是什么

// 正确做法：节点存储key
Node lru = tail.prev;
removeNode(lru);
map.remove(lru.key);  // 可以正确删除

import java.util.HashMap;
import java.util.Map;

// 双向链表节点定义
class DoublyLinkedNode {
    int key;
    int value;
    DoublyLinkedNode prev;
    DoublyLinkedNode next;
    
    public DoublyLinkedNode(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

public class LRUCache {
    private final Map<Integer, DoublyLinkedNode> cacheMap;
    private final DoublyLinkedNode head;  // 哑头节点
    private final DoublyLinkedNode tail;  // 哑尾节点
    private final int capacity;
    private int size;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cacheMap = new HashMap<>();
        this.size = 0;
        
        // 初始化哑节点
        head = new DoublyLinkedNode(0, 0);
        tail = new DoublyLinkedNode(0, 0);
        head.next = tail;
        tail.prev = head;
    }
    
    // 获取key对应的value
    public int get(int key) {
        if (!cacheMap.containsKey(key)) {
            return -1;
        }
        DoublyLinkedNode node = cacheMap.get(key);
        moveToHead(node);  // 标记为最近使用
        return node.value;
    }
    
    // 插入或更新键值对
    public void put(int key, int value) {
        if (cacheMap.containsKey(key)) {
            // key已存在，更新value并移到头部
            DoublyLinkedNode node = cacheMap.get(key);
            node.value = value;
            moveToHead(node);
        } else {
            // key不存在，创建新节点
            DoublyLinkedNode newNode = new DoublyLinkedNode(key, value);
            cacheMap.put(key, newNode);
            addToHead(newNode);
            size++;
            
            // 超出容量，淘汰LRU
            if (size > capacity) {
                DoublyLinkedNode lru = removeTail();
                cacheMap.remove(lru.key);
                size--;
            }
        }
    }
    
    // 将节点移到头部（标记为最近使用）
    private void moveToHead(DoublyLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }
    
    // 从链表中删除节点
    private void removeNode(DoublyLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    // 将节点添加到头部
    private void addToHead(DoublyLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
    
    // 删除尾部节点（LRU节点）
    private DoublyLinkedNode removeTail() {
        DoublyLinkedNode lru = tail.prev;
        removeNode(lru);
        return lru;
    }
}

import java.util.LinkedHashMap;

public class LRUCacheSimple extends LinkedHashMap<Integer, Integer> {
    private final int capacity;
    
    public LRUCacheSimple(int capacity) {
        super(capacity, 0.75f, true);  // accessOrder=true表示按访问顺序排序
        this.capacity = capacity;
    }
    
    public int get(int key) {
        return super.getOrDefault(key, -1);
    }
    
    public void put(int key, int value) {
        super.put(key, value);
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;  // 返回true时自动删除最老的条目
    }
}

import java.util.HashMap;
import java.util.Map;

class Node {
    int key, value, freq;
    Node prev, next;
    
    public Node(int key, int value) {
        this.key = key;
        this.value = value;
        this.freq = 1;
    }
}

class DoubleLinkedList {
    Node head, tail;
    int size;
    
    public DoubleLinkedList() {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }
    
    public void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        size++;
    }
    
    public void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        size--;
    }
    
    public Node removeTail() {
        if (size == 0) return null;
        Node node = tail.prev;
        removeNode(node);
        return node;
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
}

public class LFUCache {
    private final Map<Integer, Node> keyMap;
    private final Map<Integer, DoubleLinkedList> freqMap;
    private final int capacity;
    private int minFreq;
    
    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.keyMap = new HashMap<>();
        this.freqMap = new HashMap<>();
        this.minFreq = 0;
    }
    
    public int get(int key) {
        if (!keyMap.containsKey(key)) {
            return -1;
        }
        Node node = keyMap.get(key);
        increaseFreq(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        if (capacity == 0) return;
        
        if (keyMap.containsKey(key)) {
            Node node = keyMap.get(key);
            node.value = value;
            increaseFreq(node);
        } else {
            if (keyMap.size() >= capacity) {
                evict();
            }
            Node newNode = new Node(key, value);
            keyMap.put(key, newNode);
            freqMap.computeIfAbsent(1, k -> new DoubleLinkedList()).addToHead(newNode);
            minFreq = 1;
        }
    }
    
    private void increaseFreq(Node node) {
        int oldFreq = node.freq;
        DoubleLinkedList oldList = freqMap.get(oldFreq);
        oldList.removeNode(node);
        
        if (oldFreq == minFreq && oldList.isEmpty()) {
            minFreq++;
        }
        
        node.freq++;
        freqMap.computeIfAbsent(node.freq, k -> new DoubleLinkedList()).addToHead(node);
    }
    
    private void evict() {
        DoubleLinkedList minFreqList = freqMap.get(minFreq);
        Node node = minFreqList.removeTail();
        keyMap.remove(node.key);
    }
}