目的

在 Android 開發(fā)中，我們需要避免程序占用過多的內存資源或者存儲空間，比如網絡加載圖片下載文件等，當緩存大小達到一定值的時候我們需要從緩存中釋放空間存放新的緩存，LruCache 就是常用的用于管理緩存的類。

LruCache 緩存算法

Lru: Least Recently Used
原理: 當緩存大小大于最大值時，優(yōu)先拋棄緩存中最近最少使用的緩存，直到當前緩存大小小于等于最大值。

LruCache LRU 實現(xiàn)

利用 LinkedHashMap 可以根據元素調用排序的特點，提供 get() put() remove() 等方法來操作緩存。

源碼解析

構造方法：

// LruCache.java
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);
}

構造方法的核心就是創(chuàng)建了一個初始容量為 0 ，默認 loadFactor = 0.75f，根據元素訪問排序的 LinkedHashMap.

// LruCache.java
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; // 當前緩存大小，不一定跟 map 中的鍵值對數相同
    private int maxSize; // 最大緩存大小

    private int putCount; // 標記 put() 被調用次數
    private int createCount; // 標記調用 create() 且返回不為 null 的次數
    private int evictionCount; // 標記 map 中被拋棄的值的數量
    private int hitCount; // 標記調用 get() 時存在值的次數
    private int missCount; // 標記調用 get() 時不存在值的次數
    
    ...

    public synchronized final int size() {
        return size;
    }

    public synchronized final int maxSize() {
        return maxSize;
    }

    public synchronized final int hitCount() {
        return hitCount;
    }

    public synchronized final int missCount() {
        return missCount;
    }

    public synchronized final int createCount() {
        return createCount;
    }

    public synchronized final int putCount() {
        return putCount;
    }

    public synchronized final int evictionCount() {
        return evictionCount;
    }
}

核心方法:

1.get()

// LruCache.java
public final V get(K key) {
    if (key == null) { // 非空判斷
        throw new NullPointerException("key == null");
    }

    V mapValue;
    synchronized (this) {
        // 從緩存 map 中獲取 mapValue
        mapValue = map.get(key);
        // 非空判斷
        if (mapValue != null) {
            // 不為空，累加 hitCount 并返回 mapValue
            hitCount++;
            return mapValue;
        }
        // mapValue 為空，累加 missCount
        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.
     *
     * 創(chuàng)建一個 value。這里需要消耗點時間，map 有可能在 create() 結束的時候
     * 發(fā)生變化。并發(fā)情況下，如果在執(zhí)行 create() 的時候有別的 value 添加到 map 中
     * 的時候，會保留別的 value 在 map 中并且丟棄 createdValue.
     */
    V createdValue = create(key);
    // 默認情況下返回 null
    if (createdValue == null) {
        return null;
    }

    // 同步鎖代碼塊
    synchronized (this) {
        // 累加 createCount
        createCount++;
        // 把 createdValue 放進 map
        // LinkedHashMap.put() 返回的是該 key 原本的 value (原本不存在時返回null)
        // 無論 value 是否為 null createdValue 依然會添加到 map 中
        mapValue = map.put(key, createdValue);
        
        if (mapValue != null) {
            // 不為空則有別的 value 已經添加在 map 中，且重新把這個 value 放進 map 中
            // There was a conflict so undo that last put
            map.put(key, mapValue);
        } else {
            // 添加成功后根據 createdValue 的大小添加到 size
            size += safeSizeOf(key, createdValue);
        }
    }

    if (mapValue != null) { // 已經存在別的 value
        // 回調 entryRemoved() 
        entryRemoved(false, key, createdValue, mapValue);
        // 返回原本存在的 value
        return mapValue;
    } else { // 添加成功
        // 縮短緩存大小直到小于最大緩存值
        trimToSize(maxSize);
        // 返回創(chuàng)建的 createdValue
        return createdValue;
    }
}

protected V create(K key) {
    return null;
}

private int safeSizeOf(K key, V value) {
    int result = sizeOf(key, value);
    if (result < 0) {
        throw new IllegalStateException("Negative size: " + key + "=" + value);
    }
    return result;
}

protected int sizeOf(K key, V value) {
    return 1;
}

protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {}

直接根據 key 從緩存 map 中直接獲取 value，并進行非空判斷：

• 非null : 直接返回 value，結束 get() 。
• null : 調用 create() 創(chuàng)建一個值若為 null 直接返回 null 結束 get()，不為 null 就調用 map.put() 到緩存中，由于存在并發(fā)的情況，所以有可能在 create() 執(zhí)行過程中已經有別的 value 對應同一個 key 添加到 map 中的情況，所以根據判斷 put() 返回值是否為空可以判斷 map 中是否已經存在 key 對應的值 :
  • null: 創(chuàng)建的 createValue 添加成功，調用 safeSizeOf() 判斷 createValue 的大小并累加到 size上，然后調用 trimTosize() 使緩存大小小于maxSize，最后返回 createValue。
  • 非null: map 中已存在別的值 mapValue ，重新把 mapValue 放進 map 中，然后調用回調方法 entryRemoved()，最后返回 mapValue。

在 get() 中有幾個 LruCache 提供給我們根據業(yè)務需求重寫的方法:

1.create()

默認直接返回 null，根據業(yè)務需求我們可以在發(fā)現(xiàn) key 對應的值不存在的時候創(chuàng)建一個值放進緩存中。

2.sizeOf()

默認值為1，根據需求我們可以設置每個值的緩存大小，比如圖片我們可以返回圖片占用的內存大小。

3.entryRemoved()

默認空實現(xiàn)，每當有 value 從 map 中被移除或者被拋棄的時候會調用。

2.put()

// LruCache.java
public final V put(K key, V value) {
    if (key == null || value == null) { // 非空判斷
        throw new NullPointerException("key == null || value == null");
    }

    V previous;
    synchronized (this) { // 同步鎖代碼塊
        // 累加 put() 調用次數
        putCount++;
        // 累加緩存大小
        size += safeSizeOf(key, value);
        // 添加到 map 中
        previous = map.put(key, value);
        // 如果該 key 對應的 value 之前已存在，
        // 當前緩存大小就需要減掉之前的 value 大小 
        if (previous != null) {
            size -= safeSizeOf(key, previous);
        }
    }

    // 如果該 key 對應的 value 之前已存在，
    // 調用回調方法 entryRemoved()
    if (previous != null) {
        entryRemoved(false, key, previous, value);
    }
    // 最后調整緩存大小
    trimToSize(maxSize);
    // 返回之前的 value 值，若 value 之前不存在則為 null
    return previous;
}

放進緩存，并返回調用 put() 之前緩存中該 key 對應的 value。

3.trimToSize()

調整緩存大小直到小于設置的最大值為止。

// LruCache.java
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!");
            }

            if (size <= maxSize) { // 若當前緩存大小小于最大值，跳出循環(huán)方法結束
                break;
            }

            // 獲取 map 最后一個鍵值對，即按照調用順序末尾的鍵值對
            Map.Entry<K, V> toEvict = map.eldest();
            if (toEvict == null) { // 若末尾值為 null，跳出循環(huán)方法結束
                break;
            }
           // 獲取 key
            key = toEvict.getKey();
            // 獲取 value
            value = toEvict.getValue();
            // 從 map 中移除
            map.remove(key);
            // 從緩存大小中減去該值的大小
            size -= safeSizeOf(key, value);
            // 累加 evictionCount
            evictionCount++;
        }
        // 調用回調方法 entryRemoved
        entryRemoved(true, key, value, null);
    }
}

每次循環(huán)都移除調用順序末尾的緩存，直到當前緩存大小小于設置的最大值。

4.remove()

根據 Key 從 map 中移除緩存。

// LruCache.java
public final V remove(K key) {
    if (key == null) { // 非空判斷
        throw new NullPointerException("key == null");
    }

    V previous;
    synchronized (this) {
        // 從 map 中移除，并獲取移除之前的 value
        previous = map.remove(key);
        if (previous != null) { 
            // 若移除之前值不為 null，當前緩存大小需要減去 previous 大小
            size -= safeSizeOf(key, previous);
        }
    }

    if (previous != null) {
        // 調用回調方法 entryRemoved
        entryRemoved(false, key, previous, null);
    }
    // 返回移除前的值，若移除前值不存在則返回 null
    return previous;
}

其他方法:

1.resize()

重置 LruCache 的最大緩存大小。

public void resize(int maxSize) {
    if (maxSize <= 0) {
        throw new IllegalArgumentException("maxSize <= 0");
    }

    synchronized (this) {
        this.maxSize = maxSize;
    }
    // 重新賦值 maxSize 后要調整令 size <= maxSize
    trimToSize(maxSize);
}

2.snapshot()

獲取一個復制當前緩存 map 的 LinkedHashMap。

public synchronized final Map<K, V> snapshot() {
    return new LinkedHashMap<K, V>(map);
}

3.evictAll()

清除所有緩存。

public final void evictAll() {
    // 直接調用 trimToSize(-1) 則最后緩存大小會變成 0
    trimToSize(-1); // -1 will evict 0-sized elements
}