LRU算法及其优化

LRU（Least Recently Used，最近最少使用）的本质是一个链表，新数据插入到链表头部，每当缓存命中，则将数据移到链表头部，当链表满了或者需要清理内存时，将链表尾部的数据丢弃。

特点：当存在热点数据时，LRU 的效率很高，但偶发性的、周期性的批量操作会导致 LRU 命中率急剧下降，产生缓存污染的（将不常用的数据也存入缓存，降低了缓存效率）问题，且每次缓存命中时，都需要遍历链表，找到命中的数据块索引并移到头部。

1. LRU-K

为了改善 LRU 算法的缓存污染问题，额外维护一个队列用于记录所有缓存数据被访问的历史，只有当数据的访问次数打到 K 次，才存入缓存中。当数据被访问次数不到 K 次时，按照一定规则（FIFO、LRU 等）淘汰，当历史队列中的数据访问达到 K 次后，将其从队列中删除转移到缓存中，并按照时间顺序重新排列缓存数据，且缓存中的数据每次被访问后重新排序。当需要清理缓存时，淘汰缓存中排在末尾的数据，也即淘汰距离上次访问最久的数据。

特点：LRU-K 降低了缓存污染带来的代价，命中率比 LRU 高，但由于其历史队列和缓存中的数据都具有优先级（可以即时排序也可以在需要淘汰数据时才排序），因此其算法复杂度和性能代价较高。尤其当有大量存入历史队列却还未存入缓存中的数据时，内存消耗较大。

通常，LRU-2 是综合因素下的最优选择，LRU-3 或更高 K 值会提高命中率，但适应性较差，需要大量的数据访问才能冲洗历史队列表。

2. LRU-Two Queues

LRU-2Q 祛除了历史队列，而是直接使用两个缓存队列进行管理，其中一个缓存队列采用 FIFO 淘汰规则，另一个缓存队列采用 LRU 淘汰规则。一个新的数据首次被访问时，假如 FIFO 队列，当该数据再次被访问时，则转移到 LRU 队列中，LRU 队列中的数据再次被访问时，则移至 LRU 队列的头部，两个队列分别根据对应的淘汰规则按需淘汰数据。

L特点：RU-2Q 的命中率高于 LRU，尽管需要两个队列，但两个队列的维护算法都比较简单。LRU-2Q 和 LRU-2 命中率、内存消耗都比较接近，不同处在于，LRU-2 中，数据首次被访问加入历史队列后，需要被访问 2 次才转移至缓存中，而 LRU-2Q 在数据首次被访问加入 FIFO 队列后，仅需再被访问 1 次即转移到缓存中。

3. LRU-Multi Queues

LRU-MQ 拥有一个 LRU 历史队列 和 K 个 LRU 缓存队列，均采用 LRU 淘汰规则。当一个数据首次被访问时，加入到最低优先级的 LRU 缓存队列中，队列中的数据每次被访问则重新计算优先级并排序，当低优先级的队列中，当某个数据优先级达到下一级 LRU 缓存队列时，将其从当前 LRU 缓存队列转移到更高级的 LRU 缓存队列的头部。为避免高优先级的数据永不淘汰，当高优先级的 LRU 缓存队列中某个数据在指定时间内未被访问时，降低其优先级并转移到低优先级的 LRU 缓存队列的头部。所有 K 个 LRU 缓存队列中被淘汰的数据，均转移到 LRU 历史队列的头部，若 LRU 历史队列中的数据重新被访问，则重新计算优先级，并根据优先级转移到目标 LRU 缓存队列的头部，否则根据 LRU 算法直到被完全淘汰，

LRU-MQ 进一步降低了缓存污染的问题，着重突出了“优先缓存访问次数多的数据”的思想，但由于具有多个队列，且每个队列都需要维护每个数据的访问时间，当 LRU-MQ 中队列数和数据量过多时，具有较高的复杂度。不过，尽管 LRU-MQ 的队列数量较多，但由于内存是有限的，因此所有的队列所占内存之和仍是受限的，因此多个短队列的长度之和与单个长队列的长度相差不大，其队列扫描性能仍然比较接近。

4. LRUCache

1
2
3
4
5
6
7
8
9
10
11

private LruCache<String, Bitmap> mLruCache = new LruCache<String, Bitmap>(cacheSize) {
    @Override
    protected int sizeOf(String key, Bitmap value) {
        //计算一个元素的缓存大小
        return value.getByteCount();
    }
};

addBitmap(String key, Bitmap bitmap) {}
getBitmap(String key) {}
removeBitmapFromMemory(String key) {}