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的内部实现了,感兴趣的童鞋可以看看源码

上一篇:LRUcache


下一篇:JDK1.8源码(九)——java.util.LinkedHashMap 类