LRU 缓存：哈希表+双向链表

LRU 缓存（LeetCode 146）

要求 get、put 均 O(1)：哈希表 + 双向链表。

• 哈希表：key → 节点，实现 O(1) 查找
• 双向链表：维护访问顺序（头部最新，尾部最旧），实现 O(1) 移动节点

class LRUCache {
    private class Node {
        int key, val;
        Node prev, next;
        Node(int k, int v) { key = k; val = v; }
    }
    private Map<Integer, Node> map = new HashMap<>();
    private Node head, tail;  // dummy 哨兵节点
    private int cap;

    public LRUCache(int capacity) {
        cap = capacity;
        head = new Node(0, 0); tail = new Node(0, 0);
        head.next = tail; tail.prev = head;
    }
    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        moveToHead(node);
        return node.val;
    }
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.val = value;
            moveToHead(node);
        } else {
            if (map.size() == cap) {
                Node lru = tail.prev;
                remove(lru); map.remove(lru.key);
            }
            Node node = new Node(key, value);
            addToHead(node); map.put(key, node);
        }
    }
    private void addToHead(Node node) {
        node.next = head.next; node.prev = head;
        head.next.prev = node; head.next = node;
    }
    private void remove(Node node) {
        node.prev.next = node.next; node.next.prev = node.prev;
    }
    private void moveToHead(Node node) { remove(node); addToHead(node); }
}

Java 内置 LinkedHashMap 可简化实现，但手写版更考察理解程度。

O(1) 插入/删除/随机取样（LeetCode 380）

哈希表 + 动态数组：

class RandomizedSet {
    private Map<Integer, Integer> indexMap = new HashMap<>();  // 值 → 数组下标
    private List<Integer> list = new ArrayList<>();

    public boolean insert(int val) {
        if (indexMap.containsKey(val)) return false;
        list.add(val);
        indexMap.put(val, list.size() - 1);
        return true;
    }
    public boolean remove(int val) {
        if (!indexMap.containsKey(val)) return false;
        // 将末尾元素移到被删位置，再删末尾
        int idx = indexMap.get(val);
        int last = list.get(list.size() - 1);
        list.set(idx, last);
        indexMap.put(last, idx);
        list.remove(list.size() - 1);
        indexMap.remove(val);
        return true;
    }
    public int getRandom() {
        return list.get(new Random().nextInt(list.size()));
    }
}

允许重复的随机取样（LeetCode 381）

思路：哈希表存"每个值对应的所有下标集合"，删除时从集合中选一个下标用尾替换。

class RandomizedCollection {
    private Map<Integer, Set<Integer>> indexMap = new HashMap<>();
    private List<Integer> list = new ArrayList<>();
    // insert, remove 类似上题，但 indexMap 中是 Set<Integer>
    // 删除时：从 set 中取一个 idx，用末尾替换，更新末尾元素的 set
}

总结