LRU 算法实现|野路玩家

LRU（Least Recently Used，最近最少使用）是一种常用的缓存淘汰算法。在 Java 中实现 LRU 算法，通常结合哈希表（HashMap）和双向链表（Doubly Linked List）来实现，以保证 get 和 put 操作的时间复杂度为 O(1)。

Java 中可以通过继承 LinkedHashMap 快速实现，也可以手动实现一个完整的 LRU 缓存类。下面分别介绍这两种方式。

✅ 方法一：继承 `LinkedHashMap`（简单实现）

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        // accessOrder = true 表示按访问顺序排序（LRU 关键）
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    // 重写 removeEldestEntry 方法，控制缓存容量
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }

    // 示例使用
    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);
        cache.put(1, "A");
        cache.put(2, "B");
        cache.put(3, "C");
        System.out.println(cache.keySet()); // [1, 2, 3]

        cache.get(2); // 访问 2
        System.out.println(cache.keySet()); // [1, 3, 2]（2 移动到末尾）

        cache.put(4, "D"); // 超出容量，淘汰最久未使用的 1
        System.out.println(cache.keySet()); // [3, 2, 4]
    }
}

⚠️ 注意：这种方式虽然简洁，但不适用于高并发场景（因为 LinkedHashMap 不是线程安全的），且对细节控制较少。

✅ 方法二：手写 LRU（推荐，理解原理）

import java.util.HashMap;
import java.util.Map;

class LRUCacheManual {
    static class Node {
        int key;
        int value;
        Node prev;
        Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;
    private final Map<Integer, Node> cache;
    private final Node head;
    private final Node tail;

    public LRUCacheManual(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.head = new Node(-1, -1);
        this.tail = new Node(-1, -1);
        head.next = tail;
        tail.prev = head;
    }

    // 获取缓存
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        Node node = cache.get(key);
        moveToHead(node); // 访问后移到头部
        return node.value;
    }

    // 添加缓存
    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            node.value = value;
            moveToHead(node);
        } else {
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addToHead(newNode);

            if (cache.size() > capacity) {
                Node tailNode = removeTail();
                cache.remove(tailNode.key);
            }
        }
    }

    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    private Node removeTail() {
        Node last = tail.prev;
        removeNode(last);
        return last;
    }
}

// 示例使用
public class Main {
    public static void main(String[] args) {
        LRUCacheManual cache = new LRUCacheManual(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1)); // 返回 1，访问后移到头部
        cache.put(3, 3); // 淘汰 key=2（最久未使用）
        System.out.println(cache.get(2)); // 返回 -1（已淘汰）
        cache.put(4, 4); // 淘汰 key=3
        System.out.println(cache.get(1)); // 返回 -1
        System.out.println(cache.get(3)); // 返回 -1
        System.out.println(cache.get(4)); // 返回 4
    }
}

🔍 实现原理说明：

双向链表：维护访问顺序，最近使用的放在链表头，最久未使用的在链表尾。
HashMap：实现 O(1) 的快速查找。
put/get 操作：
- get：若存在，返回值并移到链表头；否则返回 -1。
- put：若已存在，更新值并移到头部；若不存在，插入头部，超出容量时删除尾部节点。

✅ 进阶建议（生产环境）：

使用 ConcurrentHashMap 和 synchronized 或 ReentrantLock 实现线程安全。
可结合 volatile 或 ThreadLocal 优化性能。
考虑使用 java.util.concurrent 包下的结构，或直接使用 Guava Cache 等成熟库。

📦 实际项目推荐（使用 Guava）：

import com.google.common.cache.CacheBuilder;
import com.google.common.cache.Cache;

Cache<Integer, String> cache = CacheBuilder.newBuilder()
    .maximumSize(100)
    .expireAfterWrite(10, TimeUnit.MINUTES)
    .build();

cache.put(1, "A");
String value = cache.getIfPresent(1);

Guava Cache 内置了 LRU 机制，功能更强大，适合生产环境。

✅线程安全的 LRU Cache 实现（基于双向链表 + HashMap + ReentrantLock）

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

public class ThreadSafeLRUCache<K, V> {
    static class Node<K, V> {
        K key;
        V value;
        Node<K, V> prev;
        Node<K, V> next;

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

    private final int capacity;
    private final Map<K, Node<K, V>> cache;
    private final Node<K, V> head;
    private final Node<K, V> tail;
    private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
    private final ReentrantReadWriteLock.ReadLock readLock = lock.readLock();
    private final ReentrantReadWriteLock.WriteLock writeLock = lock.writeLock();

    public ThreadSafeLRUCache(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("Capacity must be positive");
        }
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.head = new Node<>(null, null);
        this.tail = new Node<>(null, null);
        head.next = tail;
        tail.prev = head;
    }

    // 获取缓存值
    public V get(K key) {
        readLock.lock();
        try {
            Node<K, V> node = cache.get(key);
            if (node == null) {
                return null;
            }
            // 移动到头部（最近使用）
            moveToHead(node);
            return node.value;
        } finally {
            readLock.unlock();
        }
    }

    // 添加缓存值
    public void put(K key, V value) {
        if (key == null || value == null) {
            return;
        }

        writeLock.lock();
        try {
            if (cache.containsKey(key)) {
                // 更新值并移到头部
                Node<K, V> node = cache.get(key);
                node.value = value;
                moveToHead(node);
            } else {
                // 创建新节点
                Node<K, V> newNode = new Node<>(key, value);
                cache.put(key, newNode);
                addToHead(newNode);

                // 超出容量，移除尾部节点
                if (cache.size() > capacity) {
                    Node<K, V> tailNode = removeTail();
                    cache.remove(tailNode.key);
                }
            }
        } finally {
            writeLock.unlock();
        }
    }

    // 移除节点
    private void removeNode(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // 添加到头部
    private void addToHead(Node<K, V> node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    // 移动到头部
    private void moveToHead(Node<K, V> node) {
        removeNode(node);
        addToHead(node);
    }

    // 移除尾部节点（最久未使用）
    private Node<K, V> removeTail() {
        Node<K, V> last = tail.prev;
        removeNode(last);
        return last;
    }

    // 获取当前缓存大小（线程安全）
    public int size() {
        readLock.lock();
        try {
            return cache.size();
        } finally {
            readLock.unlock();
        }
    }

    // 清空缓存（可选）
    public void clear() {
        writeLock.lock();
        try {
            cache.clear();
            head.next = tail;
            tail.prev = head;
        } finally {
            writeLock.unlock();
        }
    }
}

🧪 使用示例

public class Main {
    public static void main(String[] args) {
        ThreadSafeLRUCache<Integer, String> cache = new ThreadSafeLRUCache<>(2);

        cache.put(1, "A");
        cache.put(2, "B");
        System.out.println(cache.get(1)); // 输出: A

        cache.put(3, "C"); // 淘汰 key=2
        System.out.println(cache.get(2)); // 输出: null（已被淘汰）

        System.out.println(cache.get(3)); // 输出: C
        System.out.println(cache.get(1)); // 输出: A
        cache.put(4, "D"); // 淘汰 key=1
        System.out.println(cache.get(1)); // 输出: null
        System.out.println(cache.get(4)); // 输出: D
    }
}

🔐 线程安全说明：

使用 ReentrantReadWriteLock：
- get 操作使用读锁，允许多个线程并发读。
- put、remove、结构变更操作使用写锁，独占访问。
读写分离，提高并发性能。
所有共享状态（cache、链表结构）在读写时都被锁保护。

🚀 生产建议：

如果你使用的是 Java 8+ 并追求高性能，也可以考虑使用 synchronized 方法 + ConcurrentHashMap，在简单场景下性能更好。
更推荐使用 Guava Cache 或 Caffeine，它们是线程安全、高性能、支持过期策略、权重控制等的成熟缓存库。

📦 使用 Caffeine（推荐生产环境）

import com.github.benmanes.caffeine.cache.Cache;
import com.github.benmanes.caffeine.cache.Caffeine;

Cache<Integer, String> cache = Caffeine.newBuilder()
    .maximumSize(100)
    .build();

cache.put(1, "A");
String value = cache.getIfPresent(1);

Caffeine 是目前 Java 领域最优秀的本地缓存库，基于改进的 LRU 算法，线程安全，性能优于 Guava。

✅ 终极版 LRU Cache（基于 Caffeine）

1. 添加依赖（Maven）

<dependency>
    <groupId>com.github.benmanes.caffeine</groupId>
    <artifactId>caffeine</artifactId>
    <version>3.1.8</version> <!-- 推荐使用最新稳定版 -->
</dependency>

2. 完整实现代码

import com.github.benmanes.caffeine.cache.Cache;
import com.github.benmanes.caffeine.cache.Caffeine;
import com.github.benmanes.caffeine.cache.RemovalListener;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.TimeUnit;

public class UltimateLRUCache<K, V> {
    private final Cache<K, V> cache;

    // 构造函数：可配置最大容量、过期时间、移除监听等
    public UltimateLRUCache(int maximumSize, long expireAfterWriteSeconds, long expireAfterAccessSeconds) {
        Caffeine<K, V> caffeine = Caffeine.newBuilder()
            .maximumSize(maximumSize)  // 最大缓存条目数（基于 LRU 回收）

            // 写入后过期（可选）
            .expireAfterWrite(expireAfterWriteSeconds, TimeUnit.SECONDS)

            // 访问后过期（可选，与 expireAfterWrite 二选一或同时使用）
            .expireAfterAccess(expireAfterAccessSeconds, TimeUnit.SECONDS)

            // 使用弱引用键（可选：允许 GC 回收不再使用的键）
            .weakKeys()

            // 使用软引用值（可选：内存不足时自动回收，避免 OOM）
            // .softValues()

            // 开启统计功能（命中率、加载次数等）
            .recordStats()

            // 缓存项被移除时的监听（可用于日志、清理资源等）
            .removalListener((RemovalListener<K, V>) (key, value, cause) -> {
                System.out.println("Key " + key + " removed, value: " + value + ", cause: " + cause);
            });

        this.cache = caffeine.build();
    }

    // 获取缓存值
    public V get(K key) {
        return cache.getIfPresent(key);
    }

    // 写入缓存
    public void put(K key, V value) {
        cache.put(key, value);
    }

    // 移除缓存
    public void invalidate(K key) {
        cache.invalidate(key);
    }

    // 清空所有缓存
    public void invalidateAll() {
        cache.invalidateAll();
    }

    // 获取统计信息（命中率、请求次数等）
    public String stats() {
        return cache.stats().toString();
    }

    // 获取当前缓存大小
    public long size() {
        return cache.estimatedSize();
    }

    // 获取缓存 map 的快照（不可变）
    public ConcurrentMap<K, V> asMap() {
        return cache.asMap();
    }
}

3. 使用示例

public class Main {
    public static void main(String[] args) throws InterruptedException {
        UltimateLRUCache<Integer, String> cache = new UltimateLRUCache<>(3, 10, 15);

        cache.put(1, "A");
        cache.put(2, "B");
        cache.put(3, "C");

        System.out.println(cache.get(1)); // A

        cache.put(4, "D"); // 超出容量，自动淘汰最久未使用的（如 2）

        System.out.println(cache.get(2)); // null（被淘汰）
        System.out.println(cache.get(3)); // C
        System.out.println(cache.get(4)); // D

        // 模拟访问 1，延长其生命周期
        System.out.println(cache.get(1)); // A

        // 输出缓存统计信息
        System.out.println("Stats: " + cache.stats());
        System.out.println("Size: " + cache.size());

        // 查看当前缓存中的键值
        System.out.println("Current entries: " + cache.asMap());
    }
}

🚀 特性说明（“终极”理由）

特性	说明
线程安全	Caffeine 内部使用高性能并发结构，天然支持多线程
LRU 回收策略	默认基于最近最少使用淘汰，自动管理
过期机制	支持写入后过期（`expireAfterWrite`）、访问后过期（`expireAfterAccess`）
弱引用键	`.weakKeys()`：键可被 GC 回收，避免内存泄漏
软引用值	`.softValues()`：值在内存不足时被回收（可选，慎用）
统计功能	监控命中率、未命中、淘汰数量等
异步加载（可扩展）	可结合 `AsyncCache` 实现异步加载
高性能	比 Guava 和 ConcurrentHashMap 更快，尤其在高并发下

🔧 高级扩展：支持自动加载（Loading Cache）

import com.github.benmanes.caffeine.cache.LoadingCache;

LoadingCache<Integer, String> loadingCache = Caffeine.newBuilder()
    .maximumSize(100)
    .expireAfterWrite(10, TimeUnit.MINUTES)
    .recordStats()
    .build(key -> "default-" + key); // 自动加载函数

String value = loadingCache.get(1); // 如果不存在，自动加载

📊 输出示例（stats）

CacheStats{hitCount=3, missCount=1, hitRate=0.750, ...}

可用于监控缓存效率。

✅ 推荐配置组合（生产常用）

Caffeine.newBuilder()
    .maximumSize(1000)
    .expireAfterWrite(5, TimeUnit.MINUTES)
    .recordStats()
    .weakKeys()           // 键用弱引用
    .build();

⚠️ 注意：不要同时使用 softValues() 和 weakValues()，推荐优先使用 maximumSize + expireAfterWrite 控制内存。

✅ Spring Boot 2.6+ 集成Caffeine 缓存

第一步：添加依赖（Maven）

<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-cache</artifactId>
</dependency>
<dependency>
    <groupId>com.github.benmanes.caffeine</groupId>
    <artifactId>caffeine</artifactId>
</dependency>

第二步：启用缓存（Spring Boot 主类）

import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;
import org.springframework.cache.annotation.EnableCaching;

@SpringBootApplication
@EnableCaching  // 开启缓存注解支持
public class CacheApplication {
    public static void main(String[] args) {
        SpringApplication.run(CacheApplication.class, args);
    }
}

第三步：配置 Caffeine 缓存管理器

import com.github.benmanes.caffeine.cache.Caffeine;
import com.github.benmanes.caffeine.cache.RemovalListener;
import org.springframework.cache.CacheManager;
import org.springframework.cache.annotation.EnableCaching;
import org.springframework.cache.caffeine.CaffeineCache;
import org.springframework.cache.support.SimpleCacheManager;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;

import java.util.Arrays;
import java.util.concurrent.TimeUnit;

@Configuration
@EnableCaching
public class CaffeineCacheConfig {

    @Bean
    public CacheManager cacheManager() {
        SimpleCacheManager cacheManager = new SimpleCacheManager();

        CaffeineCache userCache = buildCache("userCache", 100, 10, 15);
        CaffeineCache orderCache = buildCache("orderCache", 50, 5, 10);

        cacheManager.setCaches(Arrays.asList(userCache, orderCache));
        return cacheManager;
    }

    private CaffeineCache buildCache(String name, int maxSize, long expireAfterWrite, long expireAfterAccess) {
        return new CaffeineCache(name,
            Caffeine.newBuilder()
                .maximumSize(maxSize)
                .expireAfterWrite(expireAfterWrite, TimeUnit.MINUTES)
                .expireAfterAccess(expireAfterAccess, TimeUnit.MINUTES)
                .weakKeys()
                .recordStats()
                .removalListener((RemovalListener<Object, Object>) (key, value, cause) -> {
                    System.out.println("Cache [" + name + "] - Key: " + key +
                        ", removed due to: " + cause);
                })
                .build());
    }
}

上面配置了两个缓存区：userCache 和 orderCache，可根据业务隔离。

第四步：在 Service 中使用缓存注解

import org.springframework.cache.annotation.Cacheable;
import org.springframework.cache.annotation.CachePut;
import org.springframework.cache.annotation.CacheEvict;
import org.springframework.stereotype.Service;

@Service
public class UserService {

    // 从缓存中获取，key = userId
    @Cacheable(value = "userCache", key = "#userId")
    public String getUserById(Integer userId) {
        System.out.println("Loading user from DB: " + userId);
        // 模拟数据库查询
        return "User-" + userId;
    }

    // 更新缓存
    @CachePut(value = "userCache", key = "#userId")
    public String updateUser(Integer userId, String name) {
        System.out.println("Updating user: " + userId + " -> " + name);
        return name;
    }

    // 删除缓存
    @CacheEvict(value = "userCache", key = "#userId")
    public void deleteUser(Integer userId) {
        System.out.println("Evicting user: " + userId);
    }

    // 清空整个缓存区
    @CacheEvict(value = "userCache", allEntries = true)
    public void clearUserCache() {
        System.out.println("Cleared userCache");
    }
}

第五步：测试使用（Controller 示例）

import org.springframework.web.bind.annotation.*;
import org.springframework.beans.factory.annotation.Autowired;

@RestController
public class UserController {

    @Autowired
    private UserService userService;

    @GetMapping("/user/{id}")
    public String getUser(@PathVariable Integer id) {
        return userService.getUserById(id);
    }

    @PutMapping("/user/{id}")
    public String updateUser(@PathVariable Integer id, @RequestParam String name) {
        return userService.updateUser(id, name);
    }

    @DeleteMapping("/user/{id}")
    public void deleteUser(@PathVariable Integer id) {
        userService.deleteUser(id);
    }

    @DeleteMapping("/cache/clear")
    public String clearCache() {
        userService.clearUserCache();
        return "User cache cleared";
    }
}

第六步：查看缓存统计信息（可选监控）

@Autowired
private CacheManager cacheManager;

@GetMapping("/cache/stats")
public String getStats() {
    org.springframework.cache.Cache cache = cacheManager.getCache("userCache");
    if (cache != null && cache.getNativeCache() instanceof com.github.benmanes.caffeine.cache.Cache) {
        var nativeCache = (com.github.benmanes.caffeine.cache.Cache<?, ?>) cache.getNativeCache();
        return nativeCache.stats().toString(); // 命中率、淘汰数等
    }
    return "Cache not found or stats not available";
}

配置说明（推荐用于生产）

配置项	推荐值	说明
`maximumSize`	1000~10000	控制内存使用，LRU 自动淘汰
`expireAfterWrite`	5~30 分钟	写入后过期，适合数据变更频繁场景
`expireAfterAccess`	10~20 分钟	最后一次访问后过期
`weakKeys()`	✅ 推荐	避免键导致内存泄漏
`recordStats()`	✅ 推荐	通过 `.stats()` 监控性能
`removalListener`	可选	可用于清理资源或打日志

🧩 高级：使用 `application.yml` 配置（可选）

虽然 Caffeine 不支持全配置化，但你可以通过 @ConfigurationProperties 自定义配置，实现动态化。例如：

cache:
  caffeine:
    user:
      maximum-size: 100
      expire-after-write: 10
      expire-after-access: 15

再通过 @ConfigurationProperties 注入配置，动态创建缓存。

LRU 算法实现

✅ 方法一：继承 LinkedHashMap（简单实现）