利用 LinkedHashMap 实现 LRU

面试时常会碰到面试官让你手撕一个 LRU，我们可以借用 Java 中 LinkedHashMap 的特性构建一个简易的 LRU。

LRU

Wiki 中对缓存文件置换机制（LRU 的父类）的描述是这样的：

缓存文件置换机制是电脑处理缓存存储器的一种机制。

电脑存储器空间的大小固定，无法容纳服务器上所有的文件，所以当有新的文件要被置换入缓存时，必须根据一定的原则来取代掉适当的文件。此原则即所谓缓存文件置换机制。

缓存文件置换方法有：

先进先出算法（FIFO）：最先进入的内容作为替换对象

最近最少使用算法（LFU）：最近最少使用的内容作为替换对象

最久未使用算法（LRU）：最久没有访问的内容作为替换对象

非最近使用算法（NMRU）：在最近没有使用的内容中随机选择一个作为替换对象

Belady’s Min

LinkedHashMap

LinkedHashMap 是 HashMap 的一个子类，底层使用 HashMap + 双向链表的混合结构，保存了记录的插入顺序，在用 Iterator 遍历 LinkedHashMap 时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。利用 LinkedHashMap 每次插入新数据时会在链首插入的特性可以实现 LRU 的功能，其中的 removeEldestEntry() 方法用于实现移除末尾元素，注意: 此类是非线程安全的。

实现代码

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

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

    public LRUCache(int cacheSize) {
        super(16, 0.75, true);
        this.cacheSize = cacheSize;
    }

    //方法返回 true 时会移除最老的元素
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() >= cacheSize;
    }
}

我们再稍微聊一下 LinkedHashMap 的构造函数，代码中可以看到调用了父类构造方法 super(16, 0.75, true); 我们看下 LinkedHashMap 的源码来理解这里的参数：

/**
* Constructs an empty <tt>LinkedHashMap</tt> instance with the
* specified initial capacity, load factor and ordering mode.
*
* @param  initialCapacity the initial capacity
* @param  loadFactor      the load factor
* @param  accessOrder     the ordering mode - <tt>true</tt> for
*         access-order, <tt>false</tt> for insertion-order
* @throws IllegalArgumentException if the initial capacity is negative
*         or the load factor is nonpositive
*/
public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {

    super(initialCapacity, loadFactor);
    
    this.accessOrder = accessOrder;
}

注释中写的很清楚了，这里细说一下，initialCapacity 初始化结构容量；loadFactor 为装载因子，当 size/capacity 超过装载因子时，容器会自动扩容避免发生溢出；accessOrder 默认为 false，控制结构是否按照读取顺序排序，默认为否，即使用插入顺序排序。