使用LinkedHashMap实现固定大小的LRU缓存

1. 什么是LRU？

LRU是”Least Recently Used”的缩写，意为”最近最少使用”。LRU缓存是一种常用的缓存淘汰算法，它的核心思想是：当缓存满时，优先淘汰最近最少使用的项目。

LRU缓存的工作原理：

新数据插入到缓存头部
每当缓存命中（即缓存数据被访问），则将数据移到缓存头部
当缓存满时，将链表尾部的数据丢弃

LRU算法的理论基础：

LRU算法基于”时间局部性原理”（Principle of Temporal Locality），该原理指出，如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。这一原理在计算机科学中广泛应用，例如在操作系统的页面置换算法中。

LRU的应用场景：

数据库缓存：减少对数据库的直接访问，提高查询速度
Web应用：缓存经常访问的页面或数据
硬件设计：CPU缓存的替换策略
操作系统：页面置换算法

2. LinkedHashMap与LRU缓存

LinkedHashMap的特性：

LinkedHashMap是Java集合框架中的一个类，它继承自HashMap，但在内部维护了一个双向链表，用于保持插入顺序或访问顺序。

关键特性：

可选的排序模式：插入顺序（默认）或访问顺序
预测遍历顺序：可以按照特定顺序遍历元素
性能：大部分操作的时间复杂度为O(1)

LinkedHashMap如何支持LRU：

LinkedHashMap通过以下机制支持LRU缓存的实现：

访问顺序：通过构造函数的accessOrder参数设置为true，启用访问顺序模式
自动重排序：每次访问元素时，该元素会被移到链表末尾（最近使用）
removeEldestEntry方法：允许在插入新元素时，决定是否删除最老的元素

继承LinkedHashMap并重写removeEldestEntry方法：

要实现LRU缓存，我们需要：

创建一个新类，继承LinkedHashMap
在构造函数中，设置LinkedHashMap的访问顺序为true
重写removeEldestEntry方法，当map中的元素个数超过指定容量时返回true

3. 代码实现与深入分析

代码实现：

以下是一个简洁的LRU缓存实现，包含了基本功能和性能监控：

LRUCache.java

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

/**
 * @desc: 使用LinkedHashMap自定义LRU缓存实现
 * @author: shy
 * @date: 2024/08/26 10:03
 */
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    // 命中数（性能监控）
    private int hits = 0;
    // 未命中数（性能监控）
    private int misses = 0;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }

    @Override
    public V get(Object key) {
        V value = super.get(key);
        if (value != null) {
            hits++;
        } else {
            misses++;
        }
        return value;
    }

    public double getHitRate() {
        int total = hits + misses;
        return total == 0 ? 0 : (double) hits / total;
    }
}

MapTest.java

public class MapTest {
    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);
        cache.put(1, "one");
        cache.put(2, "two");
        cache.put(3, "three");
        System.out.println(cache); // 输出: {1=one, 2=two, 3=three}
        cache.get(1);
        System.out.println(cache); // 输出: {2=two, 3=three, 1=one}

        cache.put(4, "four");
        System.out.println(cache); // 输出: {3=three, 1=one, 4=four}

        // 输出缓存命中率
        System.out.println("Hit rate: " + cache.getHitRate());
    }
}