前言：自从Andorid3.1之后，谷歌引入了LruCache，官方文档说明如下：
* A cache that holds strong references to a limited number of values. Each time
* a value is accessed, it is moved to the head of a queue. When a value is
* added to a full cache, the value at the end of that queue is evicted and may
* become eligible for garbage collection.
*
* <p>If your cached values hold resources that need to be explicitly released,
* override {@link #entryRemoved}.
*
* <p>If a cache miss should be computed on demand for the corresponding keys,
* override {@link #create}. This simplifies the calling code, allowing it to
* assume a value will always be returned, even when there's a cache miss.
*
* <p>By default, the cache size is measured in the number of entries. Override
* {@link #sizeOf} to size the cache in different units. For example, this cache
*
* <p>This class does not allow null to be used as a key or value. A return
* value of null from {@link #get}, {@link #put} or {@link #remove} is
* unambiguous: the key was not in the cache.
*
- 官方文档指出几点:
--hold strong reference: 该缓存引用的是强引用。
--a value is accessed, it is moved to the head of a queue ：每次一个数据被访问，就会被移到对头
--要重载sizeof用于测量当前内存大小
--不支持空的key。
LRU:什么是LRU算法？ LRU是Least Recently Used的缩写，即最近最少使用
LruCache里面最重要的是维护了一个双向链表（该链表支持有序插入）用于存放缓存数据,LinkedHashMap底层正是实现了LRU算法.
private final LinkedHashMap<K, V> map;
LinkedHashMap :
- LinkedHashMap is an implementation of {@link Map} that guarantees > iteration order.
- All optional operations are supported.
- <p>All elements are permitted as keys or values, including null.
- <p>Entries are kept in a doubly-linked list. The iteration order is, by > > > default, theorder in which keys were inserted. Reinserting an already-present key > doesn't change theorder. If the three argument constructor is used, and {@code accessOrder} is specified as
{@code true}, the iteration will be in the order that entries were accessed.- The access order is affected by {@code put}, {@code get}, and {@code putAll} operations,
- but not by operations on the collection views.
LinkedHashMap 继承HashMap,里面维护一个内部类LinkeEntry双向链表用于存储数据。
具体分析可以看该博客：图解LinkedHashMap原理
我们先开LruCache的构造函数
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);
}
构造了一个LinkedHashMap，而且第三个参数为true，表示访问有序(这个是实现该LruCache算法的核心。)
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);
previous = map.put(key, value);
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {
entryRemoved(false, key, previous, value);
}
trimToSize(maxSize);
return previous;
}
分析：
每次放入一个数据，size会根据当前的数据大小增加
private int safeSizeOf(K key, V value) {
int result = sizeOf(key, value);//该方法就是上面说的要重写的方法
if (result < 0) {
throw new IllegalStateException("Negative size: " + key + "=" + value);
}
return result;
}
然后将数据放入map，返回一个previous,其中，map.put(key, value):
HashMap.java
@Override public V put(K key, V value) {
if (key == null) {
return putValueForNullKey(value);
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
if (e.hash == hash && key.equals(e.key)) {
preModify(e);
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
// No entry for (non-null) key is present; create one
modCount++;
if (size++ > threshold) {
tab = doubleCapacity();
index = hash & (tab.length - 1);
}
addNewEntry(key, value, hash, index);
return null;
}
当当前的key在map里面是有的时候，返回旧的数据,并且被回收掉。
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {
entryRemoved(false, key, previous, value);
}
public void trimToSize(int maxSize) {
while (true) {
K key;
V value;
synchronized (this) {
//如果重载的sizeof方法返回的大小单位跟max传入的大小单位不同，这里会报错
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);
}
对缓存进行内存裁剪，不断第将队尾的数据删除，直到size<=maxSize.
其中最关键的就是map.eldest()这段代码，拿到当前最老的数据，也就是说最近最少访问的数据。
public Entry<K, V> eldest() {
LinkedEntry<K, V> eldest = header.nxt;
return eldest != header ? eldest : null;
}
由于在构造LinkedMap的时候，构造参数accessOrder是true,也就是说当前的链表的顺序是根据访问时间去定当前数据的位置，越久没访问，越前。
LinkedHashMap:
/**
* Relinks the given entry to the tail of the list. Under access ordering,
* this method is invoked whenever the value of a pre-existing entry is
* read by Map.get or modified by Map.put.
*/
private void makeTail(LinkedEntry<K, V> e) {
// Unlink e
e.prv.nxt = e.nxt;
e.nxt.prv = e.prv;
// Relink e as tail
LinkedEntry<K, V> header = this.header;
LinkedEntry<K, V> oldTail = header.prv;
e.nxt = header;
e.prv = oldTail;
oldTail.nxt = header.prv = e;
modCount++;
}
上面就是每次调整数据顺序的代码。
--在如果做图片处理的时候，可以复写entryRemoved对从map里面移除的图片进行复用内存。
get方法：
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++;
}
/*
* Attempt to create a value. This may take a long time, and the map
* may be different when create() returns. If a conflicting value was
* added to the map while create() was working, we leave that value in
* the map and release the created value.
*/
V createdValue = create(key);
if (createdValue == null) {
return null;
}
//下面代码跟put的代码差不多，也是新建一个value放入map
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;
}
}
该方法有个特殊的地方就是，如果map里面没有对应的key的数据或者出于其他原因key对应的数据被删除了，提供了create(key)方法给用于去重新创建对应的数据。
LruCache
