Java集合框架如何利用LinkedHashMap实现LRU缓存_Java集合框架特殊映射的应用技巧

LinkedHashMap

LinkedHashMap

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

/**
 * 一个基于LinkedHashMap实现的简单LRU缓存。
 * 当缓存大小超过预设的最大值时，会自动移除最近最少使用的条目。
 *
 * @param <K> 键的类型
 * @param <V> 值的类型
 */
public class LRUCache<K, V> extends LinkedHashMap<K, V> {

    private final int capacity;

    /**
     * 构造一个新的LRU缓存实例。
     *
     * @param capacity 缓存的最大容量。当缓存大小达到此值时，会触发LRU淘汰。
     */
    public LRUCache(int capacity) {
        // initialCapacity: 初始容量，可以根据预期大小调整
        // loadFactor: 负载因子，默认0.75
        // accessOrder: true表示按访问顺序排序，false表示按插入顺序排序。
        // LRU缓存需要按访问顺序，所以这里必须是true。
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    /**
     * 重写此方法以实现LRU淘汰策略。
     * 当此方法返回true时，LinkedHashMap会移除最老的条目。
     *
     * @param eldest 最近最少使用的条目。
     * @return 如果返回true，则移除eldest条目；否则不移除。
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // 当当前缓存大小超过容量时，返回true，LinkedHashMap会自动移除最老的条目。
        return size() > capacity;
    }

    // 示例用法
    public static void main(String[] args) {
        LRUCache<String, Integer> cache = new LRUCache<>(3);

        System.out.println("--- 首次添加元素 ---");
        cache.put("apple", 1); // {apple=1}
        cache.put("banana", 2); // {apple=1, banana=2}
        cache.put("cherry", 3); // {apple=1, banana=2, cherry=3}
        System.out.println("当前缓存: " + cache); // 预期输出：{apple=1, banana=2, cherry=3}

        System.out.println("\n--- 访问元素，改变顺序 ---");
        cache.get("apple"); // 访问apple，apple会移动到链表末尾，成为最近访问的
        System.out.println("访问apple后: " + cache); // 预期输出：{banana=2, cherry=3, apple=1}

        System.out.println("\n--- 添加新元素，触发淘汰 ---");
        cache.put("date", 4); // 添加date，容量超限，banana被淘汰
        System.out.println("添加date后: " + cache); // 预期输出：{cherry=3, apple=1, date=4} (banana被淘汰)

        System.out.println("\n--- 再次访问，再次改变顺序 ---");
        cache.get("cherry"); // 访问cherry，cherry移动到末尾
        System.out.println("访问cherry后: " + cache); // 预期输出：{apple=1, date=4, cherry=3}

        System.out.println("\n--- 添加新元素，再次触发淘汰 ---");
        cache.put("elderberry", 5); // 添加elderberry，容量超限，apple被淘汰
        System.out.println("添加elderberry后: " + cache); // 预期输出：{date=4, cherry=3, elderberry=5} (apple被淘汰)
    }
}

LinkedHashMap

HashMap

accessOrder=false

accessOrder=true

LinkedHashMap

accessOrder

true

get

put

LinkedHashMap

LinkedHashMap

removeEldestEntry

true

LinkedHashMap

LinkedHashMap

LinkedHashMap

LinkedHashMap

accessOrder

true

false

LinkedHashMap

LinkedHashMap

LRUCache

ConcurrentModificationException

LinkedHashMap

get

put

HashMap

removeEldestEntry

capacity