你的位置:首页 > 操作系统

[操作系统]内存缓存LruCache实现原理


  自己项目中一直都是用的开源的xUtils框架,包括BitmapUtils、DbUtils、ViewUtils和HttpUtils四大模块,这四大模块都是项目中比较常用的。最近决定研究一下xUtils的源码,用了这么久总得知道它的实现原理吧。我是先从先从BitmapUtils模块开始的。BitmapUtils和大多数图片加载框架一样,都是基于内存-文件-网络三级缓存。也就是加载图片的时候首先从内存缓存中取,如果没有再从文件缓存中取,如果文件缓存没有取到,就从网络下载图片并且加入内存和文件缓存。

  这篇帖子先分析内存缓存是如何实现的。好吧开始进入正题。
  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 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 }

  看完代码是不是觉得内存缓存的实现其实很简单?