Java实现LRU算法

LRU（Least Recently Used）算法是一种常见的缓存淘汰算法，Java中可以通过LinkedHashMap来实现。

LinkedHashMap是HashMap的一个子类，它具有HashMap的所有特性，同时还维护了一个双向链表，用于记录元素的插入顺序或访问顺序。因此，在使用LinkedHashMap时，可以通过设置accessOrder参数为true，使其按照访问顺序来排列元素，实现LRU算法。

以下是一个简单的Java代码实现LRU算法的示例：

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

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private int cacheSize;  // 缓存大小

    public LRUCache(int cacheSize) {
        super(16, 0.75f, true);  // accessOrder设置为true，按访问顺序排序
        this.cacheSize = cacheSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > cacheSize;  // 当缓存大小超过设定值时，移除最老的元素
    }

    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.put(4, "d");
        System.out.println(cache);  // 输出{2=b, 3=c, 4=d}
        cache.get(2);
        System.out.println(cache);  // 输出{3=c, 4=d, 2=b}
    }
}

在上述示例中，LRUCache继承自LinkedHashMap，并重写了removeEldestEntry方法，当缓存大小超过设定值时，移除最老的元素。在main方法中，先向缓存中添加三个元素，然后再添加一个新的元素，此时缓存大小超过了设定值，因此最老的元素（1=a）被移除，输出{2=b, 3=c, 4=d}。接下来，通过get方法访问了元素2，使得元素2成为最近访问的元素，输出{3=c, 4=d, 2=b}。