实现一个支持LRU淘汰策略的线程安全缓存

题目

实现一个支持LRU淘汰策略的线程安全缓存

信息

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

考点

ConcurrentHashMap应用, 线程安全设计, LinkedHashMap原理, 缓存淘汰策略, 泛型使用

快速回答

实现要点：

• 使用ConcurrentHashMap保证基础线程安全
• 通过Collections.synchronizedMap包装LinkedHashMap实现LRU
• 重写removeEldestEntry控制缓存大小
• 使用读写锁分离提升性能
• 注意泛型类型约束和内存泄漏防范

问题背景

在实际开发中，缓存是提升系统性能的关键组件。本题要求实现一个线程安全的LRU（最近最少使用）缓存，需要同时满足：

• 线程安全：支持多线程并发访问
• 容量控制：达到上限时自动淘汰最久未使用的数据
• 高效访问：保证O(1)时间复杂度的读写操作

核心实现方案

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

public class LRUCache<K, V> {
    private final int capacity;
    private final Map<K, V> cacheMap;
    private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();

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

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

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

    public void remove(K key) {
        lock.writeLock().lock();
        try {
            cacheMap.remove(key);
        } finally {
            lock.writeLock().unlock();
        }
    }
}

关键设计原理

• LRU实现机制：LinkedHashMap的构造参数accessOrder=true会将访问过的元素移至链表尾部，链表头部即为最久未使用的元素
• 线程安全保证：
  • 外层使用Collections.synchronizedMap保证基础原子操作安全
  • 读写锁（ReentrantReadWriteLock）实现读写分离，提升并发读性能
• 淘汰策略触发：重写removeEldestEntry方法，当size() > capacity时自动删除头部元素

最佳实践

• 锁粒度优化：使用读写锁而非synchronized，避免读操作阻塞
• 内存泄漏防范：对于键类型K，必须正确实现hashCode()和equals()
• 容量设置：初始容量建议设置为(最大缓存数/负载因子)+1避免频繁扩容

常见错误

• 线程安全问题：直接使用LinkedHashMap未加同步控制
• 淘汰策略失效：未正确设置accessOrder参数或重写removeEldestEntry
• 死锁风险：在同步块内调用外部方法可能引发死锁
• 性能瓶颈：使用全局锁导致并发度下降

扩展知识

• 替代方案：可直接使用ConcurrentHashMap + 自定义双向链表实现更细粒度的控制
• 其他淘汰策略：
  • FIFO（先进先出）：设置accessOrder=false
  • LFU（最不经常使用）：需要额外维护使用频率计数器
• Guava Cache：生产环境推荐使用Guava的CacheBuilder，支持权重、过期时间等高级特性