手写LRU缓存：基于LinkedHashMap和双向链表+HashMap

方式1：继承LinkedHashMap（最简单）

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;
    
    public LRUCache(int maxSize) {
        super(maxSize, 0.75f, true);  // accessOrder=true 开启访问排序
        this.maxSize = maxSize;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;  // 超过容量时移除最老的（最近最少使用）
    }
    
    // 直接使用父类的get/put，自动维护LRU顺序
}

原理：accessOrder=true时，每次get/put都会将该条目移到链表尾部，头部的就是最近最少使用的。

方式2：双向链表+HashMap（手写）

public class LRUCacheManual<K, V> {
    
    static class Node<K, V> {
        K key;
        V value;
        Node<K, V> prev, next;
        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
    
    private final int capacity;
    private final Map<K, Node<K, V>> map = new HashMap<>();
    private final Node<K, V> head = new Node<>(null, null);  // 虚拟头
    private final Node<K, V> tail = new Node<>(null, null);  // 虚拟尾
    
    public LRUCacheManual(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }
    
    public V get(K key) {
        Node<K, V> node = map.get(key);
        if (node == null) return null;
        moveToTail(node);  // 最近使用，移到尾部
        return node.value;
    }
    
    public void put(K key, V value) {
        Node<K, V> node = map.get(key);
        if (node != null) {
            node.value = value;
            moveToTail(node);
        } else {
            if (map.size() >= capacity) {
                Node<K, V> removed = removeHead();  // 移除链表头（最久未使用）
                map.remove(removed.key);
            }
            Node<K, V> newNode = new Node<>(key, value);
            map.put(key, newNode);
            addToTail(newNode);
        }
    }
    
    private void moveToTail(Node<K, V> node) {
        removeNode(node);
        addToTail(node);
    }
    
    private void addToTail(Node<K, V> node) {
        node.prev = tail.prev;
        node.next = tail;
        tail.prev.next = node;
        tail.prev = node;
    }
    
    private void removeNode(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    private Node<K, V> removeHead() {
        Node<K, V> node = head.next;
        removeNode(node);
        return node;
    }
}

时间复杂度：get O(1)，put O(1) — HashMap提供O(1)查找，双向链表提供O(1)节点移动。