LRUCache最最zhui易懂的解析，你还不来看看？

编程入门行业动态更新时间:2024-10-23 19:23:23

LRUCache最最zhui易懂的解析，你还不<a href=https://www.elefans.com/category/jswz/34/1757742.html style= 来看看？"/>

LRUCache最最zhui易懂的解析，你还不来看看？

最近在研究图片加载框架Glide，里面的代码真是非常复杂，它包括了网络请求，图片缓存、异步回调，线程池还有对图片的处理等等的内容，其中图片缓存机制用到了LRUCache和弱引用结合的方式来构建。

LRU算法大家都知道吧，它会丢弃最近，最少使用的项目，从而保留使用频率高的项目，达到一定的使用优化效果。那么LRUCache，因为其特性，特别适合在安卓中来决策图片的缓存策略，避免缓存太多不需要使用的图片，从而导致的OOM。

在此之前我对LRUCache只有大概的了解，知道其特性，但其内部原理我却没有深入了解过，所以今天就让我们好好看看LRUCache内部是怎么处理的。

自Android 3.1开始，LruCache就被引入作为android support包下的一部分，所以我们直接在Andriod Studio下全局搜索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);
}

传入的参数很简单，只需要传入一个maxSize，这个maxSize，默认情况下代表这个cache的能够存储的最大条目数，如果你重写了这个类的**sizeOf()**方法，那么这个maxSize就代表cache能够存储的最大容量。关于这点，源码分析的后面也能从代码中看出。

接着就是初始化一个LinkedHashMap，设置初始容量为0，容差因子为0.75，并以访问顺序(访问过该元素过后，元素就会被添加到链表的后面)存储项目，这个hashmap就是用来存储缓存数据的。关于LinkedHashMap的用法和内部知识就不在这里展开了，本文主要以介绍LRUCache为主。

因为LruCache是个数据存储类，接下来看看它的数据来源。

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

数据进来后，先计算新数据的大小，并计入size，然后再把数据插入到linkedHashMap里面，调用map.put(key, val)把数据插入，如果该key在map中已有旧值，就把旧值传给previous。

判断previous是否为空，如果不为空，则需要从size中减去旧值的所占的容量。

这里的容量怎么计算呢？看看safeSizeOf()方法

int safeSizeOf(K key, V value)

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

其内部也很简单，只是调用了sizeOf()就返回了，这个sizeOf()就是我们开头提到的，其返回值会改变maxSize的意义。看看它在LruCache中的默认实现

int sizeOf(K key, V value)

protected int sizeOf(K key, V value) {return 1;
}

可以看到，它默认直接返回了1，也就是说，当我们计算数据的容量时，默认都是返回1个容量，如果你刚开始设置的maxSize是10的话，那么每次新增一个数据，size就会加一，如果size大于了maxSize，就会把linkedHashMap头部，也就是最老的数据“踢”出去，“踢出”的操作后面可以看到。这里我们先接着往下看。

如果该key在map中已有旧值，调用entryRemoved()，这是一个回调方法，在map中元素被踢出或被替换时就会被调用，LruCache中默认是空实现的，我们可以通过重写该方法做一些特殊处理。

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

protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {}

在对LruCache进行put、get、remove、trimToSize操作时都会调用这个方法，方法对应的参数意义：

evicted: 元素是否是被踢出的，例如新元素进来，但已达最大容量maxSize，这时候需要把最老的元素踢出去。
key: map的索引key
oldValue：key对应的旧值
newValue: key对应的新值（如果有的话，例如remove()是没有新值的）

entryRemoved()过后，检查一遍put新值后，size是否超出maxSize，调用trimToSize()，来看看它的内部实现

void trimToSize(int maxSize)

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

首先是个无限遍历，每次调用map.eldest()，返回map中的最老的节点进行remove，Map.eldest()方法是安卓中为LruCache新加的，可以看看它的源码注释

// Android-added: eldest(), for internal use in LRU caches
/*** Returns the eldest entry in the map, or {@code null} if the map is empty.* @hide*/
public Map.Entry<K, V> eldest() {return head;
}

将最老的元素remove后，还需要重新计算当前的size，safeSizeOf()方法上面我们已经看过了，内部只调用了一个sizeOf()，返回一个item所需要占用的容量。

最后调用entryRemoved()回调。

至此put()流程走完，简单画个流程图，走着：

LruCache经过put操作后，cache中已有数据，接下来看看它的get操作。

V get(K key)

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++;}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 putmap.put(key, mapValue);} else {size += safeSizeOf(key, createdValue);}}if (mapValue != null) {entryRemoved(false, key, createdValue, mapValue);return mapValue;} else {trimToSize(maxSize);return createdValue;}
}

虽然里面有两个synchronized，但逻辑也不复杂，我们一点一点看。

首先调用map.get(key)，尝试获取map中的旧值。如果map中存储了该key的值，直接返回旧值。

如果没有，调用create(key)，尝试为这个key，创建一个值，这个create()方法默认也是空实现的，有需要我们可以重写该方法。

如果createdValue成功创建，不为空，则重新调用map.put(key, createdValue)。

因为synchronized的原因，在进入第二个sync之前，如果有其他线程B获取了对象锁，调用完put()方法后释放，然后当前线程A再获取锁，这时候map中对应的key就可能有值了，如果有值的话就会返回给mapValue。此时LruCache认为这时候对map的操作有冲突，是脏数据，以put的值为准，进行回滚操作，把mapValue的值插入进去。

否则createdValue被put成功，计算size。

最后在根据mapValue，来判断是进行entryRemoved()还是trimToSize()。

同样，我们简单画个图总结下。

cache数据的来源和获取我们都看了，接下来看看cache的remove方法。

V remove(K 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);}return previous;
}

remove的实现还是比较简单的，我们简单过一遍就好了。

显示从map中去掉该key对应的value，同时从size中减掉该value所占的容量，最后调用entryRemoved()回调。

因为这里并没有新值插入，也并不是因为控件不足而进行的“踢出”操作，所以entryRemoved的第一个参数evict传入false，最后的newValue为null。

接下来我们看看LruCache中其他比较好玩的方法，evictAll()和resize()

void evictAll()

/*** Clear the cache, calling {@link #entryRemoved} on each removed entry.*/
public final void evictAll() {trimToSize(-1); // -1 will evict 0-sized elements
}

void resize()

public void resize(int maxSize) {if (maxSize <= 0) {throw new IllegalArgumentException("maxSize <= 0");}synchronized (this) {this.maxSize = maxSize;}trimToSize(maxSize);
}

这两个方法内部都是通过trimToSize()来实现的，只是传入的参数值有所不同，

我们回顾一下trimToSize()的内部实现，摘取下面一段代码：

public void trimToSize(int maxSize) {while (true) {...synchronized (this) {...if (size <= maxSize) {break;}...size -= safeSizeOf(key, value);}}
}

在文章的开头我们提到，如果我们重写了sizeOf()方法，会给maxSize赋予不同的意义。

默认情况下代表这个cache的能够存储的最大条目数，如果你重写了这个类的**sizeOf()**方法，那么这个maxSize就代表cache能够存储的最大容量。

现在想想是不是这样？如果默认实现sizeOf返回1，那么我们每经历一个while循环，就会让size减1，就相当于是减掉了一个数量的item，那么此时maxSize代表的可不就是当前cache的item数量了嘛？

而如果我们重写了sizeOf()，返回一个特定的数值(假如是15)，而我们在初始化时设置的maxSize等于100，那么此时maxSize就代表了这个cache整体的容量了，最多也只能缓存6个item。

好了，文章读到现在大家对LRUCache内部实现应该有个直观的认识了，我要接着去看Glide的源码了。。