浅谈LruCache源码实现

LruCache是Android在3.1版本中新增的一个缓冲类,在低于3.1版本中可以使用support V4包中的LruCache。LruCache是基于LRU缓存算法实现的,LRU(Least Recently Used)缓存算法即最近最少使用,它的核心思想是当缓存满时,会优先淘汰那些近期最少使用的缓存对象。

LRU算法最早接触还是在学习操作系统时接触的,在本文中并不会详细介绍该算法的实现,主要还是为了查看一下LruCache源码实现。LruCache本身并没有实现LRU算法,真正实现算法的其实是一个集合类LinkedHashMap,该集合类有一个Linked前缀,从这里可以看出该集合类是基于链表实现的有序的集合。为了查看LruCache的实现机制,这里我们首先看一下LinkedHashMap的使用。

Map map = new LinkedHashMap<>();
map.put(1, "aaa");
map.put(2, "bbb");
map.put(3, "ccc");
map.put(4, "ddd");
map.put(5, "eee");
System.out.println(map.toString());
//{1=aaa, 2=bbb, 3=ccc, 4=ddd, 5=eee}

map.get(1);
map.get(2);
map.put(6, "fff");
System.out.println(map.toString());
//{1=aaa, 2=bbb, 3=ccc, 4=ddd, 5=eee, 6=fff}

从输出结果可以看出LinkedHashMap确实是一个有序的Map,而且Map中数据的顺序正是添加的顺序,其实LinkedHashMap还有一个三个参数的构造方法,其中有一个参数accessOrder,该参数用于标识LinkedHashMap中数据的排序方式,在默认构造方法中accessOrder为false,表示在LinkedHashMap中的数据的顺序是根据插入顺序排列。当accessOrder为true时,LinkedHashMap中数据顺序是以访问顺序排序的,当然了插入顺序仍然是有序的,只不过如果我们使用get()方法访问了其中一个数据,该位置的数据就会被放置在尾部,即意味着只要访问了某个数据就会影响该数据的顺序位置。当我们将accessOrder设置为true时,继续输出Map中的数据如下:

Map map = new LinkedHashMap<>(0,0.75f,true);
//{1=aaa, 2=bbb, 3=ccc, 4=ddd, 5=eee}
//{3=ccc, 4=ddd, 5=eee, 1=aaa, 2=bbb, 6=fff}

这种访问排序实现机制类似我们的LRU算法,LRU算法表示如下图:

LruCache类中就是维护了一个LinkedHashMap,然后LruCache再设置一个总大小的最大值maxSize,当LinkedHashMap中的元素的总大小大于maxSize,根据LRU算法移除最近很少使用的元素,当然了LruCache中必须给出每一个元素大小的计算方式,每次放入一个元素时实时计算当前LinkedHashMap已经包含的元素的总大小。

如下是Android在使用LruCache处理Bitmap时最常用的使用方式。

int memCacheSize=20*1024*1024;
LruCache mMemoryCache = new LruCache(memCacheSize) {

		//LruCache移除元素时回调方法
		@Override
		protected void entryRemoved(boolean evicted, String key,
				Bitmap oldValue, Bitmap newValue) {
			//...
		}

		@Override
		protected int sizeOf(String key, Bitmap value) {
			final int bitmapSize = getBitmapSize(value) / 1024 / 1024;
			return bitmapSize == 0 ? 1 : bitmapSize;
		}
	};
}
public static int getBitmapSize(BitmapDrawable value) {
	Bitmap bitmap = value.getBitmap();

	//Android4.4及其以上
	if (Utils.hasKitKat()) {
		return bitmap.getAllocationByteCount();
	}

	//Android3.1及其以上
	if (Utils.hasHoneycombMR1()) {
		return bitmap.getByteCount();
	}

	return bitmap.getRowBytes() * bitmap.getHeight();
}

源码分析

构造方法

LruCache只有一个构造方法如下:

public LruCache(int maxSize) {
	if (maxSize <= 0) {
		throw new IllegalArgumentException("maxSize <= 0");
	}
	this.maxSize = maxSize;
	this.map = new LinkedHashMap(0, 0.75f, true);
}

构造方法要求传入一个int类型的入参,该参数就是LruCache设置的需要缓存的元素的总大小,唯一需要注意的就是入参maxSize的大小的单位需要跟sizeOf中设置的单位一致,然后就是对LinkedHashMap进行创建。LinkedHashMap使用的是三个参数的构造方法,三个参数分别为initialCapacity、loadFactor和accessOrder。其中initialCapacity是初始容量;loadFactor是负载因子,什么是负载因子呢,假设LinkedHashMap的容量是100,当放入的元素个数达到75个时,LinkedHashMap就会自动扩容;accessOrder是定义LinkedHashMap的排序方式,可以参看上文的介绍。构造方法很简单,一个入参以及必要的参数校验,一个对LinkedHashMap的初始化。

V get(K key)方法

根据key查询缓存,如果存在于缓存或者被create方法创建了。

如果值返回了,那么它将被移动到双向循环链表的的尾部。

如果如果没有缓存的值,则返回null。

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++;
	}

	/*
	 * 尝试创建一个值,这可能需要很长时间,并且Map可能在create()返回的值时有所不同。
	 * 如果在create()执行的时候,一个冲突的值被添加到Map,我们在Map中删除这个值,释放被创造的值。
	 */
	V createdValue = create(key);
	if (createdValue == null) {
		return null;
	}
	/*
	 * 一般情况下走不到这里,否则应该是重写了create()方法并且返回了一个非null的值
	 * create()方法默认返回null
	 */
	synchronized (this) {
		createCount++;
		//将自定义create创建的值,放入LinkedHashMap中,如果key已经存在,会返回 之前相同key 的值
		mapValue = map.put(key, createdValue);

		if (mapValue != null) {
			//有冲突所以撤销刚才的操作将之前相同key的值重新放回去
			map.put(key, mapValue);
		} else {
			//没有冲突则计算现有元素的总大小值
			size += safeSizeOf(key, createdValue);
		}
	}
	//如果上面判断出了将要放入的值发生冲突
	if (mapValue != null) {
		//刚才create的值被删除了,原来的之前相同key 
		//的值被重新添加回去了告诉自定义的entryRemoved方法
		entryRemoved(false, key, createdValue, mapValue);
		return mapValue;
	} else {
		//上面进行了size += 操作所以这里要重整计算大小
		trimToSize(maxSize);
		return createdValue;
	}
}

V put(K key, V value)

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;
}

int safeSizeOf(K key, V value)

该方法用于计算每次放入key值对应的size大小,该方法是一个私有方法,方法体中调用了sizeOf()方法,但是sizeOf()方法是暴露出来的,系统默认返回值是1,sizeOf()方法方法一般需要开发人员自己重写,重写safeSizeOf()方法目的就是为了计算LruCache中加入的每一个元素大小的逻辑,这样就可以跟构造方法中maxSize做比较,如果一旦超过限制在调用trimToSize()方法时就会移除最近很少使用的某个元素。

private int safeSizeOf(K key, V value) {
	int result = sizeOf(key, value);
	if (result < 0) {
		throw new IllegalStateException("Negative size: " + key + "=" + value);
	}
	return result;
}
protected int sizeOf(K key, V value) {
	return 1;
}

void trimToSize(int maxSize)

trimToSize()方法用于来判断缓存是否已满,如果满了就要删除近期最少使用的算法。方法中设置了一个死循环,如果当前元素的总大小小于设置的总大小,则会直接退出循环。否则会移除最近很少使用的元素,直到现有元素大小小于设置的总大小跳出循环。每次有一个元素移除调用一次entryRemoved()方法。trimToSize()方法也可以用于清除LruCache中内存缓存,直接trimToSize(-1)即可。

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 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);
	}
}

entryRemoved(boolean evicted, K key, V oldValue, V newValue)

该方法只有在现有元素容量大于设置总容量移除最近很少使用的元素时evicted值为true,在put或者remove的时候都是false。该方法虽然也暴露给了开发者,但是却很少使用。在设计图片缓存框架时,Google官方给的demo示例倒是使用了此方法,当元素被移除时,又将移除的元素重新放入了一个软引用中。

一般entryRemoved调用常见如下:

  • put发生key冲突时被调用,evicted=false,key=此次put的key,oldValue=被覆盖的冲突 value,newValue=此次 put的value。
  • remove的时候,存在对应key,并且被成功删除后被调用。evicted=false,key=此次 put的 key,oldValue=此次删除的 value,newValue=null(此次没有冲突,只是 remove)。
  • trimToSize的时候,删除的最近很少使用的数据移除。evicted=true,key=移除元素的key,oldValue=移除元素的 value,newValue=null(此次没有冲突,只是 remove)。

其它

LruCache是线程安全的,比较常用的几个方法如get()、put()等方法都使用了synchronized锁,另外entryRemoved()方法虽然没有使用锁,但是由于该方法的参数都是局部变量,位于Java虚拟机栈中,本身就是线程私有的,所以也是线程安全的。

maxSize()和 sizeOf()方法的覆写是务必注意使用相同的单位,如maxSize是5MB,自定义的sizeOf计算每个数据大小的时候必须能算出与MB之间有联系的单位。

评论

您确定要删除吗?删除之后不可恢复