设计一个线程安全的LRU缓存 -

题目

设计一个线程安全的LRU缓存

信息

类型：问答
难度：⭐⭐

考点

LinkedHashMap原理, 并发控制, 缓存策略

快速回答

实现线程安全的LRU缓存需要：

继承LinkedHashMap并重写removeEldestEntry方法实现LRU淘汰策略
使用ReentrantReadWriteLock保证线程安全：
- 写操作使用写锁（独占锁）
- 读操作使用读锁（共享锁）
设置合理的初始容量和负载因子避免频繁扩容

## 解析

1. 原理说明

LRU（Least Recently Used）缓存根据访问顺序淘汰最久未使用的数据：

LinkedHashMap原理：通过维护双向链表记录访问顺序（设置accessOrder=true）
线程安全：读写锁分离，读操作可并发，写操作互斥
淘汰策略：重写removeEldestEntry方法，当缓存满时自动移除链表头节点

2. 代码示例

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class ThreadSafeLRUCache<K, V> {
    private final int maxCapacity;
    private final LinkedHashMap<K, V> cache;
    private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();

    public ThreadSafeLRUCache(int maxCapacity) {
        this.maxCapacity = maxCapacity;
        this.cache = new LinkedHashMap<>(maxCapacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > maxCapacity;
            }
        };
    }

    public V get(K key) {
        lock.readLock().lock();
        try {
            return cache.get(key);
        } finally {
            lock.readLock().unlock();
        }
    }

    public void put(K key, V value) {
        lock.writeLock().lock();
        try {
            cache.put(key, value);
        } finally {
            lock.writeLock().unlock();
        }
    }

    // 可选：实现其他方法（如remove）时需同步加锁
}

3. 最佳实践

锁粒度控制：读写锁分离提升读密集型场景性能
容量规划：根据业务需求设置初始容量和负载因子，避免频繁扩容
访问顺序：构造LinkedHashMap时第三个参数必须设为true
资源释放：在finally块中释放锁确保可靠性

4. 常见错误

未使用读写锁：仅用synchronized会导致读操作串行化，性能下降
忘记设置accessOrder：LinkedHashMap默认按插入顺序排序
锁泄露：未在finally中释放锁可能导致死锁
非原子性复合操作：如“先检查是否存在再插入”需整体加写锁

5. 扩展知识

替代方案：
- Guava的CacheBuilder提供更丰富的缓存策略（TTL、弱引用等）
- ConcurrentHashMap+ConcurrentLinkedQueue可实现更高并发的LRU
其他淘汰策略：LFU（最不经常使用）、FIFO（先进先出）
性能优化：
- 读多写少场景：StampedLock乐观读进一步提升并发度
- 缓存预热：启动时加载热点数据