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);
- }
- }
往缓存中放一张图片:
- mLruCache.put(name, bitmap);
获取一张图片:
- mLruCache.get(name);
删除一张图片:
- mLruCache.remove(name);
- /**
- * @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 注意最后的true 表示LinkedHashMap 中accessOrder设置为true
- }
- /**
- * 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(key, value); //size 表示当期使用的缓存大小 safeSizeOf 会掉用sizeOf方法 用于计算当前节点的大小
- previous = map.put(key, value); // 将新节点放入LinkedHashMap 如果有返回值,表示map集合中存在旧值
- if (previous != null) { //存在旧值 在移除旧值后 更新缓存大小
- size -= safeSizeOf(key, previous);
- }
- }
- if (previous != null) { //有旧值移除 回调entryRemoved
- 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!");
- }
- if (size <= maxSize || map.isEmpty()) { //size <= maxSize 停止遍历列表,不然继续遍历列表修剪节点。
- 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;
- }
- protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {} //entryRemoved的默认实现
- /**
- * 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;
- }
- /**
- * 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(false, key, previous, null); //当节点移除时回调entryRemoved方法
- }
- 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) return putForNullKey(value); //HashMap的特点 可以放key为null的值
- 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中实现
- 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);
- }
- createEntry(hash, key, value, bucketIndex); //LinkedHashMap重写了该方法
- }
- //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) {
- LinkedHashMapEntry < K,
- V > e = (LinkedHashMapEntry < K, V > ) getEntry(key); //使用HashMap的getEntry方法,验证了我们所说的查询效率为O(1)
- 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;
- e.recordRemoval(this); //注意这一行 开头我们说过 LinkedHashMap用的节点是自己定义的LinkedHashMapEntry ,继承自HashMapEntry
- 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;
- }
OK,关于LruCache源码实现层面的就分析完了,感谢你的耐心阅读。如果觉得我的内容对你有帮助,给个赞哦。
来源: https://juejin.im/entry/5a20c1026fb9a0452b490707