公子姓王

在之前講LinkedHashMap的時候,我們說起可以用來實現(xiàn)LRU(least recent used)算法,接下來我看一下其中的一個具體實現(xiàn)-----android sdk 中的LruCache.

關于Lru算法,請參考漫畫:什么是LRU算法?

talk is cheap, I am gonna show you something really expensive.

package android.util;// 該類是從Android sdk 中摘錄

public class LruCache<K, V> {

    private final LinkedHashMap<K, V> map;// 這里的 LinkedHashMap 為 android.jar 中的類,與jdk中的有所區(qū)別,這里不做區(qū)分
    private int size;// 當前 cache 的大小
    private int maxSize;// cache 最大容量
    private int putCount;// put() 調(diào)用的次數(shù)
    private int createCount;// get()未命中,成功構建新 key:value 的次數(shù)
    private int evictionCount;// 因cache大小超過容量限制,將 key:value 從 cache 中驅(qū)逐的次數(shù)
    private int hitCount;// get()命中的次數(shù)
    private int missCount;// get()未命中的次數(shù)

    // 構造時設置最大容量
    public LruCache(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("maxSize <= 0");
        }
        this.maxSize = maxSize;
        // 這里傳入的 LinkedHashMap 的 accessOrder 為true,表示 其中的鏈表中的結點順序為 "按訪問順序"
        this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
    }

    // 重新設置 cache 最大容量
    public void resize(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("maxSize <= 0");
        }
        synchronized (this) {
            this.maxSize = maxSize;
        }
        trimToSize(maxSize);
    }

    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++;// 命中次數(shù) + 1
                return mapValue;
            }
            missCount++;// 未命中次數(shù) + 1
        }
        V createdValue = create(key);// 通過 key 構建一個value(比如從文件中讀入value)
        if (createdValue == null) {// 創(chuàng)建失敗
            return null;
        }
        synchronized (this) {
            createCount++;// 構建 value 成功次數(shù) + 1
            mapValue = map.put(key, createdValue);// 添加到 LinkedHashMap 中
            if (mapValue != null) {
                // LinkedHashMap 原來有該key的值(在構建value的時候,被其他線程添加進去的),這里重新把原來的值放進去,cache大小沒有增加
                map.put(key, mapValue);
            } else {
                size += safeSizeOf(key, createdValue);// cache 大小增加
            }
        }
        if (mapValue != null) {
            entryRemoved(false, key, createdValue, mapValue);
            return mapValue;
        } else {
            trimToSize(maxSize);// 大小增加了,保證在最大容量范圍內(nèi)
            return createdValue;
        }
    }

    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);
            previous = map.put(key, value);
            if (previous != null) {
                size -= safeSizeOf(key, previous);// 替換已有的value
            }
        }
        if (previous != null) {
            entryRemoved(false, key, previous, value);
        }
        trimToSize(maxSize);
        return previous;
    }

    // 移除LRU鍵值對,保證 cache 的大小在 maxSize 范圍內(nèi)
    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();// 最老的結點,返回head結點,也即 LRU結點
                if (toEvict == null) {// 沒有可以刪除的key:value了
                    break;
                }
                key = toEvict.getKey();
                value = toEvict.getValue();
                map.remove(key);
                size -= safeSizeOf(key, value);// 大小降低
                evictionCount++;// 驅(qū)逐次數(shù) + 1
            }
            entryRemoved(true, key, value, null);
        }
    }

    public final V remove(K key) {
        if (key == null) {
            throw new NullPointerException("key == null");
        }
        V previous;
        synchronized (this) {
            previous = map.remove(key);// 通過 LinkedHashMap 移除
            if (previous != null) {
                size -= safeSizeOf(key, previous);// cache總大小降低
            }
        }
        if (previous != null) {
            entryRemoved(false, key, previous, null);
        }
        return previous;
    }

    // key:oldValue 被 移除 或 驅(qū)逐 時回調(diào)
    protected void entryRemoved(boolean evicted/*是否是被驅(qū)逐(因cache大小超過容量限制被刪除)*/,
                                K key, V oldValue, V newValue) {
    }

    // 根據(jù)指定 key,構建 value
    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;
    }

    // key:value 鍵值對大小,用于計算cache大小
    // 可根據(jù)情況自定義,默認為 1
    // 該 key:value 在 cache 中時大小不應該變化
    protected int sizeOf(K key, V value) {
        return 1;
    }

    public final void evictAll() {
        trimToSize(-1); // -1 will evict 0-sized elements
    }

    // 各種方法,返回成員變量,省略
    public synchronized final Map<K, V> snapshot() {
        return new LinkedHashMap<K, V>(map);
    }

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

}