使用ConcurrentHashMap实现线程安全的LRU缓存

题目

使用ConcurrentHashMap实现线程安全的LRU缓存

信息

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

考点

ConcurrentHashMap原理, 线程安全设计, LinkedHashMap扩展, LRU淘汰策略

快速回答

实现要点：

• 继承LinkedHashMap并重写removeEldestEntry方法实现LRU淘汰
• 使用ConcurrentHashMap的线程安全保证
• 通过ReentrantLock控制写操作的原子性
• 使用Collections.synchronizedMap包装保证迭代安全

1. 问题背景

在并发环境下实现LRU（Least Recently Used）缓存需要同时满足：
1) 线程安全 2) 高效的读写操作 3) 自动淘汰最久未使用的数据。

2. 核心实现方案

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

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

    public V get(K key) {
        return cache.get(key); // 读操作无需加锁
    }

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

3. 关键设计原理

• LinkedHashMap特性：通过构造函数第三个参数accessOrder=true开启访问顺序记录，最近访问的元素移动到链表尾部
• LRU淘汰机制：重写removeEldestEntry方法，当大小超过maxSize时移除链表头部的元素（最久未使用）
• 线程安全分层：
  • Collections.synchronizedMap包装保证迭代器安全（fail-safe）
  • ReentrantLock独占锁保证写操作的原子性
  • ConcurrentHashMap的CAS机制保证基础读操作的高并发

4. 最佳实践

• 读写分离：读操作无锁化（利用ConcurrentHashMap特性），写操作加锁
• 容量设置：初始容量建议设置为(maxSize / loadFactor) + 1避免频繁扩容
• 锁粒度优化：对于超高并发场景，可使用分段锁（Segment）替代全局锁

5. 常见错误

• 直接使用ConcurrentHashMap：无法实现访问顺序追踪和自动淘汰
• 未同步写操作：多个线程同时执行put可能导致LRU链表断裂
• 忽略迭代器安全：未包装synchronizedMap时，并发迭代可能触发ConcurrentModificationException

6. 扩展知识

• 替代方案：Google Guava的CacheBuilder或Caffeine缓存库提供更完善的实现
• 性能优化：当缓存命中率高时，可考虑使用ReadWriteLock减少写锁竞争
• 淘汰策略扩展：可通过实现Queue接口实现FIFO或LFU等淘汰算法