使用LinkedHashMap实现LRU

什么是LRU

LRU (Least Recently Used，最近最少使用) 是一种常见的缓存淘汰算法，它的基本思路是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小，那么就可以将其淘汰掉。

LRU实现原理

LRU可以使用哈希表和双向链表相结合的方式来实现，哈希表可以用来快速查找缓存中的数据，而双向链表可以用来维护数据的访问顺序。具体实现如下：

使用哈希表存储缓存数据，哈希表的key是缓存的键，value是缓存的值和双向链表中对应节点的指针。
使用双向链表维护缓存数据的访问顺序，链表的头节点存储的是最近访问的数据，尾节点存储的是最久未访问的数据。
当访问一个缓存数据时，如果数据存在于哈希表中，则将该数据对应的节点移动到链表头部；如果不存在，则在哈希表和链表头部分别插入新节点。
当缓存数据达到容量上限时，将链表尾部的节点删除，并从哈希表中删除对应的键值对。

Java实现LRU

在Java中，可以使用LinkedHashMap来实现LRU算法。LinkedHashMap是一个基于哈希表和双向链表实现的Map，它可以按照插入顺序或者访问顺序来迭代元素。通过重写removeEldestEntry方法，可以实现LRU算法。

javaCopy code
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private int capacity;
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

在LRUCache类中，构造函数中传入的0.75f表示负载因子，true表示使用访问顺序来迭代元素。重写的removeEldestEntry方法中，如果LRUCache的大小超过了容量上限，则返回true，LinkedHashMap会自动删除最久未访问的元素。

LinkedHashMap是HashMap的一个子类，它在HashMap的基础上增加了维护插入顺序或访问顺序的功能。而accessOrder就是LinkedHashMap中一个用于控制维护顺序的参数。 accessOrder是一个boolean类型的参数，它有两个可选值：

false，表示维护插入顺序,元素插入到LinkedHashMap中的顺序就是它们在LinkedHashMap中的顺序。
true，当accessOrder设置为true时，LinkedHashMap会按照元素的访问顺序来维护元素的顺序。也就是说，当我们访问一个元素时，它会被移动到链表的尾部，表示它是最近访问的元素。这样，我们就可以通过访问顺序来实现LRU缓存的功能。下面是一个使用accessOrder的例子，我们可以看到当accessOrder为true时，元素的顺序是按照访问顺序来维护的：

import java.util.LinkedHashMap;
import java.util.Map;
public class LinkedHashMapDemo {
    public static void main(String[] args) {
        Map<Integer, String> map = new LinkedHashMap<>(4, 0.75f, true);
        map.put(1, "one");
        map.put(2, "two");
        map.put(3, "three");
        map.put(4, "four");
        System.out.println(map); // {1=one, 2=two, 3=three, 4=four}
        map.get(2);
        map.get(3);
        System.out.println(map); // {1=one, 4=four, 2=two, 3=three}
    }
}

在LinkedHashMap中，当访问一个已经存在的节点时，会将该节点移动到链表尾部，而不是链表头部。具体实现可以参考LinkedHashMap类中的afterNodeAccess方法和afterNodeInsertion方法。在afterNodeAccess方法中，会将已经存在的key的节点从双向链表中删除，然后将其插入到链表尾部。在afterNodeInsertion方法中，调用重写的 removeEldestEntry如果返回true ，则删除链表头的节点。从而实现了LRU算法。