专栏首页java一日一条10行Java代码实现最近被使用(LRU)缓存

10行Java代码实现最近被使用(LRU)缓存

在最近的面试中,我曾被多次问到,怎么实现一个最近最少使用(LRU)的缓存。缓存可以通过哈希表来实现,然而为这个缓存增加大小限制会变成另一个有意思的问题。现在我们看一下怎么实现。

最近最少使用缓存的回收

为了实现缓存回收,我们需要很容易做到:

  • 查询出最近最晚使用的项
  • 给最近使用的项做一个标记

链表可以实现这两个操作。检测最近最少使用的项只需要返回链表的尾部。标记一项为最近使用的项只需要从当前位置移除,然后将该项放置到头部。比较困难的事情是怎么快速的在链表中找到该项。

哈希表的帮助

看一下我们工具箱中的数据结构,哈希表可以在(消耗)常量的时间内索引到某个对象。如果我们创建一个形如key->链表节点的哈希表,我们就能够在常量时间内找到最近使用的节点。更甚的是,我们也能够在常量时间内判断节点的是否存在(或不存在);

找到这个节点后,我们就能将这个节点移动到链表的最前端,标记为最近使用的项了。

Java的捷径

据我所知,很少有一种编程语言的标准库中有通用的数据结构能提供上述功能的。这是一种混合的数据结构,我们需要在哈希表的基础上建立一个链表。但是Java已经为我们提供了这种形式的数据结构-LinkedHashMap!它甚至提供可覆盖回收策略的方法(见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;
  }
 
  protected boolean removeEldestEntry
(Map.Entry<K, V> eldest) {
    return size() >= cacheSize;
  }
}

原文链接: Chriswu 翻译: ImportNew.com - paddx

本文分享自微信公众号 - java一日一条(mjx_java),作者:小马哥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2015-07-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 15 个 Android 通用流行框架大全

    Android自带很多测试工具:JUnit,Monkeyrunner,UiAutomator,Espresso等

    哲洛不闹
  • 也谈如何构建高性能服务端程序

    引子:我接触过很多编程语言,接触过各种各样的服务器端开发,Java,Go,Ruby,Javascript等语言,Spring,Node.js,Rails等等常见...

    哲洛不闹
  • 30多年程序员生涯经验总结

    在我30多年的程序员生涯里,我学到了不少有用的东西。下面是我这些年积累的经验精华。我常常想,如果以前能有人在这些经验上指点一二,我相信我现在会站得更高。

    哲洛不闹
  • 10行Java代码实现最近被使用(LRU)缓存

    我是攻城师
  • 图解LeetCode第 2 号问题:两个数字相加

    设立一个表示进位的变量carried,建立一个新链表,把输入的两个链表从头往后同时处理,每两个相加,将结果加上carried后的值作为一个新节点到新链表后面。

    五分钟学算法
  • 【推荐阅读】大数据用户画像的方法、实践与行业应用

    本文作者:刘译璟

    钱塘数据
  • 使用神经网络和深度学习构造围棋智能算法:实现棋盘落子编码

    在前面章节中,我们引入不少算法和数据结构用以支持围棋机器人实现。由于围棋的步骤组合太多,几乎没有确定性的算法能在合理的时间内给出好的走法。从本节开始,我们将像A...

    望月从良
  • Arkin Net引领SDN网络可视化新浪潮

    近来,业界流传了很多关于网络可见性和软件定义网络的信息。初创公司Arkin Net最近透露了其在这两项上的最新研究进展。 该公司由ex-Cloud.com和Nu...

    SDNLAB
  • 前端面试题总结(持续更新。。)

    Ewall
  • 算法集锦(25)| DeepMind(里程碑式进展)新AI框架可实现临床级眼科3维图像的精确诊断

    DeepMind提出了一个里程碑式的新AI框架,可以对眼科诊断中的三维扫描图像进行准确诊断,准确率达到甚至超过了专家水准。有关成果已在Nature发表。

    用户7623498

扫码关注云+社区

领取腾讯云代金券