设计一个线程安全的LRU缓存，要求支持高并发访问，并考虑内存管理和性能优化

题目

设计一个线程安全的LRU缓存，要求支持高并发访问，并考虑内存管理和性能优化

信息

• 类型：问答
• 难度：⭐⭐⭐

考点

并发编程,集合框架,LRU算法,性能优化

快速回答

实现线程安全的LRU缓存需要结合LinkedHashMap和并发控制机制，核心要点包括：

• 使用LinkedHashMap的访问顺序特性（accessOrder=true）实现LRU淘汰逻辑
• 通过重写removeEldestEntry方法控制缓存容量
• 采用读写锁（ReadWriteLock）分离读/写操作，提高并发性能
• 使用弱引用（WeakReference）防止内存泄漏
• 考虑ConcurrentHashMap替代方案优化写并发

原理说明

LRU（Least Recently Used）缓存淘汰策略要求当缓存满时优先移除最久未使用的数据。Java的LinkedHashMap通过维护双向链表可实现访问顺序追踪：

• 构造函数设置accessOrder=true时，访问操作（get/put）会将节点移到链表尾部
• 链表头部即为最久未使用节点，通过重写removeEldestEntry实现淘汰逻辑
• 线程安全需解决并发访问冲突，读写锁（读共享写互斥）可优化读多写少场景

代码示例

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

public class ConcurrentLRUCache<K, V> {
    private final int maxSize;
    private final Map<K, V> cache;
    private final ReadWriteLock lock = new ReentrantReadWriteLock();

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

    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();
        }
    }

    // 内存优化版本（使用弱引用）
    private static class WeakValueCache<K, V> extends LinkedHashMap<K, WeakReference<V>> {
        // 实现类似但值包装为WeakReference
    }
}

最佳实践

• 锁粒度优化：读写锁分离减少读操作阻塞，写操作使用分段锁（如ConcurrentHashMap）
• 内存管理：值对象使用WeakReference/SoftReference，配合ReferenceQueue自动清理
• 性能平衡：读多写少用读写锁，写频繁时考虑ConcurrentHashMap+AtomicReference
• 容量控制：设置合理初始容量和负载因子避免频繁扩容

常见错误

• 死锁风险：在同步块内调用外部方法（如回调函数）
• 内存泄漏：未清理无效弱引用导致Entry堆积（需配合ReferenceQueue）
• 可见性问题：未正确同步导致脏读（如双重检查锁未用volatile）
• 性能陷阱：LinkedHashMap全表锁导致写操作串行化

扩展知识

• 替代方案：Guava Cache/Caffeine等专业缓存库（支持权重、过期策略）
• 并发优化：ConcurrentHashMap+AtomicReference实现无锁读（但写操作需CAS重试）
• 淘汰策略扩展：结合访问频率实现LRU-K或W-TinyLFU混合策略
• 监控指标：添加hit/miss统计、淘汰计数器等运维支持