Android LruCache 源碼分析

0. 前言

學過作業系統這門課的朋友都還記得

LRU

這個算法吧，中文名叫”最近最久未使用”，它是用在頁面置換政策中的一種很巧妙的淘汰算法，而在

Android

中，也有一個緩存淘汰機制用到了它，叫做

LruCache

，它也可以說是一個精妙的設計吧，這篇博文中，筆者将帶領大家剖析它源碼中的精妙之處…

1. 初始化

LruCache

類源碼位于

android.util.LruCache

包下，大家也可以同步閱讀。第一件事，便是看其執行個體化過程，隻有一個帶參數的構造函數，參數的意思是緩存最大支援的記憶體容量，注意哦，不是數量，是占用空間的容量:

public LruCache(int maxSize) {
    if (maxSize <= ) {
        throw new IllegalArgumentException("maxSize <= 0");
    }
    // 指派
    this.maxSize = maxSize;
    // 建立 HashMap
    // 參數：初始容量為0；加載因子為0.75；以最近最久未使用排序
    this.map = new LinkedHashMap<K, V>(, f, 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

算法，可以說非常值得一讀！