Java实现LRU缓存

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

LRU的原理

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

利用JDK中LinkedHashMap

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

程序输出为:

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

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

实现LRU缓存

我们都知道LinkedHashMap内部实际上比普通Map多了一个双向链表,以此来维护顺序。LinkedHashMap也提供了一个方法removeEldestEntry,只要重写这个方法,就很容易实现LRU的cache。

这个方法的注释是这样写的:

意思是说,当调用map的putputAll方法后会调用removeEldestEntry()检查是否应该删除eldest元素。

我们来重写这个方法并做测试:

运行结果:

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

自己实现?

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

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

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

1 条评论

发表评论

电子邮件地址不会被公开。