Java 实现 LRU 缓存

最近面美团基础数据平台部的时候碰到一个面试题，问如何实现LRU缓存算法，感觉挺有意思的，既考察了操作系统，又考察了对JDK中util工具的掌握程度，还可以考察算法设计和对缓存的理解功底。

LRU的原理

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，把最近一次使用时间离现在时间最远的数据删除掉，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

利用JDK中LinkedHashMap

在构造LinkedHashMap的时候可以选择一个参数`accessOrder`，默认为`false`，map内部会按照插入顺序进行维护。如果手动把它设置为`true`，那么map内部会按照访问顺序进行维护。

public class Main {
    public static void main(String[] args) {
        Map<String, String> map = new LinkedHashMap<>(16, 0.75f, true);
        map.put("a", "1");
        map.put("b", "2");
        map.put("c", "3");
        map.put("d", "4");
        System.out.println(map);
        map.get("a");
        map.get("b");
        System.out.println(map);
    }
}

程序输出为：

{a=1, b=2, c=3, d=4}
{c=3, d=4, a=1, b=2}

如果把LinkedHashMap的构造改为默认的`map = new LinkedHashMap<>();`，则对应的输出为：

{a=1, b=2, c=3, d=4}
{a=1, b=2, c=3, d=4}

可以看到，只要我们把`accessOrder`设为`true`，就会把最近访问的元素放在最后。

实现LRU缓存

我们都知道LinkedHashMap内部实际上比普通Map多了一个双向链表，以此来维护顺序。

LinkedHashMap也提供了一个方法`removeEldestEntry`，只要重写这个方法，就很容易实现LRU的cache。这个方法的注释是这样写的：

/**
 * Returns <tt>true</tt> if this map should remove its eldest entry.
 * This method is invoked by <tt>put</tt> and <tt>putAll</tt> after
 * inserting a new entry into the map.  It provides the implementor
 * with the opportunity to remove the eldest entry each time a new one
 * is added.  This is useful if the map represents a cache: it allows
 * the map to reduce memory consumption by deleting stale entries.
 */

意思是说，当调用map的`put`和`putAll`方法后会调用`removeEldestEntry()`检查是否应该删除eldest元素。我们来重写这个方法并做测试：

public class Main {
    public static void main(String[] args) {
        Map<String, String> map = new LinkedHashMap<String, String>(16, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
                return size() > 3;
            }
        };
        map.put("a", "1");
        map.put("b", "2");
        map.put("c", "3");
        System.out.println(map);
        map.get("a");
        map.get("b");
        System.out.println(map);
        map.put("d", "4");
        System.out.println(map);
    }
}

运行结果：

{a=1, b=2, c=3}
{c=3, a=1, b=2}
{a=1, b=2, d=4}

可以看到，我们构造了一个大小为3的LRU缓存，当插入第4个元素`d`的时候，把`c`这个最久未访问的元素删掉了。

自己实现？

我们可以自己用一个双向链表来实现LRU缓存：

当新数据插入时添加到链表尾部
当缓存命中时，将数据移动到链表尾部
当链表满时，把链表头部的数据删除
为了方便查找数据，可以使用一个普通map，在map和链表节点之间做引用映射

其实这就很像LinkedHashMap的内部实现了，感兴趣的童鞋可以看看源码