Android緩存機制——LruCache

Android緩存機制——LruCache

LruCache的核心原理就是對LinkedHashMap的有效利用，它的内部存在一個LinkedHashMap成員變量，值得注意的4個方法：構造方法、get、put、trimToSize

LRU(Least Recently Used)緩存算法便應運而生，LRU是最近最少使用的算法，它的核心思想是當緩存滿時，會優先淘汰那些最近最少使用的緩存對象。采用LRU算法的緩存有兩種：LrhCache和DisLruCache，分别用于實作記憶體緩存和硬碟緩存，其核心思想都是LRU緩存算法。

LRU原理

LruCache的核心思想很好了解，就是要維護一個緩存對象清單，其中對象清單的排列方式是按照通路順序實作的，即一直沒通路的對象，将放在隊尾，即将被淘汰。而最近通路的對象将放在隊頭，最後被淘汰。

LruCache 其實使用了 LinkedHashMap 雙向連結清單結構，現在分析下 LinkedHashMap 使用方法。

1.構造方法：

複制代碼

public LinkedHashMap(int initialCapacity,

float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;           

}

當 accessOrder 為 true 時，這個集合的元素順序就會是通路順序，也就是通路了之後就會将這個元素放到集合的最後面。

例如：

LinkedHashMap < Integer, Integer > map = new LinkedHashMap < > (0, 0.75f, true);

map.put(0, 0);

map.put(1, 1);

map.put(2, 2);

map.put(3, 3);

map.get(1);

map.get(2);

for (Map.Entry < Integer, Integer > entry: map.entrySet()) {

System.out.println(entry.getKey() + ":" + entry.getValue());
           

輸出結果：

0:0

3:3

1:1

2:2

下面我們在LruCache源碼中具體看看，怎麼應用LinkedHashMap來實作緩存的添加，獲得和删除的：

/**

* @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) {
        throw new IllegalArgumentException("maxSize <= 0");
    }
    this.maxSize = maxSize;
    this.map = new LinkedHashMap<K, V>(0, 0.75f, true);//accessOrder被設定為true
}           

從LruCache的構造函數中可以看到正是用了LinkedHashMap的通路順序。

2.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++;//插入緩存對象加1
        size += safeSizeOf(key, value);//增加已有緩存的大小
        previous = map.put(key, value);//向map中加入緩存對象
        if (previous != null) {//如果已有緩存對象，則緩存大小恢複到之前
            size -= safeSizeOf(key, previous);
        }
    }

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

    trimToSize(maxSize);//調整緩存大小(關鍵方法)
    return previous;
}           

可以看到put()方法重要的就是在添加過緩存對象後，調用 trimToSize()方法來保證記憶體不超過maxSize

3.trimToSize方法

再看一下trimToSize()方法：

/**

* Remove the eldest entries until the total of remaining entries is at or
 * below the requested size.
 *
 * @param maxSize the maximum size of the cache before returning. May be -1
 *            to evict even 0-sized elements.
 */
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) {
                break;
            }           

　　　　　　　　　　// 取出 map 中最老的映射

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);
    }
}           

trimToSize()方法不斷地删除LinkedHashMap中隊頭的元素，即近期最少通路的，直到緩存大小小于最大值。

1. get方法

   當調用LruCache的get()方法擷取集合中的緩存對象時，就代表通路了一次該元素，将會更新隊列，保持整個隊列是按照通路順序排序。這個更新過程就是在LinkedHashMap中的get()方法中完成的。

接着看LruCache的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) {//key不能為空
        throw new NullPointerException("key == null");
    }

    V mapValue;
    synchronized (this) {           

　　　　　　　　/擷取對應的緩存對象

mapValue = map.get(key);
        if (mapValue != null) {
            hitCount++;
            return mapValue;
        }
        missCount++;
    }           

看到LruCache的get方法實際是調用了LinkedHashMap的get方法：

public V get(Object key) {

LinkedHashMapEntry<K,V> e = (LinkedHashMapEntry<K,V>)getEntry(key);
    if (e == null)
        return null;
    e.recordAccess(this);//實作排序的關鍵
    return e.value;
}           

再接着看LinkedHashMapEntry的recordAccess方法：

　　　　 /**

* This method is invoked by the superclass whenever the value
     * of a pre-existing entry is read by Map.get or modified by Map.set.
     * If the enclosing Map is access-ordered, it moves the entry
     * to the end of the list; otherwise, it does nothing.
     */
    void recordAccess(HashMap<K,V> m) {
        LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
        if (lm.accessOrder) {//判斷是否是通路順序
            lm.modCount++;
            remove();//删除此元素
            addBefore(lm.header);//将此元素移到隊尾
        }
    }           

recordAccess方法的作用是如果accessOrder為true，把已存在的entry在調用get讀取或者set編輯後移到隊尾，否則不做任何操作。

也就是說： 這個方法的作用就是将剛通路過的元素放到集合的最後一位

5.總結：

LruCache的核心原理就是對LinkedHashMap 對象的有效利用。在構造方法中設定maxSize并将accessOrder設為true，執行get後會将通路元素放到隊列尾，put操作後則會調用trimToSize維護LinkedHashMap的大小不大于maxSize。

參考：

https://juejin.im/post/5b5d4e2d6fb9a04fc226c09f

；

https://www.cnblogs.com/ganchuanpu/p/8908264.html

原文位址

https://www.cnblogs.com/ivoo/p/10744558.html