LRU缓存淘汰策略的实现——LinkedHashMap哈希链表

本文介绍: 需要重写 r emo v eEldestEntry 方法，在缓存容量超过设置的上限时，移除最老的缓存项。哈希表用于快速获取缓存项，而双向链表用于保持缓存项的顺序，最近使用的项在链表的末尾，最少使用的项在链表的开头。：使用 put 方法向缓存中存入键值对，使用 get 方法获取指定键对应的值。通过Lin k e dHa shMap的特性，最近访问的缓存项会被移动到链表尾部，从而实现LRU淘汰。Lin k e dHa shMap 是 Jav a 中提供的一种数据结构，它综合了哈希表和双向链表的特点，非常适合用来实现 LRU 缓存。

LRU（最近最少使用）缓存淘汰策略可以通过使用哈希链表实现。Lin k e dHa shMap 是 Java 中提供的一种数据结构，它综合了哈希表和双向链表的特点，非常适合用来实现 LRU 缓存。

Lin k e dHashMap 内部维护了一个哈希表和一个双向链表。哈希表用于快速获取缓存项，而双向链表用于保持缓存项的顺序，最近使用的项在链表的末尾，最少使用的项在链表的开头。
!](https://img-blog.csdnimg.cn/direct/f9e5d26f64994d68b0e72186f7326e00.png)

如何使用 Lin k e dHashMap 实现 LRU 缓存淘汰策略(Java实现)：

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

public class LRUCache&lt;K, V&gt; extends LinkedHashMap&lt;K, V&gt; {
    private final int capacity;

    public LRUCache(int capacity) {
        // 设置 accessOrder 参数为 true，使得 LinkedHashMap 按访问顺序排序
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry&lt;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); // 输出：{1=A, 2=B, 3=C}

        cache.get(2); // 模拟访问缓存项 2

        cache.put(4, "D"); // 超出容量，触发淘汰策略，移除最老的缓存项

        System.out.println(cache); // 输出：{2=B, 3=C, 4=D}
    }
}

我们定义了一个 LRUCache 类继承自 LinkedHashMap，并重写了 removeEldestEntry 方法来控制是否移除最老的缓存项。需要注意以下几点：
1、构造函数：在构造LRUCac he时，需要指定容量和装载因子，并将accessOrder参数设置为true，以便使LinkedHas hMap按访问顺序排序。
2、removeEldestEntry 方法：需要重写 rem oveEldestEntry 方法，在缓存容量超过设置的上限时，移除最老的缓存项。默认实现为返回 false，即不移除任何缓存项，需要修改为返回 size() > capacity时返回 true。
3、缓存操作：使用put方法向缓存中存入键值对，使用get 方法获取指定键对应的值。通过LinkedHashMap的特性，最近访问的缓存项会被移动到链表尾部，从而实现LRU淘汰。