LruCache 分析

LruCache 是 Android 的一個內(nèi)部類，提供了基于內(nèi)存實現(xiàn)的緩存

用法

     //獲取系統(tǒng)分配給每個應(yīng)用程序的最大內(nèi)存炬藤，每個應(yīng)用系統(tǒng)分配32M  
    int maxMemory = (int) Runtime.getRuntime().maxMemory();    
    int mCacheSize = maxMemory / 8;  
    //給LruCache分配1/8 4M  
    mMemoryCache = new LruCache<String, Bitmap>(mCacheSize){  

        //必須重寫此方法啤誊，來測量Bitmap的大小  
        @Override  
        protected int sizeOf(String key, Bitmap value) {  
            return value.getRowBytes() * value.getHeight();  
        }  
          
    };  

源碼

LRUCache 的源碼不是很長，我們從上到下逐個分析涛菠，先看官方對這個類的注釋（注釋往往很有用）

注釋

/**
 * BEGIN LAYOUTLIB CHANGE
 * This is a custom version that doesn't use the non standard LinkedHashMap#eldest.
 * END LAYOUTLIB CHANGE
 *
 * A cache that holds strong references to a limited number of values. Each time
 * a value is accessed, it is moved to the head of a queue. When a value is
 * added to a full cache, the value at the end of that queue is evicted and may
 * become eligible for garbage collection.
 *
 * <p>If your cached values hold resources that need to be explicitly released,
 * override {@link #entryRemoved}.
 *
 * <p>If a cache miss should be computed on demand for the corresponding keys,
 * override {@link #create}. This simplifies the calling code, allowing it to
 * assume a value will always be returned, even when there's a cache miss.
 *
 * <p>By default, the cache size is measured in the number of entries. Override
 * {@link #sizeOf} to size the cache in different units. For example, this cache
 * is limited to 4MiB of bitmaps:
 * <pre>   {@code
 *   int cacheSize = 4 * 1024 * 1024; // 4MiB
 *   LruCache<String, Bitmap> bitmapCache = new LruCache<String, Bitmap>(cacheSize) {
 *       protected int sizeOf(String key, Bitmap value) {
 *           return value.getByteCount();
 *       }
 *   }}</pre>
 *
 * <p>This class is thread-safe. Perform multiple cache operations atomically by
 * synchronizing on the cache: <pre>   {@code
 *   synchronized (cache) {
 *     if (cache.get(key) == null) {
 *         cache.put(key, value);
 *     }
 *   }}</pre>
 *
 * <p>This class does not allow null to be used as a key or value. A return
 * value of null from {@link #get}, {@link #put} or {@link #remove} is
 * unambiguous: the key was not in the cache.
 *
 * <p>This class appeared in Android 3.1 (Honeycomb MR1); it's available as part
 * of <a s
 * Support Package</a> for earlier releases.
 */

注釋比較長屹篓，不過提供了幾個關(guān)鍵信息

• 說明了 LRU 的工作原理，最近使用的會放進(jìn)隊列的頭部匙奴，最久未使用的放進(jìn)隊列的尾部堆巧，會首先刪除隊尾元素
• 如果你 cache 的某個值需要明確釋放，重寫 entryRemoved 方法
• 如果 key 相對應(yīng)的 item 丟掉泼菌，重寫create()谍肤，這簡化了調(diào)用代碼，即使丟失了也總會返回哗伯。
• 默認(rèn)的荒揣，我們需要重寫 sizeOf 方法
• 該類是線程安全的
• 該類不允許空值和空 key
• 該類出現(xiàn)在 Android 3.1系統(tǒng)及其以后，但是會向下兼容

下面看其定義的變量

變量

 private final LinkedHashMap<K, V> map;// 以 LinkedHashMap 進(jìn)行存儲

/** Size of this cache in units. Not necessarily the number of elements. */
private int size;// 當(dāng)前大小
private int maxSize;// 最大容量

private int putCount;// put次數(shù)
private int createCount;// 創(chuàng)建次數(shù)
private int evictionCount;// 回收次數(shù)
private int hitCount;// 命中次數(shù)
private int missCount;// 未命中次數(shù)

再看構(gòu)造方法

構(gòu)造方法

/**
 * @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) {// 必須大于 0 焊刹，看上面的用發(fā)就知道了
        throw new IllegalArgumentException("maxSize <= 0");
    }
    this.maxSize = maxSize;
    this.map = new LinkedHashMap<K, V>(0, 0.75f, true);// 將LinkedHashMap的accessOrder 設(shè)置為 true 來實現(xiàn) LRU
}

構(gòu)造方法沒啥好說的系任，主要就是 將 LinkedHashMap 的 accessOrder 設(shè)置為 true 來實現(xiàn) LRU，利用訪問順序而不是插入順序虐块。

接下來是 resize 方法

resize()

/**
 * Sets the size of the cache.
 * @param maxSize The new maximum size.
 *
 * @hide
 */
public void resize(int maxSize) {
    if (maxSize <= 0) {
        throw new IllegalArgumentException("maxSize <= 0");
    }

    synchronized (this) {
        this.maxSize = maxSize;
    }
    trimToSize(maxSize);
}

重新計算緩存的大小俩滥，里面涉及到了 trimToSize 方法。另外贺奠，注意 synchronized

trimToSize()

/**
 * @param maxSize the maximum size of the cache before returning. May be -1
 *     to evict even 0-sized elements.
 */
private void trimToSize(int maxSize) {
    while (true) {// 死循環(huán)
        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) {
                break;
            }

            // BEGIN LAYOUTLIB CHANGE
            // get the last item in the linked list.
            // This is not efficient, the goal here is to minimize the changes
            // compared to the platform version.
            Map.Entry<K, V> toEvict = null;
            for (Map.Entry<K, V> entry : map.entrySet()) {
                toEvict = entry;
            }
            // END LAYOUTLIB CHANGE

            if (toEvict == null) {
                break;
            }

            key = toEvict.getKey();
            value = toEvict.getValue();
            map.remove(key);
            size -= safeSizeOf(key, value);
            evictionCount++;
        }

        entryRemoved(true, key, value, null);
    }
}

該方法根據(jù) maxSize 來調(diào)整內(nèi)存 cache 的大小霜旧，如果 maxSize 傳入 -1，則清空緩存中的所有對象儡率。該源碼可知挂据，該內(nèi)部是一個死循環(huán)，靠滿足相應(yīng)的條件達(dá)到退出的目的

• 條件1儿普，當(dāng)當(dāng)前大小 size 小于 最大容量時崎逃，退出
• 當(dāng)需要刪除的 entry 為空時，會退出眉孩。這里 請看 LAYOUTLIB CHANGE 之間的代碼婚脱，這里好像刪除的是 Map 的隊尾元素，但是，我們知道針對 LinkedHashMap 障贸，隊尾則是最新使用的元素错森，這里把最新的刪掉了，和原意相違背篮洁。注釋里面講解到：This is not efficient, the goal here is to minimize the changes compared to the platform version.

上面的代碼是 Android API 22 Platform 里面的

而在 Android API 23 Platform 里面新代碼改變了

 Map.Entry<K, V> toEvict = map.eldest();

這里可以看出涩维，是取的最久未使用的，將最久未使用的刪除了袁波。（谷歌的工程師也在不斷的調(diào)整）

里面涉及到 safeSizeOf 方法

safeSizeOf()

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

里面涉及到了我們需要復(fù)寫的方法 sizeOf

最后調(diào)用 entryRemoved 方法

entryRemoved()

/**
 * Called for entries that have been evicted or removed. This method is
 * invoked when a value is evicted to make space, removed by a call to
 * {@link #remove}, or replaced by a call to {@link #put}. The default
 * implementation does nothing.
 *
 * <p>The method is called without synchronization: other threads may
 * access the cache while this method is executing.
 *
 * @param evicted true if the entry is being removed to make space, false
 *     if the removal was caused by a {@link #put} or {@link #remove}.
 * @param newValue the new value for {@code key}, if it exists. If non-null,
 *     this removal was caused by a {@link #put}. Otherwise it was caused by
 *     an eviction or a {@link #remove}.
 */
protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {}

該方法是空方法瓦阐，看注釋可知：當(dāng) item 被回收或者刪掉時調(diào)用。該方法當(dāng) value 被回收釋放存儲空間時被 remove 調(diào)用篷牌，或者替換 item 值時 put 調(diào)用睡蟋，默認(rèn)實現(xiàn)什么都沒做。

每次回收對象就調(diào)用該函數(shù)枷颊，這里參數(shù)為 true --為釋放空間被刪除戳杀；false --get、put 或 remove 導(dǎo)致夭苗。前面類注釋可知信卡，需要用戶考量進(jìn)行重寫

接下來看 get 方法

get()

/**
 * Returns the value for {@code key} if it exists in the cache or can be
 * created by {@code #create}. If a value was returned, it is moved to the
 * head of the queue. This returns null if a value is not cached and cannot
 * be created.
 */
public final V get(K key) {
    if (key == null) {
        throw new NullPointerException("key == null");
    }

    V mapValue;
    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.
     */
    // 如果丟失了就試圖創(chuàng)建一個item
    V createdValue = create(key);
    if (createdValue == null) {
        return null;
    }
    // 接下來是如果用戶重寫了create方法后，可能會執(zhí)行到
    synchronized (this) {
        createCount++;// 創(chuàng)建數(shù)增加  
        mapValue = map.put(key, createdValue);// 將剛剛創(chuàng)建的值放入map中题造，返回的值是在map中與key相對應(yīng)的舊值（就是在放入new value前的old value）  
        // 如果有人實現(xiàn)了create方法傍菇，需要注意create方法的注釋
        /**
         * Called after a cache miss to compute a value for the corresponding key.
         * Returns the computed value or null if no value can be computed. The
         * default implementation returns null.
         *
         * <p>The method is called without synchronization: other threads may
         * access the cache while this method is executing.
         *
         * <p>If a value for {@code key} exists in the cache when this method
         * returns, the created value will be released with {@link #entryRemoved}
         * and discarded. This can occur when multiple threads request the same key
         * at the same time (causing multiple values to be created), or when one
         * thread calls {@link #put} while another is creating a value for the same
         * key.
         */
        // 涉及到了多線程會造成沖突的問題
        if (mapValue != null) {
            // There was a conflict so undo that last put
            map.put(key, mapValue);// 如果之前位置上已經(jīng)有元素了，就還把原來的放回去界赔，等于size沒變  
        } else {
            size += safeSizeOf(key, createdValue);// 如果之前的位置上沒有元素丢习，說明createdValue是新加上去的，所以要加上createdValue的size 
        }
    }
    /* 
     * 剛剛?cè)绻麢z測到舊值淮悼，因為最后舊值還是在map中泛领，但是中途被回收了，所以還是要通知別人這個對象被回收過敛惊。 
     * 所以就調(diào)用了entryRemoved
     */  
    if (mapValue != null) {
        entryRemoved(false, key, createdValue, mapValue);
        return mapValue;
    } else {
        /* 
         * 如果剛剛沒有檢測到舊值渊鞋，將新值放入map。 
         * 那么需要重新檢測是否size是否超出了maxSize瞧挤，所以就調(diào)用了trimToSize,并返回新值 
         */  
        trimToSize(maxSize);
        return createdValue;
    }
}

開頭注釋說明：通過 key 返回相應(yīng)的 item锡宋，或者創(chuàng)建返回相應(yīng)的 item。相應(yīng)的 item 會移動到隊列的頭部特恬，如果 item 的 value 沒有被 cache 或者不能被創(chuàng)建执俩，則返回 null。

這里面涉及到了 create 方法

create()

/**
 * Called after a cache miss to compute a value for the corresponding key.
 * Returns the computed value or null if no value can be computed. The
 * default implementation returns null.
 *
 * <p>The method is called without synchronization: other threads may
 * access the cache while this method is executing.
 *
 * <p>If a value for {@code key} exists in the cache when this method
 * returns, the created value will be released with {@link #entryRemoved}
 * and discarded. This can occur when multiple threads request the same key
 * at the same time (causing multiple values to be created), or when one
 * thread calls {@link #put} while another is creating a value for the same
 * key.
 */
protected V create(K key) {
    return null;
}

create 函數(shù)是根據(jù) key 來創(chuàng)建相應(yīng)的 item癌刽，但是在 LruCache 中默認(rèn)返回的是null役首。因為 LruCache 未記錄被回收的數(shù)據(jù)尝丐，這里讀者可以重寫該 create 函數(shù)，為 key 創(chuàng)建相應(yīng)的 item衡奥，這里是需要讀者自行設(shè)計爹袁。請注意，多線程會導(dǎo)致沖突

下面看一下 put 方法

put()

/**
 * Caches {@code value} for {@code key}. The value is moved to the head of
 * the queue.
 *
 * @return the previous value mapped by {@code key}.
 */
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++;// put次數(shù)增加
        size += safeSizeOf(key, value);// 計算size
        previous = map.put(key, value);// 這里其實是放到了隊尾
        if (previous != null) {// 不為空矮固，說明之前有數(shù)據(jù)失息，所以要把size減去
            size -= safeSizeOf(key, previous);
        }
    }

    if (previous != null) {
        entryRemoved(false, key, previous, value);
    }

    trimToSize(maxSize);
    return previous;
}

接下來看看 remove 方法

remove()

/**
 * Removes the entry for {@code key} if it exists.
 *
 * @return the previous value mapped by {@code key}.
 */
public final V remove(K key) {
    if (key == null) {
        throw new NullPointerException("key == null");
    }

    V previous;
    synchronized (this) {
        previous = map.remove(key);// 刪除key，并返回舊值  
        if (previous != null) {
            size -= safeSizeOf(key, previous);// 如果舊值不為空档址，則為size減去其舊值大小  
        }
    }

    if (previous != null) {
        entryRemoved(false, key, previous, null);
    }

    return previous;
}

最后看看其他方法

其他方法

 /**
 * Returns the size of the entry for {@code key} and {@code value} in
 * user-defined units.  The default implementation returns 1 so that size
 * is the number of entries and max size is the maximum number of entries.
 * 返回用戶定義的item的大小盹兢，默認(rèn)返回1代表item的數(shù)量，最大size就是最大item值
 * <p>An entry's size must not change while it is in the cache.
 */
protected int sizeOf(K key, V value) {
    return 1;
}

/**
 * Clear the cache, calling {@link #entryRemoved} on each removed entry.
 */
public final void evictAll() {
    trimToSize(-1); // -1 will evict 0-sized elements 清除map中全部的數(shù)據(jù) 
}

/**
 * For caches that do not override {@link #sizeOf}, this returns the number
 * of entries in the cache. For all other caches, this returns the sum of
 * the sizes of the entries in this cache.
 */
public synchronized final int size() {
    return size;
}

/**
 * For caches that do not override {@link #sizeOf}, this returns the maximum
 * number of entries in the cache. For all other caches, this returns the
 * maximum sum of the sizes of the entries in this cache.
 */
public synchronized final int maxSize() {
    return maxSize;
}

/**
 * Returns the number of times {@link #get} returned a value that was
 * already present in the cache.
 */
public synchronized final int hitCount() {
    return hitCount;
}

/**
 * Returns the number of times {@link #get} returned null or required a new
 * value to be created.
 */
public synchronized final int missCount() {
    return missCount;
}

/**
 * Returns the number of times {@link #create(Object)} returned a value.
 */
public synchronized final int createCount() {
    return createCount;
}

/**
 * Returns the number of times {@link #put} was called.
 */
public synchronized final int putCount() {
    return putCount;
}

/**
 * Returns the number of values that have been evicted.
 */
public synchronized final int evictionCount() {
    return evictionCount;
}

/**
 * Returns a copy of the current contents of the cache, ordered from least
 * recently accessed to most recently accessed.
 */
public synchronized final Map<K, V> snapshot() {
    return new LinkedHashMap<K, V>(map);// 返回當(dāng)前緩存中所有的條目集合
}

@Override public synchronized final String toString() {
    int accesses = hitCount + missCount;
    int hitPercent = accesses != 0 ? (100 * hitCount / accesses) : 0;
    return String.format("LruCache[maxSize=%d,hits=%d,misses=%d,hitRate=%d%%]",
            maxSize, hitCount, missCount, hitPercent);
}

看相關(guān)注釋守伸，不難理解

總結(jié)

• LruCache 封裝了 LinkedHashMap绎秒，提供了 LRU 緩存的功能；
• LruCache 通過 trimToSize 方法自動刪除最近最少訪問的鍵值對尼摹；
• LruCache 不允許空鍵值见芹；
• LruCache 線程安全；
• LruCache 的源碼在不同版本中不一樣窘问，需要區(qū)分
• 繼承 LruCache 時辆童，必須要復(fù)寫 sizeOf 方法宜咒，用于計算每個條目的大小惠赫。

參考鏈接

LruCache 源碼解析

Android中LruCache的源碼分析

Android LruCache源碼詳解