LRU（Least Recently Used）最近最少使用算法
原理
缓存保存了一个强引用（Android 2.3开始，垃圾回收器更倾向于回收弱引用和软引用，软引用和弱引用变得不可靠，Android 3.0中，图片的数据会存储在本地的内存当中，因而无法用一种可预见的方式将其释放）限制值的数量. 每当值被访问的时候，它会被移动到队列的头部. 当缓存已满的时候加入新的值时，队列中最后的值会出队，可能被回收
LRUCache内部维护主要是通过LinkedHashMap实现
这是一个安全的线程，多线程缓存通过同步实现
使用
默认情况下，缓存的大小是由值的数量决定，重写sizeOf计算不同的值
如果你缓存值需要明确释放，重写entryRemoved()
int maxMemory = (int) Runtime.getRuntime().maxMemory();
int mCacheSize = maxMemory / 8;
//给LruCache分配1/8 4M
mMemoryCache = new LruCache<String, Bitmap>(mCacheSize){
//必须重写此方法，来测量Bitmap的大小
@Override
protected int sizeOf(String key, Bitmap value) {
return value.getRowBytes() * value.getHeight();
}
};
mMemoryCache.put(key, bitmap)
mMemoryCache.get(key)
这个类不允许有空的键值. get，put，remove 返回空值，key对应的值不在缓存中
源码分析
构造函数
/**
* @param maxSize for caches that do not override {@link #sizeOf}, this is
* the maximum number of entries in the cache. For all other caches,
* this is the maximum sum of the sizes of the entries in this cache.
*/
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
public LinkedHashMap(
int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
init();
this.accessOrder = accessOrder;
}
initialCapacity：初始化hashMap的容量，这个值必须大于等于0
loadFactor：已被忽略，取值为3/4
accessOrder：如果accessOrder为true，排序是根据最近最少使用算法，如果accessOrder为false，排序是基于插入顺序
@Override void init() {
header = new LinkedEntry<K, V>();
}
初始化LinkedEntry，其中包含双向链表中的next和previous的初始化
put方法
/**
* Caches {@code value} for {@code key}. The value is moved to the head of * the queue.
*
* @return the previous value mapped by {@code key}.
*/
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;
}
首先不允许键值为空，然后是线程安全，put的次数加一，size增加，以键值对的形式存入LinkedHashMap，如果之前已经存在了这个键值对，size减少成原来的大小，如果容量超过maxsize，将会删除最近很少访问的entry
@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是否为空，如果不为空，获取hash值和table，两个值与运算，如果key值和hash值都相同，修改value值，返回旧的value值；
如果为空，执行putValueForNullKey方法，在putValueForNullKey方法中
private V putValueForNullKey(V value) {
HashMapEntry<K, V> entry = entryForNullKey;
if (entry == null) {
addNewEntryForNullKey(value);
size++;
modCount++;
return null;
} else {
preModify(entry);
V oldValue = entry.value;
entry.value = value;
return oldValue;
}
}
判断entryForNullKey是否为空，如果为空，创建一个新的Entry，返回null，不为空，返回之前的value值
put方法有一个很关键的地方超过最大值是会删除最近最少访问的
trimToSize方法
首先线程安全，检查当前大小是否大于最大值，如果大于最大值，从LinkedHashMap中去除最近最少（循环删除链表首部元素）被访问的元素，获得键值，删除知道size<= maxSize, 跳出循环
/**
* Remove the eldest entries until the total of remaining entries is at or * below the requested size.
*
* @param maxSize the maximum size of the cache before returning. May be -1
* to evict even 0-sized elements.
*/
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);
}
}
get方法
首先key不能为空，线程安全，根据key，从LinkedHashMap中获得value，不为空的话返回，为空的话，创建一个key，创建失败返回null，创建成功，在LinkedHashMap中创建键值对，存在就覆盖，不存在size增加，返回value值
/**
* Returns the value for {@code key} if it exists in the cache or can be
* created by {@code #create}. If a value was returned, it is moved to the
* head of the queue. This returns null if a value is not cached and cannot * be created.
*/
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;
}
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;
}
}
LinkedHashMap get方法
key为null，根据entryForNullKey，如果为空直接返回null.
获得key对应的hash值，如果key和hash值都相同，accessOrder为false的话直接返回value值，accessOrder为true的话走makeTail方法，然后返回value值
@Override
public V get(Object key) {
/*
* This method is overridden to eliminate the need for a polymorphic
* invocation in superclass at the expense of code duplication.
*/
if (key == null) {
HashMapEntry<K, V> e = entryForNullKey;
if (e == null)
return null;
if (accessOrder)
makeTail((LinkedEntry<K, V>) e);
return e.value;
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)]; e != null; e = e.next) {
K eKey = e.key;
if (eKey == key || (e.hash == hash && key.equals(eKey))) {
if (accessOrder)
makeTail((LinkedEntry<K, V>) e);
return e.value;
}
}
return null;
}
makeTail方法
重新连接给定条目列表的尾部，在访问排序下，当一个预知的条目是通过调用Map.get 或者 通过Map.put方法修改时这个方法会被调用
这个方法主要是将访问的e，通过操作双向链表，将e放入链表的头部，实现排序
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++;
}
注：本文源码来自api 23
网友评论