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

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

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

引言：最近许多人在博客中提到自己在面试时被问“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 中的 Lru 指的是“Least Recently Used-近期最少使用算法”。这就意味着，LruCache 应该是一个能够判断哪个缓存对象是近期最少使用的缓存类。解释到这里我相信大家都能明白为什么需要引入队列了。

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

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

从代码里我们可以知道：LruCache 不是其他类的子类，并且其中实际涉及到的只有一个 LinkedHashMap 对象和一堆 int 值。也就是说，LruCache 实现其核心逻辑的关键应该就是 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 到底能干些什么，毕竟从他的外在表现去分析内在逻辑会更轻松些，下面是一段简单的 Java 代码：

这是输出：

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

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

我们直接看 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 的核心 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开发日报--@好东西传送门出品,过刊见