位置: 编程技术 - 正文

深入源码剖析LruCache(如何分析源码)

编辑:rootadmin

推荐整理分享深入源码剖析LruCache(如何分析源码),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:quagga源码分析,源码分析怎么写,xen源码分析,源码分析怎么写,源码分析是什么意思,源码分析怎么写,源码分析,源码分析怎么写,内容如对您有帮助,希望把文章链接给更多的朋友!

引言:最近许多人在博客中提到自己在面试时被问“LruCache 的原理是?”,发现自己之前完全没有接触过这个知识点,本着知其然知其所以然的态度,先搜索了一些博文了解相关知识,就去看源码了。现在大概知道 LruCache 是啥,写个博文权当是学习笔记把

LruCache 的前世今生LruCache 是何方神圣?

我一般不喜欢野路子的定义,所以我摘选了 Android 官方对 LruCache 的定义:

A cache that holds strong references to a limited number of values. Each time a value is accessed, it is moved to the head of a queue. When a value is added to a full cache, the value at the end of that queue is evicted and may become eligible for garbage collection.

定义的意思是:LruCache 是对限定数量的缓存对象持有强引用的缓存,每一次缓存对象被访问,都会被移动到队列的头部。当有对象要被添加到已经达到数量上限的 LruCache 中,队列尾部的对象将会被移除,而且可能会被垃圾回收机制回收。

所以从定义里我们可以知道:LruCache 中有一个队列存储对象的访问顺序,在 LruCache 达到存储上线时,将会通过移除队列中的队尾元素为需要添加进来的元素腾出空间。

LruCache 中的队列的存在意义是什么?

要探讨这个问题首先我们要知道的是:LruCache 中的 Lru 指的是“Least Recently Used-近期最少使用算法”。这就意味着,LruCache 应该是一个能够判断哪个缓存对象是近期最少使用的缓存类。解释到这里我相信大家都能明白为什么需要引入队列了。

引入队列的意义在于,每一次 LruCache 中的某个缓存对象被访问,该对象在队列中的位置就会发生改变——即提到队列的头部,假设队列有 n 个元素,n-1 个元素都被不同频率地访问过,唯独元素 A 一直没有被访问,那么 A 必然处于队尾,成为“近期最少使用元素”了。

LruCache 的实现原理LruCache 初步源码分析

代码太多,我不可能全都贴上来,所以我就按照我的思路来贴啦~

从代码里我们可以知道:LruCache 不是其他类的子类,并且其中实际涉及到的只有一个 LinkedHashMap 对象和一堆 int 值。也就是说,LruCache 实现其核心逻辑的关键应该就是 LinkedHashMap。

那我们就先来看看 LinkedHashMap的源码吧。

LinkedHashMap 剖析LinkedHashMap 是什么

同样的,引用官方的解释:

LinkedHashMap is an implementation of Map that guarantees iteration order. All optional operations are supported.

Entries are kept in a doubly-linked list. The iteration order is, by default, the order in which keys were inserted. Reinserting an already-present key doesn’t change the order. If the three argument constructor is used, and accessOrder is specified as true, the iteration will be in the order that entries were accessed. The access order is affected by put, get, and putAll operations, but not by operations on the collection views.

LinkedHashMap 是 Map 的一种实现(HashMap 的子类,HashMap 的父类是抽象 Map 类,其中实现了 Map 接口),能够保证迭代器的顺序。LinkedHashMap 中的数据通过一个双向链表存储,默认情况下,迭代器的顺序为键的掺入顺序,并且重新插入一个已经存在的键不会改变迭代器的顺序。

如果构造方法中的第三个参数 boolean accessOrder 被使用,而且 accessOrder 的值为 true,那么迭代器的顺序就是数据的访问顺序,并且,这个顺序将受 put,get,putall 这些方法影响,但不受集合视图操作的影响。

LinkedHashmap 的解释证明了我们刚刚的猜测 LruCache 实现其核心逻辑的关键应该就是 LinkedHashMap 是对的,那么我们只要弄懂了 LinkedHashpMap 的具体原理,LruCache 的原理也不是问题了。

LinkedHashMap 使用范例

在分析 LinkedHashMap 之前,我们不妨先看看 LinkedHashMap 到底能干些什么,毕竟从他的外在表现去分析内在逻辑会更轻松些,下面是一段简单的 Java 代码:

深入源码剖析LruCache(如何分析源码)

这是输出:

处理前 one two three 处理后 two three one

我们可以看到,处理后 one 的位置显然发生了改变,跑到了 two,three 的前面。

LinkedHashMap 实现原理

我们直接看 LinkedHashMap 中相关的第三个构造方法吧:

我们可以看到,构造方法调用了父类的构造方法,创建了一个 LinkedEntry 对象,并把 accessOrder 的值设为构造方法传入的值。那这个 LinkedEntry 是什么呢?

我们可以看到,LinkedEntry 就是用于存储数据的双向链表。所以,我们现在只需要知道 LinkedHashMap 类是如何根据 accessOrder 的值,决定程序使用 get,put 等方法将如何操作 LinkedEntry 就可以知道一整个 LinkedHashMap 的实现原理了。

我们追踪 accessOrder 的值很容易发现在 get 方法中有相应的处理:

从代码中可以看到,只要 accessOrder 为 true,就会执行 makeTail 方法操作一个新建的 LinkedEntry 对象,我们不妨进入 makeTail 方法一探究竟:

相信这里的逻辑稍微学过数据结构的朋友都能看懂了,就是改变某个结点的位置,把它放到头部。

get 带来的队列变化我们是知道了,那 put 呢?我们一搜索 put,发现类里没有这个方法,这是什么鬼……莫慌,我们耐心地翻翻代码会发现 addNewEntry(K key, V value, int hash, int index) 和 addNewEntryForNullKey(V value) 方法,而它们就是实现 put 改变队列逻辑的两个方法了,我们不妨看看:

addNewEntry 方法中,当有新元素加入时就会执行进行判断,决定是否移除过期的元素,当我们进入 removeEldestEntry 方法会发现,removeEldestEntry 方法的返回值恒为 false,也就是说过期元素无论如何都不会被移除,那这是什么意思呢?

其实这挺好理解的,LinkedHashMap 作为一个存储结构,它并没有限制自身的存储容量(因为他的实现基于一个双向链表),所以他没有理由在默认实现中移除过期元素,而 LruCache 中则是自己设计了相应的逻辑去处理过期元素。

再探 LruCache

通过刚刚的分析,我们已经知道 LruCache 的核心 LinkedHashMap 是如何提取“近期最少使用对象”的了,那么 LruCache 中还利用 LinkedHashMap 的特性做了什么事呢?大家跟着我继续探索吧~

通过 get/put 方法我们可以知道,LruCache 是通过 trimToSize 来控制其中的元素数量的,当达到数量上限,添加元素则会将过期元素移除:

代码首先作一些简单判断,只有 size > maxSize 才会执行相关逻辑:遍历 LinkedHashMap 双向链表的元素,取得队列尾部的元素(就是我们所说的过期元素),如果它不为空,就将它移除。

注意事项

1、如果你的缓存对象持有需要被精确回收的资源,重写 entryRemoved 方法能完成你的需求。

2、默认情况下,缓存空间的大小由元素的数量决定,但你可以在不同的单元中重写 sizeOf 方法改变大小。例如:bitmap 对象大小为 4m

3、传入 LruCache 的键值对不能是 null,因为 get/put/remove 方法的含义会因此变得模糊。

adb push、adb install 和强制安装 1.adbpushXXX.apk目录是将apk发送到手机指定的目录adbpushtest.apk/sdcard/test/test.apk2.adbinstall电脑中apk的路径是安装电脑中的apk到手机adbinstall/Users/test/test.apk3.强

使用Ant自动签名、打包Android apk并且自动安装到手机 一、建立Ant打包Apk新建一个TestAnt项目创建App的签名密钥参考我的这篇github,欢迎Star|点击这里取到密钥后,在项目中创建一个keystore的文件夹,复制密

App开发日报 -- Android 5.X系列之如何阅读源码 App开发日报--@好东西传送门出品,过刊见

标签: 如何分析源码

本文链接地址:https://www.jiuchutong.com/biancheng/382258.html 转载请保留说明!

上一篇:Android快速开发--使用ORMLite操作数据库(android 快速开发工具)

下一篇:adb push、adb install 和强制安装

  • 个体工商户需要进项发票吗
  • 小规模企业所得税会计分录怎么做
  • 一般纳税人资格证明
  • 增值税发票进销项不一致
  • 简易计税方法使用范围
  • 缴纳税收凭证有原件吗
  • 总公司签合同发票由分公司开可以吗
  • 被客户扣钱怎么办
  • 专票未认证是什么意思
  • 生产车间的修理计入什么科目
  • 什么企业没有销售费用
  • 培训费没有发票怎么办
  • 加工费发票怎么做账务处理
  • 即征即退增值税政策
  • 国税登记流程
  • 公司的资本成本取决于投资人的必要报酬率
  • 本年固定资产投资额与不良贷款的关系
  • 增值税纳税申报表在哪里打印
  • 土地租赁期间政府征收
  • valorant!
  • mac怎么保存网页上的音频
  • 事业单位年终事迹材料
  • 基本户被冻结了一般户可以发工资吗
  • 总公司以固定资产出资入股,固定资产是不是新公司的
  • 收益性支出的项目有哪些
  • PHP:stream_context_get_params()的用法_Stream函数
  • php数组函数 菜鸟
  • 生产加工型企业安全隐患排查内容
  • 基金会债券收入吗
  • 无私有住房证明怎么开
  • 要点初见:Stable Diffusion NovelAI模型优质文字Tag汇总与实践【魔咒汇总】
  • php中实现文件上传需要用到哪几个函数
  • 技术服务增值税申报表怎么填
  • 文化事业建设费税收优惠2023
  • 税务机关代开的增值税发票要加盖发票专用章吗?
  • 劳务维修费怎么开票
  • 加计抵减会计分录其他收益
  • 不抵扣勾选有什么风险
  • linux系统中mysql数据库的导入和导出
  • 委托加工应税消费品收回后直接销售
  • 暂估成本跨年后收到票可以直接附在暂估凭证
  • 长期股权投资收益要交税吗
  • 不确认销售收入的原因
  • 实收资本账务处理流程
  • 医院药品进销差价规定
  • 车贷管理费合理吗
  • 单位经办人给员工发工资
  • 二级分支机构不具有主体生产经营职能?
  • 汇兑损益的账务处
  • mysql 5.6.26 winx64安装配置图文教程(一)
  • MSSQL转MYSQL,gb2312转utf-8无乱码解决方法
  • window10重装显卡驱动
  • xp系统怎样设置无线网络连接
  • linux ./执行
  • bd是什么文件
  • win10怎么预览
  • win7开始菜单在哪个文件夹
  • linux常用命令chmod
  • Win10更新后浏览器不能联网怎么办
  • 新版电脑装win7
  • cocos2dx4.0入门
  • exact form
  • 简单谈谈你的入党动机
  • Android 开源项目集合
  • shell脚本for循环 计算1到100的和
  • javascript编写
  • js class属性
  • 提高网页的效率的方法有
  • pygame实例
  • unity编辑工具软件介绍
  • angular.js
  • jquery数据绑定
  • javascript的对象
  • node express 路由
  • 在企业内部具有行使否决权的是
  • 土地使用税申报流程图
  • 广东国税局发票查询平台
  • 三证合一后还要做什么
  • 回迁房需要交契税吗
  • 残疾人个人所得税减免政策2023
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设