lru缓存

这篇帖子先分析内存缓存是如何实现的。好吧开始进入正题。

　　BitmapUtils内存缓存的核心类LruMemoryCache，LruMemoryCache代码和v4包的LruCache一样，只是加了一个存储超期的处理，这里分析LruCache源码。LRU即Least Recently Used，近期最少使用算法。也就是当内存缓存达到设定的最大值时将内存缓存中近期最少使用的对象移除，有效的避免了OOM的出现。

​ 讲到LruCache不得不提一下LinkedHashMap，因为LruCache中Lru算法的实现就是通过LinkedHashMap来实现的。LinkedHashMap继承于HashMap，它使用了一个双向链表来存储Map中的Entry顺序关系，这种顺序有两种，一种是LRU顺序，一种是插入顺序，这可以由其构造函数public LinkedHashMap(int initialCapacity,float loadFactor, boolean accessOrder)指定。所以，对于get、put、remove等操作，LinkedHashMap除了要做HashMap做的事情，还做些调整Entry顺序链表的工作。LruCache中将LinkedHashMap的顺序设置为LRU顺序来实现LRU缓存，每次调用get(也就是从内存缓存中取图片)，则将该对象移到链表的尾端。调用put插入新的对象也是存储在链表尾端，这样当内存缓存达到设定的最大值时，将链表头部的对象（近期最少用到的）移除。关于LinkedHashMap详解请前往http://www.cnblogs.com/children/archive/2012/10/02/2710624.html。

​ 下面看下LruCache的源码，我都注释的很详细了。

  1 /*
  2  * Copyright (C) 2011 The Android Open Source Project
  3  *
  4  * Licensed under the Apache License, Version 2.0 (the "License");
  5  * you may not use this file except in compliance with the License.
  6  * You may obtain a copy of the License at
  7  *
  8  *      http://www.apache.org/licenses/LICENSE-2.0
  9  *
 10  * Unless required by applicable law or agreed to in writing, software
 11  * distributed under the License is distributed on an "AS IS" BASIS,
 12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 13  * See the License for the specific language governing permissions and
 14  * limitations under the License.
 15  */
 16 
 17 package android.support.v4.util;
 18 
 19 import java.util.LinkedHashMap;
 20 import java.util.Map;
 21 
 22 /**
 23  * Static library version of {@link android.util.LruCache}. Used to write apps
 24  * that run on API levels prior to 12. When running on API level 12 or above,
 25  * this implementation is still used; it does not try to switch to the
 26  * framework's implementation. See the framework SDK documentation for a class
 27  * overview.
 28  */
 29 public class LruCache<K, V> {
 30     private final LinkedHashMap<K, V> map;
 31 
 32     /** Size of this cache in units. Not necessarily the number of elements. */
 33     private int size;    //当前cache的大小
 34     private int maxSize; //cache最大大小
 35 
 36     private int putCount;       //put的次数
 37     private int createCount;    //create的次数
 38     private int evictionCount;  //回收的次数
 39     private int hitCount;       //命中的次数
 40     private int missCount;      //未命中次数
 41 
 42     /**
 43      * @param maxSize for caches that do not override {@link #sizeOf}, this is
 44      *     the maximum number of entries in the cache. For all other caches,
 45      *     this is the maximum sum of the sizes of the entries in this cache.
 46      */
 47     public LruCache(int maxSize) {
 48         if (maxSize <= 0) {
 49             throw new IllegalArgumentException("maxSize <= 0");
 50         }
 51         this.maxSize = maxSize;
 52         //将LinkedHashMap的accessOrder设置为true来实现LRU
 53         this.map = new LinkedHashMap<K, V>(0, 0.75f, true);  
 54     }
 55 
 56     /**
 57      * Returns the value for {@code key} if it exists in the cache or can be
 58      * created by {@code #create}. If a value was returned, it is moved to the
 59      * head of the queue. This returns null if a value is not cached and cannot
 60      * be created.
 61      * 通过key获取相应的item，或者创建返回相应的item。相应的item会移动到队列的尾部，
 62      * 如果item的value没有被cache或者不能被创建，则返回null。
 63      */
 64     public final V get(K key) {
 65         if (key == null) {
 66             throw new NullPointerException("key == null");
 67         }
 68 
 69         V mapValue;
 70         synchronized (this) {
 71             mapValue = map.get(key);
 72             if (mapValue != null) {
 73                 //mapValue不为空表示命中，hitCount+1并返回mapValue对象
 74                 hitCount++;
 75                 return mapValue;
 76             }
 77             missCount++;  //未命中
 78         }
 79 
 80         /*
 81          * Attempt to create a value. This may take a long time, and the map
 82          * may be different when create() returns. If a conflicting value was
 83          * added to the map while create() was working, we leave that value in
 84          * the map and release the created value.
 85          * 如果未命中，则试图创建一个对象，这里create方法返回null,并没有实现创建对象的方法
 86          * 如果需要事项创建对象的方法可以重写create方法。因为图片缓存时内存缓存没有命中会去
 87          * 文件缓存中去取或者从网络下载，所以并不需要创建。
 88          */
 89         V createdValue = create(key);
 90         if (createdValue == null) {
 91             return null;
 92         }
 93         //假如创建了新的对象，则继续往下执行
 94         synchronized (this) {
 95             createCount++;  
 96             //将createdValue加入到map中，并且将原来键为key的对象保存到mapValue
 97             mapValue = map.put(key, createdValue);   
 98             if (mapValue != null) {
 99                 // There was a conflict so undo that last put
100                 //如果mapValue不为空，则撤销上一步的put操作。
101                 map.put(key, mapValue);
102             } else {
103                 //加入新创建的对象之后需要重新计算size大小
104                 size += safeSizeOf(key, createdValue);
105             }
106         }
107 
108         if (mapValue != null) {
109             entryRemoved(false, key, createdValue, mapValue);
110             return mapValue;
111         } else {
112             //每次新加入对象都需要调用trimToSize方法看是否需要回收
113             trimToSize(maxSize);
114             return createdValue;
115         }
116     }
117 
118     /**
119      * Caches {@code value} for {@code key}. The value is moved to the head of
120      * the queue.
121      *
122      * @return the previous value mapped by {@code key}.
123      */
124     public final V put(K key, V value) {
125         if (key == null || value == null) {
126             throw new NullPointerException("key == null || value == null");
127         }
128 
129         V previous;
130         synchronized (this) {
131             putCount++;
132             size += safeSizeOf(key, value);  //size加上预put对象的大小
133             previous = map.put(key, value);
134             if (previous != null) {
135                 //如果之前存在键为key的对象，则size应该减去原来对象的大小
136                 size -= safeSizeOf(key, previous);
137             }
138         }
139 
140         if (previous != null) {
141             entryRemoved(false, key, previous, value);
142         }
143         //每次新加入对象都需要调用trimToSize方法看是否需要回收
144         trimToSize(maxSize);
145         return previous;
146     }
147 
148     /**
149      * @param maxSize the maximum size of the cache before returning. May be -1
150      *     to evict even 0-sized elements.
151      * 此方法根据maxSize来调整内存cache的大小，如果maxSize传入-1，则清空缓存中的所有对象
152      */
153     private void trimToSize(int maxSize) {
154         while (true) {
155             K key;
156             V value;
157             synchronized (this) {
158                 if (size < 0 || (map.isEmpty() && size != 0)) {
159                     throw new IllegalStateException(getClass().getName()
160                             + ".sizeOf() is reporting inconsistent results!");
161                 }
162                 //如果当前size小于maxSize或者map没有任何对象,则结束循环
163                 if (size <= maxSize || map.isEmpty()) {
164                     break;
165                 }
166                 //移除链表头部的元素，并进入下一次循环
167                 Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
168                 key = toEvict.getKey();
169                 value = toEvict.getValue();
170                 map.remove(key);
171                 size -= safeSizeOf(key, value);
172                 evictionCount++;  //回收次数+1
173             }
174 
175             entryRemoved(true, key, value, null);
176         }
177     }
178 
179     /**
180      * Removes the entry for {@code key} if it exists.
181      *
182      * @return the previous value mapped by {@code key}.
183      * 从内存缓存中根据key值移除某个对象并返回该对象
184      */
185     public final V remove(K key) {
186         if (key == null) {
187             throw new NullPointerException("key == null");
188         }
189 
190         V previous;
191         synchronized (this) {
192             previous = map.remove(key);
193             if (previous != null) {
194                 size -= safeSizeOf(key, previous);
195             }
196         }
197 
198         if (previous != null) {
199             entryRemoved(false, key, previous, null);
200         }
201 
202         return previous;
203     }
204 
205     /**
206      * Called for entries that have been evicted or removed. This method is
207      * invoked when a value is evicted to make space, removed by a call to
208      * {@link #remove}, or replaced by a call to {@link #put}. The default
209      * implementation does nothing.
210      *
211      * <p>The method is called without synchronization: other threads may
212      * access the cache while this method is executing.
213      *
214      * @param evicted true if the entry is being removed to make space, false
215      *     if the removal was caused by a {@link #put} or {@link #remove}.
216      * @param newValue the new value for {@code key}, if it exists. If non-null,
217      *     this removal was caused by a {@link #put}. Otherwise it was caused by
218      *     an eviction or a {@link #remove}.
219      */
220     protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {}
221 
222     /**
223      * Called after a cache miss to compute a value for the corresponding key.
224      * Returns the computed value or null if no value can be computed. The
225      * default implementation returns null.
226      *
227      * <p>The method is called without synchronization: other threads may
228      * access the cache while this method is executing.
229      *
230      * <p>If a value for {@code key} exists in the cache when this method
231      * returns, the created value will be released with {@link #entryRemoved}
232      * and discarded. This can occur when multiple threads request the same key
233      * at the same time (causing multiple values to be created), or when one
234      * thread calls {@link #put} while another is creating a value for the same
235      * key.
236      */
237     protected V create(K key) {
238         return null;
239     }
240 
241     private int safeSizeOf(K key, V value) {
242         int result = sizeOf(key, value);
243         if (result < 0) {
244             throw new IllegalStateException("Negative size: " + key + "=" + value);
245         }
246         return result;
247     }
248 
249     /**
250      * Returns the size of the entry for {@code key} and {@code value} in
251      * user-defined units.  The default implementation returns 1 so that size
252      * is the number of entries and max size is the maximum number of entries.
253      *
254      * <p>An entry's size must not change while it is in the cache.
255      * 用来计算单个对象的大小，这里默认返回1，一般需要重写该方法来计算对象的大小
256      * xUtils中创建LruMemoryCache时就重写了sizeOf方法来计算bitmap的大小
257      * mMemoryCache = new LruMemoryCache<MemoryCacheKey, Bitmap>(globalConfig.getMemoryCacheSize()) {
258      *       @Override
259      *       protected int sizeOf(MemoryCacheKey key, Bitmap bitmap) {
260      *           if (bitmap == null) return 0;
261      *           return bitmap.getRowBytes() * bitmap.getHeight();
262      *       }
263      *   };
264      *
265      */
266     protected int sizeOf(K key, V value) {
267         return 1;
268     }
269 
270     /**
271      * Clear the cache, calling {@link #entryRemoved} on each removed entry.
272      * 清空内存缓存
273      */
274     public final void evictAll() {
275         trimToSize(-1); // -1 will evict 0-sized elements
276     }
277 
278     /**
279      * For caches that do not override {@link #sizeOf}, this returns the number
280      * of entries in the cache. For all other caches, this returns the sum of
281      * the sizes of the entries in this cache.
282      */
283     public synchronized final int size() {
284         return size;
285     }
286 
287     /**
288      * For caches that do not override {@link #sizeOf}, this returns the maximum
289      * number of entries in the cache. For all other caches, this returns the
290      * maximum sum of the sizes of the entries in this cache.
291      */
292     public synchronized final int maxSize() {
293         return maxSize;
294     }
295 
296     /**
297      * Returns the number of times {@link #get} returned a value.
298      */
299     public synchronized final int hitCount() {
300         return hitCount;
301     }
302 
303     /**
304      * Returns the number of times {@link #get} returned null or required a new
305      * value to be created.
306      */
307     public synchronized final int missCount() {
308         return missCount;
309     }
310 
311     /**
312      * Returns the number of times {@link #create(Object)} returned a value.
313      */
314     public synchronized final int createCount() {
315         return createCount;
316     }
317 
318     /**
319      * Returns the number of times {@link #put} was called.
320      */
321     public synchronized final int putCount() {
322         return putCount;
323     }
324 
325     /**
326      * Returns the number of values that have been evicted.
327      */
328     public synchronized final int evictionCount() {
329         return evictionCount;
330     }
331 
332     /**
333      * Returns a copy of the current contents of the cache, ordered from least
334      * recently accessed to most recently accessed.
335      */
336     public synchronized final Map<K, V> snapshot() {
337         return new LinkedHashMap<K, V>(map);
338     }
339 
340     @Override public synchronized final String toString() {
341         int accesses = hitCount + missCount;
342         int hitPercent = accesses != 0 ? (100 * hitCount / accesses) : 0;
343         return String.format("LruCache[maxSize=%d,hits=%d,misses=%d,hitRate=%d%%]",
344                 maxSize, hitCount, missCount, hitPercent);
345     }
346 }