LRU 是 Least Recently Used 的縮寫，即“最近最少使用”，說(shuō)明 LRU 緩存算法的淘汰策略是把最近最少使用的數(shù)據(jù)移除，讓出內(nèi)存給最新讀取的數(shù)據(jù)。下面看一下 Android開發(fā)中的LruCache 。

Android.util.LruCache

這個(gè)LruCache 在 android.util 包下，是 API level 12 引入的，對(duì)于 API level 12 之前的系統(tǒng)可以使用 support library 中的 LruCache 。先來(lái)看看 android.util.LruCache 的源碼。

首先是成員變量：

private final LinkedHashMap<K, V> map;

    /** Size of this cache in units. Not necessarily the number of elements. */

    private int size;

    private int maxSize;

    private int putCount;

    private int createCount;

    private int evictionCount;

    private int hitCount;

    private int missCount;

LruCache 內(nèi)部使用一個(gè) LinkedHashMap 作為存儲(chǔ)容器，并對(duì)各種操作進(jìn)行計(jì)次。

構(gòu)造器：

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

    }

構(gòu)造器的參數(shù)maxSize 用于指定緩存的最大容量，并初始化一個(gè) LinkedHashMap ，順便看看這個(gè) LinkedHashMap 的構(gòu)造函數(shù)：

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {

        super(initialCapacity, loadFactor);

        init();

        this.accessOrder = accessOrder;

    }

initialCapacity 即初始容量設(shè)為 0 ，裝填因子 loadFactor 設(shè)為 0.75 ， accessOrder 設(shè)為 true ，即鏈表中的元素按照最近最少訪問(wèn)到最多訪問(wèn)排序。這里設(shè)置的裝填因子為 0.75 ，設(shè)置其它值行不行呢？在 LinkedHashMap 這個(gè)構(gòu)造器中只是將 loadFactor 作為參數(shù)傳給了父類構(gòu)造器，該父類構(gòu)造器如下：

public HashMap(int capacity, float loadFactor) {

        this(capacity);

        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {

            throw new IllegalArgumentException("Load factor: " + loadFactor);

        }

        /*

         * Note that this implementation ignores loadFactor; it always uses

         * a load factor of 3/4. This simplifies the code and generally

         * improves performance.

         */

    }

調(diào)用了HashMap 的構(gòu)造器，可以看到只是對(duì) loadFactor 進(jìn)行了合法檢查，除此之外沒(méi)有其他調(diào)用或賦值操作， Note 中解釋了，這個(gè) loadFactor 沒(méi)用，裝填因子永遠(yuǎn)使用 3/4 ，也就是 0.75 。所以在構(gòu)造 LinkedHashMap 時(shí)，設(shè)了裝填因子也沒(méi)什么用。

繼續(xù)看LruCache ， resize 方法更新鏈表容量，調(diào)用 trimToSize 方法。

public void resize(int maxSize) {

        if (maxSize <= 0) {

            throw new IllegalArgumentException("maxSize <= 0");

        }

        synchronized (this) {

            this.maxSize = maxSize;

        }

        trimToSize(maxSize);

    }

先看get 方法， key 為空會(huì)拋異常，取出對(duì)應(yīng)的 value ，若不為空則命中次數(shù) hitCount 加 1 并 return 這個(gè) value ，否則 missCount 加 1 。該 value 為空時(shí)繼續(xù)向下執(zhí)行，根據(jù) key 嘗試創(chuàng)建 value ，如果創(chuàng)建返回的 createdValue 是 null ，那就確實(shí)沒(méi)有該值，若創(chuàng)建操作返回的 createdValue 不為 null ，則嘗試把 createdValue 放回 map ，若存在舊值則返回舊值，否則返回這個(gè) createdValue 。

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++;

        }

        V createdValue = create(key);

        if (createdValue == null) {

            return 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;

        }

    }

put 方法將鍵值對(duì)放入 map ，重新計(jì)算大小之后調(diào)用 trimToSize 方法，刪除訪問(wèn)次數(shù)最少的元素。

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++;

            size += safeSizeOf(key, value);

            previous = map.put(key, value);

            if (previous != null) {

                size -= safeSizeOf(key, previous);

            }

        }

        if (previous != null) {

            entryRemoved(false, key, previous, value);

        }

        trimToSize(maxSize);

        return previous;

    }

trimToSize 方法中會(huì)一直嘗試刪除隊(duì)首元素即訪問(wèn)次數(shù)最少的元素，直到 size 不超過(guò)最大容量或?qū)⒁獎(jiǎng)h除的對(duì)象為空。

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) {

                    break;

                }

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

        }

    }

android.support.v4.util.LruCache

support v4 包中的 LruCache 可以用于 API level 12 之前的系統(tǒng)，和 android.util 包的 LruCache 的區(qū)別是在 trimToSize 中獲取將要?jiǎng)h除元素的方法不一樣：

· android.util.LruCache

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

· android.support.v4.util.LruCache

Map.Entry<K, V> toEvict = map.entrySet().iterator().next();

LinkedHashMap 的 eldest() 方法已經(jīng)被標(biāo)注為 @hide ，所以使用 android.support.v4.util.LruCache 更加保險(xiǎn)一點(diǎn)。

來(lái)源：簡(jiǎn)書