文档章节

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

Simon丶Ma
 Simon丶Ma
发布于 2016/04/14 14:45
字数 576
阅读 7
收藏 0

在最近的面试中,我曾被多次问到,怎么实现一个最近最少使用(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;
  }
}

 

© 著作权归作者所有

Simon丶Ma
粉丝 4
博文 134
码字总数 299850
作品 0
深圳
程序员
私信 提问
Ehcache和MemCached比较分析

项目 Memcache Ehcache 分布式 不完全,集群默认不实现 支持 集群 可通过客户端实现 支持(默认是异步同步) 持久化 可通过第三方应用实现,如sina研发的memcachedb,将cache的数据保存到[ur...

浮躁的码农
2015/07/24
2.2K
0
Guava 源码分析(Cache 原理)

前言 Google 出的 Guava 是 Java 核心增强的库,应用非常广泛。 我平时用的也挺频繁,这次就借助日常使用的 Cache 组件来看看 Google 大牛们是如何设计的。 缓存 本次主要讨论缓存。 缓存在日...

crossoverJie
2018/06/13
0
0
Guava 源码分析之Cache的实现原理

前言 Google 出的 Guava 是 Java 核心增强的库,应用非常广泛。 我平时用的也挺频繁,这次就借助日常使用的 Cache 组件来看看 Google 大牛们是如何设计的。 缓存 本次主要讨论缓存。缓存在日...

crossoverJie
2018/01/20
0
0
有关 SoftReference 的一些事实

Java 的 SoftReference 有很多年都没有被人惦记了。在 Javadoc 里, 它的描述是这样: ”虚拟机在抛出 OutOfMemoryError 之前会保证所有的软引用对象已被清除。此外,没有任何约束保证软引用将...

长源
2013/08/12
0
0
Retrofit 风格的 RxCache及其多种缓存替换算法

RxCache 是一个支持 Java 和 Android 的 Local Cache 。 之前的文章《给 Java 和 Android 构建一个简单的响应式Local Cache》、《RxCache 整合 Android 的持久层框架 greenDAO、Room》曾详细...

fengzhizi715
2018/11/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
今天
5
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
今天
7
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
今天
6
0
【技术分享】TestFlight测试的流程文档

上架基本需求资料 1、苹果开发者账号(如还没账号先申请-苹果开发者账号申请教程) 2、开发好的APP 通过本篇教程,可以学习到ios证书申请和打包ipa上传到appstoreconnect.apple.com进行TestF...

qtb999
今天
10
0
再见 Spring Boot 1.X,Spring Boot 2.X 走向舞台中心

2019年8月6日,Spring 官方在其博客宣布,Spring Boot 1.x 停止维护,Spring Boot 1.x 生命周期正式结束。 其实早在2018年7月30号,Spring 官方就已经在博客进行过预告,Spring Boot 1.X 将维...

Java技术剑
今天
18
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部