0. 前言

学过操作系统这门课的朋友都还记得 LRU 这个算法吧，中文名叫”最近最久未使用”，它是用在页面置换策略中的一种很巧妙的淘汰算法，而在 Android 中，也有一个缓存淘汰机制用到了它，叫做 LruCache，它也可以说是一个精妙的设计吧，这篇博文中，笔者将带领大家剖析它源码中的精妙之处…

1. 初始化

LruCache 类源码位于 android.util.LruCache 包下，大家也可以同步阅读。第一件事，便是看其实例化过程，只有一个带参数的构造函数，参数的意思是缓存最大支持的内存容量，注意哦，不是数量，是占用空间的容量:

public LruCache(int maxSize) {
    if (maxSize <= 0) {
        throw new IllegalArgumentException("maxSize <= 0");
    }
    // 赋值
    this.maxSize = maxSize;
    // 创建 HashMap
    // 参数：初始容量为0；加载因子为0.75；以最近最久未使用排序
    this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}

它将最大容量赋给了成员变量，还创建了一个 LinkedHashMap，它是一个循环链表，前面两个参数不要紧，关键在最后一个参数，最后一个参数含义是”是否以最近访问的顺序排序”，也就是说，如果为 true，那么 HashMap 的链表将会以最近访问的元素在尾部，很久没访问的元素在头部的顺序来排序，在 LinkedHashMap 的源码中可以证实这一说法:

// 调用此函数说明产生一次访问记录
public V get(Object key) {
    ...
    // 遍历链表
    for (...; e != null; e = e.next) {
        K eKey = e.key;
        // 如果找到值
        if (eKey == key || ...) {
            if (accessOrder)
                // 将结点e移至循环链表尾部
                makeTail((LinkedEntry<K, V>) e);
            return e.value;
        }
    }
    return null;
}

private void makeTail(LinkedEntry<K, V> e) {
    e.prv.nxt = e.nxt;
    e.nxt.prv = e.prv;
    // 将 e 去除
    // --------------------
    // |                  ↓
    // pre      e        nxt
    //  ↑                 |
    //  -------------------

    LinkedEntry<K, V> header = this.header;
    LinkedEntry<K, V> oldTail = header.prv;
    e.nxt = header;
    e.prv = oldTail;
    oldTail.nxt = header.prv = e;
    // 将 e 加在循环链表尾部: 
    // Tail（header的前面一个元素） 和 Header 中间
    // -------------- --------------
    // |            ↓ ↓            |
    // tail          e           header
    // ↑            | |            ↑
    // -------------- --------------
    modCount++;
}

并且，通过 LinkedHashMap#eldest() 方法可以返回最老的结点:

public Entry<K, V> eldest() {
    // 头第一个结点便是最老的节点
    LinkedEntry<K, V> eldest = header.nxt;
    // 如果 header 的下一个结点就是 header 
    // 说明该循环链表为空
    return eldest != header ? eldest : null;
}

2. 添加

初始化步骤为我们提供了一个可供存储缓存的循环链表，还提供好了 LRU 排序。接下来看看如何添加一个缓存记录的:

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++; // 放入的次数 调用 remove() 不会减少
        size += safeSizeOf(key, value); // 占用的大小 默认为1 供子类重写 sizeOf()
        previous = map.put(key, value); // 放入 LinkedHashMap 返回值表示先前是否存在有记录
        if (previous != null) { // 如果之前缓存中存在有记录，那么并没有放入
            size -= safeSizeOf(key, previous);  // 所以大小要减少
        }
    }
    if (previous != null) {
        entryRemoved(false, key, previous, value);  // 调用供子类覆写的方法
    }
    trimToSize(maxSize);    // 重建大小 淘汰旧的元素
    return previous;
}

不少的代码，其实就是两步，先将缓存结点添加进 LinkedHashMap，然后调用 trimToSize(maxSize) 检查大小并淘汰。接下来看看是如何淘汰就节点的:

public void trimToSize(int maxSize) {
    while (true) {
        K key;
        V value;
        synchronized (this) {
            ...
            Map.Entry<K, V> toEvict = map.eldest(); // 返回最老的元素
            if (toEvict == null) {
                break;
            }
            key = toEvict.getKey();
            value = toEvict.getValue();
            map.remove(key); // 移除该元素
            size -= safeSizeOf(key, value); // 减小大小
            evictionCount++; // 移除的次数
        }
        // 子类重写方法以实现具体的移除策略
        entryRemoved(true, key, value, null);
    }
}

上面两段代码都提到了 entryRemoved() 方法，这其实是一个供子类扩展功能的方法，它可以被子类覆写，比如可以再增加一级磁盘缓存，那么磁盘上的添加和移除缓存方法就需要子类来重写了:

// 子类重写方法 以实现具体的移除策略
// 参数一 表示 是否是被淘汰出去的
// 参数三 表示 移除了一个旧的值 用新的值来替换
protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {}

// 子类重写方法 以实现具体的添加策略
// 参数一 表示 键值对的键
protected V create(K key) {
    return null;
}

3. 取出

添加好了缓存就可以取出来用了，接下来看是如何取出来的:

public final V get(K key) {
    ...
    V mapValue;
    synchronized (this) {
        mapValue = map.get(key);
        if (mapValue != null) {
            hitCount++; // 用到的元素数目 越大相当于利用率越高
            return mapValue; // 找到了就直接返回
        }
        missCount++;    // 没有找到元素 丢失的缓存数目
    }
    // 如果缓存容器中没有值 就调用 create() 方法再创建
    V createdValue = create(key);
    if (createdValue == null) {
        return null;    // 创建不成功 返回 null
    }
    synchronized (this) {
        createCount++; // 创建次数
        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;
    }
}

其实完成的内容也很简单，就是从 LinkedHashMap 中取出，如果有就返回，如果没有就调用子类的 create(key) 方法，最后要记得验证是否需要淘汰最近最久未使用的元素。

总结

LruCache 的源码还是很简单的，但它很巧妙地结合 LinkedHashMap 实现了 LRU 算法，可以说非常值得一读！