LRUCache的實現原理

2019-11-09 18:44:56

字體：大中小

來源：轉載

供稿：網友

簡介

LRU(Least Recently Used)最近最少使用，最近有時間和空間最近的歧義，所以我更喜歡叫它近期最少使用算法。它的核心思想是，如果一個數據被訪問過，我們有理由相信它在將來被訪問的概率就越高。于是當LRU緩存達到設定的最大值時將緩存中近期最少使用的對象移除。LRUCache內部使用LinkedHashMap來存儲key-value鍵值對，并將LinkedHashMap設置為訪問順序來體現LRU算法。

簡單使用

// 拿到當前的最大內存long maxMemory = Runtime.getRuntime().maxMemory();int cacheSize = (int) (maxMemory / 8);// 將LruCache的緩存容量設置為cacheSize，并重寫sizeOf方法。lruCache = new LruCache<String, Bitmap>(cacheSize) { @Override PRotected int sizeOf(String key, Bitmap value) { return value.getByteCount(); }};// put一條數據lruCache.put(key, bitmap);// get一條數據lruCache.get(key);// remove一條數據lruCache.remove(key);

數據結構

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

可以看到，除了初始化maxSize，還初始化了一個全局的LinkedHashMap,當第三個參數設為true時，map被設置為訪問順序，也就是每操作一次map的某個Entry，它就會被放到雙向鏈表的隊尾。也就是說LRU算法的任務，完全交給了LinkedHashMap。

put方法

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); // 如果key不沖突就返回null // 如果key沖突就用value替換odlValue,并返回oldValue previous = map.put(key, value); if (previous != null) { size -= safeSizeOf(key, previous); } } if (previous != null) { entryRemoved(false, key, previous, value); } trimToSize(maxSize); return previous; }

數據通過key-value的形式被put到了map里，在put之前通過sizeOf方法計算value的size，并累加到全局變量size里，它用來記錄當前緩存的數據大小。sizeOf原則上必須重寫，用來定義自己的計算規則。然后調用了trimToSize方法，這個方法用以保證緩存大小不會超過maxSize。

trimToSize方法

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 || map.isEmpty()) { break; } Map.Entry<K, V> toEvict = map.entrySet().iterator().next(); key = toEvict.getKey(); value = toEvict.getValue(); map.remove(key); size -= safeSizeOf(key, value); evictionCount++; } entryRemoved(true, key, value, null); } }

一進來就是一個死循環，然后就迭代刪除位于隊首的數據。只有當前緩存容量小于maxSize的時候才break。

綜上 LruCache自己主要是實現maxSize的判斷，以及通過trimToSize對緩存的裁剪。其他存儲、提取數據的方法以及LRU的算法都是借助LinkedHashMap來實現的。

上一篇：給UITableView的側滑刪除增加多個按鈕

下一篇：常見內存泄漏分析