实现线程安全的 LRU 缓存。

核心回答

可以用哈希表加双向链表，再用同一把锁保护完整操作。哈希表把键映射到节点，链表按最近访问顺序排列；get 命中、put 更新或新增，都把节点移到最近使用端，超出容量就淘汰另一端。

线程安全的关键是：查表、移动节点、插入与淘汰属于一个临界区，不能只保护哈希表。get 命中也会修改链表，因此同样需要独占保护。下面实现单进程、按条目数限容的严格 LRU，采用 Java 泛型和 synchronized。

代码实现

约定：容量为 0 时不保存数据，负容量非法；不接受 null 键和值，get 未命中返回 null。head 后面是最久未用的节点，tail 前面是最近使用的节点；两个哨兵不保存业务条目。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;

public final class ThreadSafeLruCache<K, V> {
    private final int capacity;
    private final Map<K, Node<K, V>> index = new HashMap<>();
    private final Node<K, V> head = new Node<>(null, null);
    private final Node<K, V> tail = new Node<>(null, null);

    private static final class Node<K, V> {
        final K key;
        V value;
        Node<K, V> prev;
        Node<K, V> next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    public ThreadSafeLruCache(int capacity) {
        if (capacity < 0) {
            throw new IllegalArgumentException("capacity must be nonnegative");
        }
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public synchronized V get(K key) {
        Objects.requireNonNull(key, "key");
        Node<K, V> node = index.get(key);
        if (node == null) {
            return null;
        }
        moveToMru(node);
        return node.value;
    }

    public synchronized void put(K key, V value) {
        Objects.requireNonNull(key, "key");
        Objects.requireNonNull(value, "value");
        if (capacity == 0) {
            return;
        }
        Node<K, V> node = index.get(key);
        if (node != null) {
            node.value = value;
            moveToMru(node);
            return;
        }
        node = new Node<>(key, value);
        index.put(key, node);
        linkAtMru(node);
        if (index.size() > capacity) {
            Node<K, V> victim = head.next;
            unlink(victim);
            index.remove(victim.key);
        }
    }

    public synchronized V remove(K key) {
        Objects.requireNonNull(key, "key");
        Node<K, V> node = index.remove(key);
        if (node == null) {
            return null;
        }
        unlink(node);
        return node.value;
    }

    public synchronized int size() {
        return index.size();
    }

    public synchronized List<K> keysFromLru() {
        List<K> keys = new ArrayList<>();
        for (Node<K, V> node = head.next; node != tail; node = node.next) {
            keys.add(node.key);
        }
        return List.copyOf(keys);
    }

    private void moveToMru(Node<K, V> node) {
        unlink(node);
        linkAtMru(node);
    }

    private void unlink(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void linkAtMru(Node<K, V> node) {
        node.prev = tail.prev;
        node.next = tail;
        tail.prev.next = node;
        tail.prev = node;
    }
}

为什么这个锁范围足够

所有公开的状态访问都锁住同一个缓存实例，辅助链表方法只由持锁的操作调用。其他线程不会在“哈希表已经插入、链表尚未连接”或者“新增后尚未淘汰”的中间状态访问缓存，因此每次操作完成时，哈希表和链表保持一一对应，容量不超过上限。

返回的是值和键列表副本，没有暴露内部节点、Map 或活跃迭代器。键的 hashCode、equals 应保持稳定；如果值是可变对象，调用方拿到它之后的修改仍需要自行协调，缓存锁不会保护对象内部的所有操作。

正常哈希分布下，get、put、remove 的数据结构操作平均为 O(1)，不包含锁等待；空间为 O(capacity)。keysFromLru 创建快照是 O(n)，不属于常数时间接口。多个独立方法调用也不会自动组成业务原子操作。

一个顺序例子

容量为 2，依次放入 A、B，最久未用到最近使用的顺序是 A、B；访问 A 后变为 B、A；再放 C，淘汰 B，留下 A、C。更新 A 的值也会使它成为最近使用的条目，不应额外占一个位置。

追问：读写锁、分段和过期时间怎么加

严格 LRU 的 get 命中会改变顺序，不能简单放进共享读锁；换成 ConcurrentHashMap 也不能单独保护另一条双向链表。单锁方案容易保证全局顺序，但高竞争下会串行化；分段可减少竞争，不过若每段独立淘汰，得到的是分段 LRU，不再等同全局严格 LRU。

若允许用标准库，可将访问有序的 LinkedHashMap 封装在统一同步边界内，并在新增后淘汰最老项；仍需保护读取和遍历，避免把底层可变视图泄露出去。

TTL 是另一个维度，本实现没有过期逻辑。扩展时需要在同一保护范围内检查并删除过期节点，也要确定过期依据和清理策略；用定时全表扫描会增加 O(n) 工作，不能继续宣称所有维护都为 O(1)。加载数据的远程调用也不宜长期占住这把全局锁。

参考资料