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;   } } 

原文发布于微信公众号 - 我是攻城师(woshigcs)

原文发表时间:2015-07-17

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏微信公众号:Java团长

理解Java的三大特性之封装

封装从字面上来理解就是包装的意思,专业点就是信息隐藏,是指利用抽象数据类型将数据和基于数据的操作封装在一起,使其构成一个不可分割的独立实体,数据被保护在抽象数据...

1082
来自专栏java一日一条

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

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

952
来自专栏Jerry的SAP技术分享

为什么ABAP整型的1转成string之后,后面会多个空格

有同事问这个问题:lv_s是从int4转过来的,长度为2,和硬编码的lv_s2(长度为1)相比,后面多了个空格。

1490
来自专栏Java架构沉思录

你真的懂Java中的String、StringBuilder和StringBuffer吗?

相信String这个类是Java中使用得最频繁的类之一,并且又是各大公司面试喜欢问到的地方,今天就来和大家一起学习一下String、StringBui...

1713
来自专栏Albert陈凯

编译型语言、解释型语言、静态类型语言、动态类型语言、强类型语言、弱类型语言概念与区别

编译型语言和解释型语言 1、编译型语言 需通过编译器(compiler)将源代码编译成机器码,之后才能执行的语言。一般需经过编译(compile)、链接(li...

44311
来自专栏小俊博客

Nginx的location规则迷之匹配

Nginx,一个改变世界的软件,其作者是一个俄罗斯人,俗称毛子,在国人的印象中,是一群晚饭后牵着大灰熊在小区楼下散步的彪汉。能写出这般顺滑的软件,可谓是心有猛虎...

6672
来自专栏Java技术分享圈

杨老师课堂_Java教程第五篇之函数运用

今天主要是讲解以下知识点: 1、方法基础知识 2、方法高级内容 3、方法案例

1002
来自专栏MelonTeam专栏

深入理解C++11(一)

导语 从最初的代号C++0x到最终的名称C++11,C++的第二个真正意义上的标准姗姗来迟。 C++11是一种新语言的开端。虽然设计C++11的目...

2009
来自专栏Modeng的专栏

Javascript数组系列一之栈与队列

所谓数组(英语:Array),是有序的元素序列。 若将有限个类型相同的变量的集合命名,那么这个名称为数组名。 组成数组的各个变量称为数组的分量,也称为数组的元素...

1445
来自专栏诸葛青云的专栏

C语言初学者必须掌握的关键字!

其实小伙伴在写代码的时候,关键字还是用的比较多的,老九主要就平常中用到的常用关键字进行总结,便于小伙伴们更全面的理解其在代码中的意图。

620

扫码关注云+社区

领取腾讯云代金券