[移动开发]Android源码分析：LruCache 缓存机制实现原理，【架构师必备】

 map.get(1);     //访问1
map.get(2);     //访问2

for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ":" + entry.getValue());
}

}

输出结果如下：

0:0
3:3
4:4
5:5
6:6
1:1
2:2

即最近访问的对象会被放到队尾，然后最后输出，那么这就正好满足的LRU缓存算法的思想。可见**LruCache**巧妙实现，就是利用了**LinkedHashMap**的这种数据结构。

下面我们在**LruCache**源码中具体看看，怎么应用**LinkedHashMap**来实现缓存的添加，获得和删除的。

#### LruCache源码分析

我们先看看成员变量有哪些：

public class LruCache<K, V> {
private final LinkedHashMap<K, V> map;

/** Size of this cache in units. Not necessarily the number of elements. */
private int size;   //当前cache的大小
private int maxSize;     //cache最大大小

private int putCount;       //put的次数
private int createCount;    //create的次数
private int evictionCount;  //驱逐剔除的次数
private int hitCount;       //命中的次数
private int missCount;      //未命中次数

//...省略...

}

构造函数如下，可以看到**LruCache**正是用了**LinkedHashMap**的**accessOrder=true**构造参数实现LRU访问顺序：

public LruCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException(“maxSize <= 0”);
}
this.maxSize = maxSize;
//将LinkedHashMap的accessOrder设置为true来实现LRU顺序
this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}

##### put方法

public final V put(K key, V value) {
//不可为空，否则抛出异常
if (key == null || value == null) {
throw new NullPointerException(“key == null || value == null”);
}

V previous; //旧值
synchronized (this) {
    putCount++;     //插入次数加1
    size += safeSizeOf(key, value);     //更新缓存的大小
    previous = map.put(key, value);
    //如果已有缓存对象，则缓存大小的值需要剔除这个旧的大小
    if (previous != null) {
        size -= safeSizeOf(key, previous);
    }
}

//entryRemoved()是个空方法，可以自行实现
if (previous != null) {
    entryRemoved(false, key, previous, value);
}

//调整缓存大小(关键方法)
trimToSize(maxSize);
return previous;

}

可以看到\*\*put()**方法并没有什么难点，重要的就是在添加过缓存对象后，调用**trimToSize()\*\*方法，来判断缓存是否已满，如果满了就要删除近期最少使用的算法。

##### trimToSize方法

public void trimToSize(int maxSize) {
while (true) {
K key;
V value;
synchronized (this) {
//如果map为空并且缓存size不等于0或者缓存size小于0，抛出异常
if (size < 0 || (map.isEmpty() && size != 0)) {
throw new IllegalStateException(getClass().getName()
+ “.sizeOf() is reporting inconsistent results!”);
}

        //如果缓存大小size小于最大缓存，或者map为空，则不需要再删除缓存对象，跳出循环
        if (size <= maxSize || map.isEmpty()) {
            break;
        }

        //迭代器获取第一个对象，即队头的元素，近期最少访问的元素
        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);
}

}

**trimToSize()**方法不断地删除**LinkedHashMap**中队头的元素，即近期最少访问的，直到缓存大小小于最大值。

当调用**LruCache**的**get()**方法获取集合中的缓存对象时，就代表访问了一次该元素，将会更新队列，保持整个队列是按照访问顺序排序。这个更新过程就是在**LinkedHashMap**中的\*\*get()\*\*方法中完成的。

我们先看LruCache的get()方法。

##### get方法

//LruCache的get()方法
public final V get(K key) {
if (key == null) {
throw new NullPointerException(“key == null”);
}

V mapValue;
synchronized (this) {
    //获取对应的缓存对象
    //LinkedHashMap的get()方法会实现将访问的元素更新到队列尾部的功能
    mapValue = map.get(key);

    //mapValue不为空表示命中，hitCount+1并返回mapValue对象
    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.
 * 如果未命中，则试图创建一个对象，这里create方法默认返回null,并没有实现创建对象的方法。
 * 如果需要事项创建对象的方法可以重写create方法。因为图片缓存时内存缓存没有命中会去
 * 文件缓存中去取或者从网络下载，所以并不需要创建，下面的就不用看了。
 */

V createdValue = create(key);
if (createdValue == null) {
    return null;
}

//假如创建了新的对象，则继续往下执行
synchronized (this) {
    createCount++;
    //将createdValue加入到map中，并且将原来键为key的对象保存到mapValue
    mapValue = map.put(key, createdValue);

    if (mapValue != null) {
        // There was a conflict so undo that last put
        //如果mapValue不为空，则撤销上一步的put操作。
        map.put(key, mapValue);
    } else {
        //加入新创建的对象之后需要重新计算size大小
        size += safeSizeOf(key, createdValue);
    }
}

if (mapValue != null) {
    entryRemoved(false, key, createdValue, mapValue);
    return mapValue;
} else {
    //每次新加入对象都需要调用trimToSize方法看是否需要回收
    trimToSize(maxSize);
    return createdValue;
}

}

其中**LinkedHashMap**的\*\*get()\*\*方法如下：

//LinkedHashMap中的get方法
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
//实现排序的关键方法
if (accessOrder)
afterNodeAccess(e);
return e.value;
}

调用的\*\*afterNodeAccess()\*\*方法将该元素移到队尾，保证最后才删除，如下：

void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
//当前节点p移动到尾部之后，尾部指针指向当前节点
tail = p;
++modCount;
}

CodeChina开源项目：《Android学习笔记总结+移动架构视频+大厂面试真题+项目实战源码》
tail = p;
++modCount;
}
[外链图片转存中…(img-CrMzAZR6-1630507997475)]

[外链图片转存中…(img-VP3Jfc1v-1630507997477)]

CodeChina开源项目：《Android学习笔记总结+移动架构视频+大厂面试真题+项目实战源码》