LruCache概要
LRU (Least Recently Used) 即最近最少使用算法。在Android开发中，LruCache是基于LRU算法实现的。当缓存空间使用完的情况下，最久没被使用的对象会被清除出缓存。
LruCache常用的场景是做图片内存缓存，电商类APP经常会用到图片，当我们对图片资源做了内存缓存，不仅可以增强用户体验，而且可以减少图片网络请求，减少用户流量耗费。
LruCache是一个内存层面的缓存，如果想要进行本地磁盘缓存，推荐使用DiskLruCache，虽然没包含在官方API中，但是官方推荐我们使用。
使用方法
LruCache的使用方法如下：
public class BitmapLruCache extends LruCache<String, Bitmap> {
//设置缓存大小，建议当前应用可用最大内存的八分之一 即(int) (Runtime.getRuntime().maxMemory() / 1024 / 8)
public BitmapLruCache(int size) {
super(size);
}
//计算当前节点的内存大小 这个方法需要重写 不然返回1
@Override
protected int sizeOf(String key, Bitmap value) {
return value.getByteCount() / 1024;
}
//当节点移除时该方法会回调，可根据需求来决定是否重写该方法
@Override
protected void entryRemoved(boolean evicted, String key, Bitmap oldValue, Bitmap
newValue) {
super.entryRemoved(evicted, key, oldValue, newValue);
}
}
存放图片
//设置缓存大小，建议当前应用可用最大内存的八分之一 即(int) (Runtime.getRuntime().maxMemory() / 1024 / 8)
int size = (int) (Runtime.getRuntime().maxMemory() / 1024 / 8);
final BitmapLruCache bitmapLruCache = new BitmapLruCache(size);
Bitmap bitmap = BitmapFactory.decodeResource(getResources(), R.mipmap.girl);
//存放图片
bitmapLruCache.put("girl", bitmap);
//获取图片
final Bitmap girl = bitmapLruCache.get("girl");
mImageView.setOnClickListener(new View.OnClickListener() {
@Override
public void onClick(View v) {
mImageView.setImageBitmap(girl);
}
});
源码分析
1.LruCache的实现原理
LruCache的核心思想很好理解，就是要维护一个缓存对象列表，其中对象列表的排列方式是按照访问顺序实现的，即一直没访问的对象，将放在队尾，即将被淘汰。而最近访问的对象将放在队头，最后被淘汰。
如下图所示：
image
那么这个队列到底是由谁来维护的，前面已经介绍了是由LinkedHashMap来维护。
而LinkedHashMap是由数组+双向链表的数据结构来实现的。其中双向链表的结构可以实现访问顺序和插入顺序，使得LinkedHashMap中的<key,value>对按照一定顺序排列起来。
2.LruCache构造方法
public LruCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
} else {
this.maxSize = maxSize;
//我们发现实现用的是LinkedHashMap 注意最后的true 表示LinkedHashMap 中accessOrder设置为true
//其中accessOrder设置为true则为访问顺序，为false，则为插入顺序。
this.map = new LinkedHashMap(0, 0.75F, true);
}
}
3.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) {//不允许key 和 value 为 null
throw new NullPointerException("key == null || value == null");
}
V previous;
synchronized (this) {//多线程安全
putCount++;
//size 表示当期使用的缓存大小 safeSizeOf 会掉用sizeOf方法 用于计算当前节点的大小
size += safeSizeOf(key, value);
// 将新节点放入LinkedHashMap 如果有返回值，表示map集合中存在旧值
previous = map.put(key, value);
if (previous != null) {//存在旧值 在移除旧值后 更新缓存大小
size -= safeSizeOf(key, previous);
}
}
//有旧值移除 回调entryRemoved
if (previous != null) {
entryRemoved(false, key, previous, value);
}
trimToSize(maxSize);//整理每个节点 主要判断当前size是否超过maxSize
return previous;
}
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!");
}
//size <= maxSize 停止遍历列表，不然继续遍历列表修剪节点。
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);
}
}
看下safeSizeOf 和 entryRemoved方法
private int safeSizeOf(K key, V value) {
int result = sizeOf(key, value);//调用了sizeOf方法
if (result < 0) {
throw new IllegalStateException("Negative size: " + key + "=" + value);
}
return result;
}
protected int sizeOf(K key, V value) {//sizeOf的默认实现
return 1;
}
//entryRemoved的默认实现
protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {}
4.get方法
/**
* 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) {//key不能为 null
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {//线程同步
mapValue = map.get(key);//调用LinkedHashMap 的get方法
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;
}
}
protected V create(K key) {//创建方法默认空实现 可根据需求决定是否重写该方法
return null;
}
5.remove方法
/**
* Removes the entry for {@code key} if it exists.
*
* @return the previous value mapped by {@code key}.
*/
public final V remove(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V previous;
synchronized (this) {//线程同步
previous = map.remove(key);//获得移除的节点
if (previous != null) {//当节点不为空 更新缓存大小
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {
//当节点移除时回调entryRemoved方法
entryRemoved(false, key, previous, null);
}
return previous;
}
通过上述几个方法代码，我们知道LruCache如何控制及更新缓存的大小的，主要是在线程同步块里对size字段进行更新,然后根据size字段和maxSize字段的大小关系来修剪节点。但如何做到最近最少使用呢？ 没错，LinkedHashMap 帮我们做到最近最少使用的排序。
让我们看下LinkedHashMap 如何实现的，在此过程我们不分析HashMap的实现，只关心LinkedHashMap 的一些实现，HashMap的实现有机会给大家分享。
//继承了HashMap 说明LinkedHashMap 的查找效率依然是O(1)
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{
//重新定义了节点 用于实现链表
private transient LinkedHashMapEntry<K,V> header;
private static class LinkedHashMapEntry<K,V> extends HashMapEntry<K,V> {
LinkedHashMapEntry<K,V> before, after;
//此处省略几个字
}
//此处省略几个字
}
LinkedHashMap类并没有重写put方法，当我们调用put方法时，调用的依然是HashMap的put方法。我们看下HashMap的put方法：
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
//HashMap的特点 可以放key为null的值
return putForNullKey(value);
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
int i = indexFor(hash, table.length);
for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;//存在旧值 就把旧值移除掉 并返回旧值 由此可知 当我们更换缓存中已存在的值时，并不会影响它在链表中位置
}
}
modCount++;
addEntry(hash, key, value, i);//LinkedHashMap 重写了该方法
return null;
}
//LinkedHashMap中实现
/**
* This override alters behavior of superclass put method. It causes newly
* allocated entry to get inserted at the end of the linked list and
* removes the eldest entry if appropriate.
*/
//将节点放在链表的末尾
void addEntry(int hash, K key, V value, int bucketIndex) {
// Previous Android releases called removeEldestEntry() before actually
// inserting a value but after increasing the size.
// The RI is documented to call it afterwards.
// **** THIS CHANGE WILL BE REVERTED IN A FUTURE ANDROID RELEASE ****
// Remove eldest entry if instructed
LinkedHashMapEntry<K,V> eldest = header.after;
if (eldest != header) {
boolean removeEldest;
size++;
try {
removeEldest = removeEldestEntry(eldest);//hook 默认为false 让用户重写removeEldestEntry 来决定是否移除eldest节点
} finally {
size--;
}
if (removeEldest) {
removeEntryForKey(eldest.key);
}
}
super.addEntry(hash, key, value, bucketIndex);//往下瞅 有惊喜
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
//HashMap中addEntry：
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
//LinkedHashMap重写了该方法
createEntry(hash, key, value, bucketIndex);
}
//LinkedHashMap中
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMapEntry<K,V> old = table[bucketIndex];
LinkedHashMapEntry<K,V> e = new LinkedHashMapEntry<>(hash, key, value, old);
table[bucketIndex] = e;
//把该节点插入到链表头部 最近使用访问到的在最前边原则
e.addBefore(header);
size++;
}
LinkedHashMap中重写了get方法，实现如下;
public V get(Object key) {
//使用HashMap的getEntry方法，验证了我们所说的查询效率为O(1)
LinkedHashMapEntry<K,V> e = (LinkedHashMapEntry<K,V>)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);//在找到节点后调用节点recordAccess方法 往下看
return e.value;
}
//LinkedHashMapEntry
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {//accessOrder该值默认为false 但是 在LruCache中设置为true
lm.modCount++;
remove();//该方法将本身节点移除链表
addBefore(lm.header);//将自己添加到节点尾部 保证最近使用的节点位于链表末尾
}
}
LinkedHashMap的并没有重写HashMap的remove方法，依然是调用HashMap的remove方法，代码如下：
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.getValue());
}
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
int i = indexFor(hash, table.length);
HashMapEntry<K,V> prev = table[i];
HashMapEntry<K,V> e = prev;
while (e != null) {
HashMapEntry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
//注意这一行 开头我们说过 LinkedHashMap用的节点是自己定义的LinkedHashMapEntry ，继承自HashMapEntry
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
//LinkedHashMapEntry 中recordRemoval
void recordRemoval(HashMap<K,V> m) {
remove();
}
private void remove() {//更改指针来移除自身
before.after = after;
after.before = before;
}
三、总结
读完源码我们可以总结出：
- LruCache是继承自HashMap，它的查找效率依然是O(1);
- LruCache内部又维护了一个双向链表结构，当我们有访问操作时候，被访问节点会移到链表结尾；
- 在Lrucache的put、get和remove方法中，对集合操作时使用了synchronized关键字，来保证线程安全；
四、Demo验证
1.首先创建LRUCache，我们设置其大小为4，因为默认每个Item大小为1，当我们执行放入操作时，最后放入的数据会在链表最后边，打印结果如下：
private void test() {
LruCache<String,String> lruCache = new LruCache<>(4);
lruCache.put("a","这是第1个放进去的值");
lruCache.put("b","这是第2个放进去的值");
lruCache.put("c","这是第3个放进去的值");
lruCache.put("d","这是第4个放进去的值");
print(lruCache);
}
private void print(LruCache<String,String> lruCache){
Map map =lruCache.snapshot();
Iterator<String> iterator = map.keySet().iterator();
String key;
while (iterator.hasNext()){
key = iterator.next();
Log.i("LruCacheItem","key ="+key+" value ="+map.get(key));
}
}
测试截图如下：
image
2.当我们访问链表中一个元素时候，该元素会移到队列末尾，测试如下;
private void test() {
LruCache<String,String> lruCache = new LruCache<>(4);
lruCache.put("a","这是第1个放进去的值");
lruCache.put("b","这是第2个放进去的值");
lruCache.put("c","这是第3个放进去的值");
lruCache.put("d","这是第4个放进去的值");
lruCache.get("c");
print(lruCache);
}
测试截图如下：
image
我们发现第一个元素被移除。
我们会发现key为c的item移到了队列末尾。
3.当我们放入元素超过总的大小时，队列首部元素会被移除：
private void test() {
LruCache<String,String> lruCache = new LruCache<>(4);
lruCache.put("a","这是第1个放进去的值");
lruCache.put("b","这是第2个放进去的值");
lruCache.put("c","这是第3个放进去的值");
lruCache.put("d","这是第4个放进去的值");
lruCache.get("c");
lruCache.put("e","这是第5个放进去的值");
print(lruCache);
}
测试截图如下：
image
我们发现超出总大小后，队列首部元素被移除。
4.移除相对简单，不会改变队列里元素的相对顺序，只是该元素出队列而已，测试如下：
private void test() {
LruCache<String,String> lruCache = new LruCache<>(4);
lruCache.put("a","这是第1个放进去的值");
lruCache.put("b","这是第2个放进去的值");
lruCache.put("c","这是第3个放进去的值");
lruCache.put("d","这是第4个放进去的值");
lruCache.get("c");
lruCache.put("e","这是第5个放进去的值");
lruCache.remove("c");
print(lruCache);
}
key为c的元素被移除链表，结果如下：
image
网友评论