前言
在Android 2.2以上的sdk中提供了缓存类LruCache。LruCache用于内存缓存，常用的应用场景有很多，比如我们的图片加载库的内存缓存就可以利用LruCache来实现，今天我们一起来学习一下LruCache的源码。
LruCache介绍
LruCache 顾名思义就是使用LRU缓存策略的缓存，那么LRU是什么呢? 最近最少使用到的（least recently used），就是当超出缓存容量的时候，就优先淘汰链表中最近最少使用的那个数据。
讲到LruCache，其实最关键的还是LinkedHashMap。LruCache的源码本身很少，而实现了LRU的功能都是靠LinkedHashMap。所以我们先来一起学习一下LinkedHashMap。
LinkedHashMap
LinkedHashMap是hashmap和链表的结合体，通过链表来记录元素的顺序和链接关系，通过HashMap来存储数据,它可以控制元素的被遍历时候输出的顺序（按照最近访问顺序来排序，还是按插入顺序）。元素被保存在一个双向链表中，默认的遍历顺序是按插入顺序来被遍历的。通过构造函数的accessOrder来控制是否按照访问顺序来遍历。待会我们一起来看看它的构造函数。当以访问顺序来排序的时候，LinkedHashMap总是将最近访问的元素放在队列的尾部，所以第一个元素就是最不经常访问的元素，从而当容量满了的时候就会将第一个元素移除，凭借，get，put，以及putAll都会影响表结构，get的时候需要将，当前被访问的这个对象移动到表的最后面。
首先 LinkHashMap是继承自HashMap的一个类，对于HashMap来说它只是多定义了两个变量如下，当然也是通过这两个变量以及重写HashMap的部分方法来实现，LRU的功能。
/**
循环链表中一个虚拟的入口，第一个元素是header的next，
最后一个元素是header的尾部
如果map是空的话，那么header.nxt == header && header.prv == header.
nxt，prv，表示一个元素的前后元素，相信学过的链表的道友们都会知道这个的吧
*/
transient LinkedEntry<K, V> header;
/**
* True if access ordered, false if insertion ordered.
这个是用于控制，外部访问链表的时候，是按什么顺序访问的 ，
，true就是按照最近访问来排列元素，从而被遍历，否则就是按照插入顺序来被遍历，当然存储的时候也会根据这个变量来做特殊的处理，
true的时候那么就会在访问和删除的时候修改链表的元素的before和next的指针。
*/
private final boolean accessOrder;
首先一起来看看LinkedHashMap的关键构造方法之一：
/**
* @param initialCapacity 定义LinkedHashMap的初始容量
* the initial capacity of this hash map.
* @param loadFactor 定义加载因子，用于当容量不够用的时候，扩展容量时，是用初始容量*加载因子等于之后扩展的容量。
* the initial load factor.
* @param accessOrder
* {@code true} if the ordering should be done based on the last
* access (from least-recently accessed to most-recently
* accessed), and {@code false} if the ordering should be the
* order in which the entries were inserted.
* @throws IllegalArgumentException
* when the capacity is less than zero or the load factor is
* less or equal to zero.
*/
public LinkedHashMap(
int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
init();
this.accessOrder = accessOrder;
}
我们可以看到LinkedHashMap的构造方法就是调用了父类构造方法，然后给accessOrder赋值，其中调用了init
()，那接下来我们一起来看看init方法，init方法很简单就是给header赋值了，指向了一个LinkedEntry对象。
@Override void init() {
header = new LinkedEntry<K, V>();
}
LinkedEntry是LinkedHashMap和HashMap的重大区别之一。HashMapEntry的结构如下：
static class HashMapEntry<K, V> implements Entry<K, V> {
final K key; //键
V value; //值
final int hash; //该元素对应的hash值
HashMapEntry<K, V> next; //table数组中下一个元素
而LinkedEntry则多了两个对象，如下：
LinkedEntry<K, V> nxt;
LinkedEntry<K, V> prv;
不知道道友们有没有学过c，c里面常用的概念指针和我们Java所指的引用，我觉得概念差不多，都是指向某个对象，这里的nxt，和prv就是指向了相对当前元素来说的前一个元素和后一个元素，从而存储了数据之前的关联关系。
从而实现一个链表结构，通过一个虚拟的头部来链接一个表的头部和尾部从而实现循环链表。
看完了初始化linkedHaspMap，接下来我们就通过他的操作来看看它的其他关键的方法，数据结构主要的操作就是增删查改咯，接下来我就带着各位道友一起来看看，这四个方法首先看增加:
@Override void addNewEntry(K key, V value, int hash, int index) {
LinkedEntry<K, V> header = this.header;
// Remove eldest entry if instructed to do so.
LinkedEntry<K, V> eldest = header.nxt;
if (eldest != header && removeEldestEntry(eldest)) {
remove(eldest.key);
}
// Create new entry, link it on to list, and put it into table
LinkedEntry<K, V> oldTail = header.prv;
LinkedEntry<K, V> newTail = new LinkedEntry<K,V>(
key, value, hash, table[index], header, oldTail);
table[index] = oldTail.nxt = header.prv = newTail;
}
从addNewEntry代码可以看到 ，首先保存了当前链表的头部，然后判断是否需要移除最不常访问的entry，然后将它移除，因为LinkedHashMap是始终将最不常访问的放在头部，所以header.nxt便是就老的entry。 然后创建一个新的entry，记录下当前最近被访问的元素即尾部元素，由于是循环链表所以头部的prv，便是当前最近被访问的元素，然后新插入的元素应该位于尾部，我们假设插入的元素为a， 那么a的prv，便是刚刚记录下来的最近被访问的元素，而nxt这是header元素，从而将entry的nxt，pre调整好之后，插入功能这也就完成了。而这个方法呢是在HashMap的put方法中调用的，LinkedHashMap重写了HashMap的addNewEntry方法。从而完成链表操作。
接下来我们来看看，查询操作get，LinkedHashMap重写了HashMap的get方法，具体代码如下:
@Override public V get(Object key) {
/*
* This method is overridden to eliminate the need for a polymorphic
* invocation in superclass at the expense of code duplication.
*/
if (key == null) {
HashMapEntry<K, V> e = entryForNullKey;
if (e == null)
return null;
if (accessOrder)
makeTail((LinkedEntry<K, V>) e);
return e.value;
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
e != null; e = e.next) {
K eKey = e.key;
if (eKey == key || (e.hash == hash && key.equals(eKey))) {
if (accessOrder)
makeTail((LinkedEntry<K, V>) e);
return e.value;
}
}
return null;
}
从上面可以看出来，key是null的时候，则使用entryForNullKey，来表示当前被查询到的entry，当然如果存在key，则通过匹配key的引用，或者key的hash相等并且key的值相等来找到对应的entry，找到entry之后他们都做了共同的操作的那就是makeTail，那么makeTail是什么作用呢，接下来我们一起看一下。
/**
当accessOrder是true的时候，重新链接传入的entry到链表的尾部。当put 修改entry和，get的时候都会调用这个方法，
* Relinks the given entry to the tail of the list. Under access ordering,
* this method is invoked whenever the value of a pre-existing entry is
* read by Map.get or modified by Map.put.
*/
private void makeTail(LinkedEntry<K, V> e) {
// Unlink e
e.prv.nxt = e.nxt;
e.nxt.prv = e.prv;
// Relink e as tail
LinkedEntry<K, V> header = this.header;
LinkedEntry<K, V> oldTail = header.prv;
e.nxt = header;
e.prv = oldTail;
oldTail.nxt = header.prv = e;
modCount++;
}
从代码和注释也可以知道，这个方法就是首先将当前被访问的entry从链表中移除，然后将当前entry添加到队列的尾部。这里需要注意的是，频繁使用查改，并不会消耗大量的内存和资源，因为其实引用的常量改变而已，没有造成new新的资源等。
这就是整个get的调用流程。
接下来一起看一下改的逻辑，其实改的逻辑也很简单，首先找到和key相对应的entry，然后修改值，并且调用makeTail方法。
首先一起来看看HashMap的put方法，因为LinkedHashMap的put方法用的就是父类的put方法，只不过是重写了preModify和addNewEntry从而实现了链表的功能呢。
@Override public V put(K key, V value) {
if (key == null) {
return putValueForNullKey(value);
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
//查找是否已经存在key的entry，如果存在着更新，而不是添加。
for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
if (e.hash == hash && key.equals(e.key)) {
preModify(e);
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
//如果没找到则添加一个新的entry
// No entry for (non-null) key is present; create one
modCount++;
if (size++ > threshold) {
tab = doubleCapacity();
index = hash & (tab.length - 1);
}
addNewEntry(key, value, hash, index);
return null;
}
从上面的代码可以看到，当更改一个元素的时候，调用了preModify方法，这个方法HashMap没有实现，而是由子类实现，linkedHashMap的实现如下：
@Override void preModify(HashMapEntry<K, V> e) {
if (accessOrder) {
makeTail((LinkedEntry<K, V>) e);
}
}
可以看到同样是调用了makeTail去使entry位于尾部。
这样看下来，其实最关键的就是将最近访问的元素添加到尾部，如果已经存在，则现将存在的那个entry从列表中删除然后再添加到尾部。
删除也是一样的道理，linkedHashMap通过重写父类的postRemove方法来实现将链表中的entry移除，具体看父类的HashMap和linkedHashMap的代码如下：
/**
* Removes the mapping with the specified key from this map.
*
* @param key
* the key of the mapping to remove.
* @return the value of the removed mapping or {@code null} if no mapping
* for the specified key was found.
*/
@Override public V remove(Object key) {
if (key == null) {
return removeNullKey();
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
for (HashMapEntry<K, V> e = tab[index], prev = null;
e != null; prev = e, e = e.next) {
if (e.hash == hash && key.equals(e.key)) {
if (prev == null) {
tab[index] = e.next;
} else {
prev.next = e.next;
}
modCount++;
size--;
postRemove(e);
return e.value;
}
}
return null;
}
LinkedHashMap:
@Override void postRemove(HashMapEntry<K, V> e) {
LinkedEntry<K, V> le = (LinkedEntry<K, V>) e;
le.prv.nxt = le.nxt;
le.nxt.prv = le.prv;
le.nxt = le.prv = null; // Help the GC (for performance)
}
从上面可以看到，同样的是先找到对应的entry，然后将调整当前entry的前一个元素的next。然后调用linkedHashMap重写的postRemove方法，然后将当前entry从链表中移除，并且将当前元素的nxt和prv置为null，从而加速GC的回收。
自己绘制了个LinkedHashMap的图，道友们凑合看看。
image
到这里LinkedHashMap就讲解完了，接下来就学习一下LruCache的源码。
首先看到构造方法：
/**
* @param maxSize for caches that do not override {@link #sizeOf}, this is
* the maximum number of entries in the cache. For all other caches,
* this is the maximum sum of the sizes of the entries in this cache.
*/
public LruCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
this.maxSize = maxSize;
this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}
通过传入一个maxSize来设置LruCache的最大值，并且穿件了一个LinkedHashMap的成员变量。接下来呢我们一起来看一下，关键的增删查改功能。
- put 插入更新数据
public final V put(K key, V value) {
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}
V previous; //查找是否已经存在key对应的元素
synchronized (this) {
putCount++;
//计算entry的大小
size += safeSizeOf(key, value);
previous = map.put(key, value);
if (previous != null) {
//如果之前存在，这先减去之前那个entry所占用的内存大小
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {
//如果之前存在则调用entryRemoved回调子类重写的此方法，做一些处理
entryRemoved(false, key, previous, value);
}
//根据最大的容量，计算是否需要淘汰掉最不常使用的entry
trimToSize(maxSize);
return previous;
}
上面的代码都有标注，可以看到对于淘汰策略关键的是trimeToSize这个方法我们一起来看看：
public void trimToSize(int maxSize) {
while (true) {
K key;
V value;
synchronized (this) {
if (size < 0 || (map.isEmpty() && size != 0)) {
throw new IllegalStateException(getClass().getName()
+ ".sizeOf() is reporting inconsistent results!");
}
//如果当前已经使用的size小于最大容量，那就不做处理直接退出。
if (size <= maxSize || map.isEmpty()) {
break;
}
//当超出容量的时候，通过map的iterator，获取第一个数据将其删除，一直循环，知道size小于maxsize为止。
Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
key = toEvict.getKey();
value = toEvict.getValue();
map.remove(key);
size -= safeSizeOf(key, value);
evictionCount++;
}
entryRemoved(true, key, value, null);
}
}
从上面可以看到，trimSize就是LruCache控制内存大小，并且淘汰掉LRU策略中最不常使用的元素的地方。
- 查询
public final V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
//根据key来查询符合条件的etnry
synchronized (this) {
mapValue = map.get(key);
if (mapValue != null) {
hitCount++;
return mapValue;
}
missCount++;
}
/*
* Attempt to create a value. This may take a long time, and the map
* may be different when create() returns. If a conflicting value was
* added to the map while create() was working, we leave that value in
* the map and release the created value.
*/
V createdValue = create(key);
if (createdValue == null) {
return null;
}
synchronized (this) {
createCount++;
//mapValue返回的是已经存在相同key的entry
mapValue = map.put(key, createdValue);
if (mapValue != null) {
// There was a conflict so undo that last put
map.put(key, mapValue);
} else {
size += safeSizeOf(key, createdValue);
}
}
if (mapValue != null) {
entryRemoved(false, key, createdValue, mapValue);
return mapValue;
} else {
trimToSize(maxSize);
return createdValue;
}
}
从上面可以看到，当根据key查询不到对应的值的时候，LruCache就会自己创建一个值，因为创建值的同时可能会有其他线程对这个key进行插入作用，所以在创建完之后如果之前有这个key被插入，那么就撤销新创建的值，然后保留之前插入的那个值。如果没有就返回创建的值。LruCache默认是null的，所以如果子类没有复写这个方法的话，那么是不会在查询不到的时候创建默认的值的。一般都不会重写这个方法的。
- 删除
public final V remove(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V previous;
synchronized (this) {
previous = map.remove(key);
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {
entryRemoved(false, key, previous, null);
}
return previous;
}
其实删除的方法很简单就调用LinkedHashMap的删除，然后减少内存的占用大小。
除了这些关键方法之外，LruCache也提供了public的方法可以访问，查询命中率以及未命中率等。
至此呢，LruCache和LinkHashMap就讲完了，总结一下，LruCache是限定大小的内部缓存类，利用LinkHashMap实现LRU的缓存策略，而LruCache主要负责缓存大小的控制以及淘汰元素控制，而LinkedHashMap通过链表和HashMap结合负责LRU的实现。
为什么要学习LruCache方便之后讲解图片的缓存策略理解原理，当然其他的缓存需求也可以用这个。今天就学习到这里。 有错误欢迎指出 _。
网友评论