【揭秘】如何使用LinkedHashMap来实现一个LUR缓存？

LRU（Least Recently Used）缓存是一种常用的缓存淘汰策略，用于在有限的缓存空间中存储数据。其基本思想是：如果数据最近被访问过，那么在未来它被访问的概率也更高。因此，LRU缓存会保留最近访问过的数据，并在缓存满时淘汰最久未使用的数据

定义

LRU（Least Recently Used）缓存是一种常用的缓存淘汰策略，用于在有限的缓存空间中存储数据，其基本思想是，如果数据最近被访问过，那么在未来它被访问的概率也更高，因此，LRU缓存会保留最近访问过的数据，并在缓存满时淘汰最久未使用的数据，代码实现思路如下：

1. 插入新的数据项。
2. 访问（或检索）现有的数据项，并将其标记为最近使用。
3. 当缓存达到其容量限制时，删除最久未使用的数据项。

代码案例

为了演示LRU，使用LinkedHashMap类来实现一个LUR缓存，因为它内部已经处理了哈希表和双向链表，哈希表提供了快速的插入和查找操作（平均时间复杂度为O(1)），而双向链表则维护了元素的插入顺序或访问顺序（取决于构造函数的参数），代码如下：

import java.util.LinkedHashMap;  
import java.util.Map;  
  
public class LRUCache<K, V> extends LinkedHashMap<K, V> {  
    private int cacheSize;  
  
    public LRUCache(int cacheSize) {  
        // 第三个参数设置为true表示应该按照访问顺序排序，最近访问的放在头部，最老访问的放在尾部  
        super(16, 0.75f, true); // 可以使用一个默认的初始容量，例如16  	
        this.cacheSize = cacheSize;  
    }  
  
    @Override  
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {  
        // 当map中的数据量大于指定的缓存个数的时候，就自动删除最老的数据（即尾部的数据）  
        return size() > cacheSize;  
    }  
}

在上面的代码中，LRUCache类继承了LinkedHashMap并重写了removeEldestEntry方法，这个方法的默认实现总是返回false，意味着不会自动移除最老的条目，但是在实现中，当缓存的大小超过了指定的cacheSize时，该方法返回true，触发移除最久未使用的条目（也就是链表中的尾部元素）。

此外，通过将LinkedHashMap的构造函数中的accessOrder参数设置为true，让链表按照访问顺序来排序元素，这样，最近访问的元素会被放在链表的头部，而最久未访问的元素则会被放在尾部，当需要移除元素时，可以快速地移除链表尾部的元素。

这个设计思想利用了哈希表的高效查找和链表的顺序性来实现一个简单而有效的LRU缓存，通过重写一个方法，能够定制缓存的行为以符合LRU策略。

public static void main(String[] args) {  
    LRUCache<Integer, String> lruCache = new LRUCache<>(3);  
    lruCache.put(1, "one");    // 缓存是 {1="one"}  
    lruCache.put(2, "two");    // 缓存是 {1="one", 2="two"}  
    lruCache.put(3, "three");  // 缓存是 {1="one", 2="two", 3="three"}  
    lruCache.get(1);           // 最近访问的是1，缓存是 {2="two", 3="three", 1="one"}  
    lruCache.put(4, "four");   // 因为缓存容量只有3，所以移除最老的条目2，缓存变为 {3="three", 1="one", 4="four"}  
}

核心总结

使用LinkedHashMap实现LRU非常简单且高效，当业务比较简单、或者用来演示LRU的实现是没有啥问题的，它本身有一些限制，因此不适合用在线上，如下：

1、它不是线程安全的，如果多个线程同时访问这个LRU缓存，可能会导致数据不一致的问题，根本在于LinkedHashMap本身并不是线程安全的，所以在多线程环境下，需要额外的同步措施，比如使用Collections.synchronizedMap方法来包装这个缓存，或者在访问时加上同步块。

2、它没办法自动处理数据加载以及数据过期，在实际应用中，有时希望当缓存中不存在请求的数据时能够自动从数据库或其他数据源加载数据，或者当数据在一定时间内没有被访问时能够自动过期。

3、它没办法精准控制内存使用，虽然可以限制缓存中的条目数量，但是这个限制并不直接对应于内存使用量，不同的缓存条目可能占用不同大小的内存，所以这个简单的LRU缓存可能会导致内存溢出，尤其是在存储大对象时。

4、它很难扩展，由于这个实现是基于LinkedHashMap的，它的扩展性受到了一定的限制，如果需要更复杂的缓存行为或更高级的功能（比如缓存分区、备份、持久化等），它是做不到的。