大厂面试问“图片如何进行缓存”的时候主要在考察什么？
- 是否对缓存淘汰算有一定的研究；
- 是否对常见的图片加载框架有深入研究；
- 是否对算法效果有验证闭环的意识，对使用场景是否适合。
一、题目剖析
1.1 如何对图片进行缓存？
- 缓存介质，网络/磁盘/内存缓存；
- 缓存算法的设计分析（关键，不同的目标对象、使用场景，使用不同的算法的效果是有差别的）；
- 以熟悉的框架为例分析它的缓存机制；
- 要有验证算法效果的（优化、量化）意识。
1.2 如何评价缓存算法是否合适？
- 获取成本很高的话缓存就很值；
- 缓存对象很大，1g，内存都不够用，缓存不合适；
- 缓存的价值是由获取成本、缓存成本和时间决定的，很有价值的缓存对象，之后用的不多了或者不再用了，它的缓存价值就趋于零了。缓存算法的衡量指标，用一个词来描述就是“命中率”。
二、缓存算法
缓存算法要解决的问题：缓存媒介放满后，新来的缓存媒介里没有对象，要放在什么位置？把哪个对象淘汰？真实算法设计中还要考虑每个对象的权重。算法就决定谁被干掉。
2.1 LRU（Least Recently Used，最近最少使用）
依次访问A-B-D-D，由于D已经缓存过了，因此当再次访问D的时候直接用缓存里得对象：
再次对B访问时，B再次命中后，依然直接用缓存对象，但是要移动B到缓存末尾：
访问C缓存没有，缓存未满，直接插到缓存末尾，保持最近使用的一直排在最后面：
这时再访问A，缓存有，直接拿来用，并将A移至末尾：
接着继续访问E，缓存中没有缓存过，需要放进缓存，此时介质存满了（达到上限），需要删掉一个原有对象，LRU就要把缓存起始位置的D干掉，E依然放到最后位置：
2.2 LFU（Least Frequently Used，最不经常使用）
从使用频率的角度来讲还有LFU，需要看具体使用场景，大多数的图片都是用LRU算法。
依次访问A-B-D-D，D访问两次，会对D对象计数为2：
继续接着访问B，要把B计数为2，并移到末尾处：
继续访问C，由于第一次对C访问，需要加入缓存：
继续访问A，把缓存原有的A计数加一，为2，移至末尾位置：
接着，再访问E，缓存内没有，需要放至缓存，恰巧缓存也没有多余的位置，需要删除一个原有的对象，LFU会干掉最近没再使用C，并把E放进去。其实，使用频率相同的情况，也有排序，最近使用过的在最后。
LRU能清楚算法设计的细节就很OK，LFU辅助理解。
三、实现细节看代码
3.1 Android里面就有LruCache
/* android.util. LruCache */
// 泛型是key和value，key是查找时的标识，value就是缓存对象，如bitmap
public class LruCache<K, V> {
// 所有lru的实现里面都有一个内部map数据结构，注意构造参数
@UnsupportedAppUsage
private final LinkedHashMap<K, V> map;
private int size;
private int maxSize;
// 统计监控用的变量，看似没用，额外占用了4x5=20个字节，主要用来监控算法的有效性
// 一点额外的开销，可以监控到整个运行状态，是否需要继续调整算法全部取决于这些监控数据
private int putCount;//存放个数
private int createCount;// 创建个数
private int evictionCount;// 弹出个数
private int hitCount;// 命中个数
private int missCount;// 未命中个数
public LruCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
this.maxSize = maxSize;
// 初始化的时候new出来，true表示每次访问后会的对象被丢到整个链表数据结构末尾
this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}
// …
protected int sizeOf(K key, V value) {
return 1;// 权重，默认1
}
// …
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++;
}
// create通常需要复写实现的，所以没加锁
// 创建不需要涉及lru内部数据的访问，不需要加锁
V createdValue = create(key);
if (createdValue == null) {
return null;
}
// 如果没使用CAS和volatile，加锁是最简单的线程安全
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;
}
}
// …
// 新进来对象超出了限制个数，就会弹出现有的对象
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);
}
}
// …
}
3.2 Glide也有类的cache类
没有create
/* com.bumptech.glide.util.LruCache */
public class LruCache<T, Y> {
private final Map<T, Entry<Y>> cache = new LinkedHashMap<>(100, 0.75f, true);
private final long initialMaxSize;
private long maxSize;
private long currentSize;
@Nullable
public synchronized Y put(@NonNull T key, @Nullable Y item) {
final int itemSize = getSize(item);
if (itemSize >= maxSize) {
onItemEvicted(key, item);
return null;
}
if (item != null) {
currentSize += itemSize;
}
@Nullable Entry<Y> old = cache.put(key, item == null ? null : new Entry<>(item, itemSize));
if (old != null) {
currentSize -= old.size;
if (!old.value.equals(item)) {
onItemEvicted(key, old.value);
}
}
evict();
return old != null ? old.value : null;
}
// …
protected synchronized void trimToSize(long size) {
Map.Entry<T, Entry<Y>> last;
Iterator<Map.Entry<T, Entry<Y>>> cacheIterator;
while (currentSize > size) {
// 取元素
cacheIterator = cache.entrySet().iterator();
last = cacheIterator.next();
final Entry<Y> toRemove = last.getValue();
currentSize -= toRemove.size;
final T key = last.getKey();
cacheIterator.remove();
onItemEvicted(key, toRemove.value);
}
}
3.3 OkHttp的DiskLruCache
/* okhttp3.internal.cache.DiskLruCache */
public final class DiskLruCache implements Closeable, Flushable {
final LinkedHashMap<String, Entry> lruEntries = new LinkedHashMap<>(0, 0.75f, true);
void trimToSize() throws IOException {
while (size > maxSize) {
Entry toEvict = lruEntries.values().iterator().next();
removeEntry(toEvict);
}
mostRecentTrimFailed = false;
}
3.4 LinkedHashMap源码
// ...
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);// move node to last
return e.value;
}
/*
* 将被访问的元素移到链表尾部，迭代器访问的第一个元素最老，通常就是要移除的对象
* 其实只要看那一行注释就明了了
*/
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMapEntry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMapEntry<K,V> p =
(LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
四、总结
- 探讨缓存的形式、价值衡量标准
- 阐述LRU、LFU算法的设计思路
- 分析常见框架的LRU算法实现