用Java写一个LRU置换算法

LRU（Least Recently Used）置换算法是一种常用的缓存淘汰算法。它的核心思想是基于时间局限性原理，如果数据最近被访问，则在将来被访问的概率更大。而如果数据较久未被访问，则在将来被访问的概率更低。因此，可以将缓存中最近最少使用的数据替换掉。

下面是用Java实现的LRU置换算法：

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

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

    public LRUCache(int capacity) {
        // 第三个参数设置为true，表示使用访问顺序排序
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

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

    public static void main(String[] args) {
        LRUCache<String, Integer> cache = new LRUCache<>(2);
        cache.put("a", 1);
        cache.put("b", 2);
        System.out.println(cache); // {a=1, b=2}
        cache.put("c", 3);
        System.out.println(cache); // {b=2, c=3}
        cache.get("b");
        System.out.println(cache); // {c=3, b=2}
        cache.put("d", 4);
        System.out.println(cache); // {b=2, d=4}
    }
}

这里使用了Java内置的LinkedHashMap作为缓存数据结构，重写了removeEldestEntry方法判断是否需要移除最久未使用的元素。在LRUCache的构造函数中，通过传入accessOrder参数为true，表示使用访问顺序排序，即最近被访问的元素排在最前面。当缓存已满需要移除元素时，LinkedHashMap会自动删除最近最少使用的元素，从而实现了LRU策略。