内存储器缓存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 put100                 //如果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 of120      * 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 -1150      *     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++;  //回收次数+1173             }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 is207      * invoked when a value is evicted to make space, removed by a call to208      * {@link #remove}, or replaced by a call to {@link #put}. The default209      * implementation does nothing.210      *211      * <p>The method is called without synchronization: other threads may212      * access the cache while this method is executing.213      *214      * @param evicted true if the entry is being removed to make space, false215      *     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 by218      *     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. The225      * default implementation returns null.226      *227      * <p>The method is called without synchronization: other threads may228      * access the cache while this method is executing.229      *230      * <p>If a value for {@code key} exists in the cache when this method231      * returns, the created value will be released with {@link #entryRemoved}232      * and discarded. This can occur when multiple threads request the same key233      * at the same time (causing multiple values to be created), or when one234      * thread calls {@link #put} while another is creating a value for the same235      * 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} in251      * user-defined units.  The default implementation returns 1 so that size252      * 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      *       @Override259      *       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 elements276     }277 278     /**279      * For caches that do not override {@link #sizeOf}, this returns the number280      * of entries in the cache. For all other caches, this returns the sum of281      * 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 maximum289      * number of entries in the cache. For all other caches, this returns the290      * 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 new305      * 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 least334      * 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 }