内存缓存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 {
 30     private final LinkedHashMap 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(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 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      

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       

The method is called without synchronization: other threads may
228       access the cache while this method is executing.
229
230       

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       

An entry’s size must not change while it is in the cache.
255       用来计算单个对象的大小,这里默认返回1,一般需要重写该方法来计算对象的大小
256       xUtils中创建LruMemoryCache时就重写了sizeOf方法来计算bitmap的大小
257       mMemoryCache = new LruMemoryCache(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 snapshot() {
337         return new LinkedHashMap(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 }

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

时间: 2024-10-26 16:53:34

内存缓存LruCache实现原理的相关文章

Android开发中内存缓存LruCache实现原理及实例应用

先分析内存缓存是如何实现的,开始进入正题. BitmapUtils内存缓存的核心类LruMemoryCache,LruMemoryCache代码和v4包的LruCache一样,只是加了一个存储超期的处理,这里分析LruCache源码.LRU即Least Recently Used,近期最少使用算法.也就是当内存缓存达到设定的最大值时将内存缓存中近期最少使用的对象移除,有效的避免了OOM的出现. 讲到LruCache不得不提一下LinkedHashMap,因为LruCache中Lru算法的实现就是

Android图片三级缓存策略(网络、本地、内存缓存)_Android

一.简介 现在的Android应用程序中,不可避免的都会使用到图片,如果每次加载图片的时候都要从网络重新拉取,这样不但很耗费用户的流量,而且图片加载的也会很慢,用户体验很不好.所以一个应用的图片缓存策略是很重要的.通常情况下,Android应用程序中图片的缓存策略采用"内存-本地-网络"三级缓存策略,首先应用程序访问网络拉取图片,分别将加载的图片保存在本地SD卡中和内存中,当程序再一次需要加载图片的时候,先判断内存中是否有缓存,有则直接从内存中拉取,否则查看本地SD卡中是否有缓存,SD

LruCache算法原理及实现

LruCache算法原理及实现 LruCache算法原理 LRU为Least Recently Used的缩写,意思也就是近期最少使用算法.LruCache将LinkedHashMap的顺序设置为LRU顺序来实现LRU缓存,每次调用get并获取到值(也就是从内存缓存中命中),则将该对象移到链表的尾端.调用put插入新的对象也是存储在链表尾端,这样当内存缓存达到设定的最大值时,将链表头部的对象(近期最少用到的)移除. 基于LinkedHashMap的LRUCache的实现,关键是重写LinkedH

Android图片三级缓存策略(网络、本地、内存缓存)

一.简介 现在的Android应用程序中,不可避免的都会使用到图片,如果每次加载图片的时候都要从网络重新拉取,这样不但很耗费用户的流量,而且图片加载的也会很慢,用户体验很不好.所以一个应用的图片缓存策略是很重要的.通常情况下,Android应用程序中图片的缓存策略采用"内存-本地-网络"三级缓存策略,首先应用程序访问网络拉取图片,分别将加载的图片保存在本地SD卡中和内存中,当程序再一次需要加载图片的时候,先判断内存中是否有缓存,有则直接从内存中拉取,否则查看本地SD卡中是否有缓存,SD

Java和Android的LRU缓存及实现原理_Android

一.概述 Android提供了LRUCache类,可以方便的使用它来实现LRU算法的缓存.Java提供了LinkedHashMap,可以用该类很方便的实现LRU算法,Java的LRULinkedHashMap就是直接继承了LinkedHashMap,进行了极少的改动后就可以实现LRU算法. 二.Java的LRU算法 Java的LRU算法的基础是LinkedHashMap,LinkedHashMap继承了HashMap,并且在HashMap的基础上进行了一定的改动,以实现LRU算法. 1.Hash

PHP中文件缓存转内存缓存的方法_php技巧

前言 顾名思义文件缓存转内存缓存就是将存储在文件中的数据转到内存中去,实现磁盘操作转为内存操作,这样可以大大提高数据访问速度,并能实现缓存数据的分布式部署.文件缓存与内存缓存的介绍请参考名词解释部分. 原理 文件缓存转内存缓存的原理就是把文件缓存中的数据转存到内存中,以实现数据全局共享,解决频繁加载文件和装载数据的问题,采用Memcache工具实现内存缓存数据. 实现机制与步骤 1,检查文件是否存在内存缓存,如果不存在加载缓存文件 2,加载缓存文件,并获取缓存文件中的数据 3,将缓存文件中的数据

PHP内存缓存功能memcached示例_php实例

下文简单介绍了memcached类的应用示例,具有一定的参考价值,感兴趣的小伙伴们可以参考一下. 一.memcached 简介 在很多场合,我们都会听到 memcached 这个名字,但很多同学只是听过,并没有用过或实际了解过,只知道它是一个很不错的东东.这里简单介绍一下,memcached 是高效.快速的分布式内存对象缓存系统,主要用于加速 WEB 动态应用程序. 二.memcached 安装 首先是下载 memcached 了,目前最新版本是 1.1.12,直接从官方网站即可下载到 memc

php MemCache内存缓存学习笔记

一.Memcache简介 Memcache(内存,缓存) :是一个高性能的分布式的内存对象缓存系统.通过在内存里维护一个巨大的HashTable.由Memcached来管理这个巨大的HashTable. 二.Memcache 与 Memcached的区别 Memcache是软件名称,Memcached是启动后的进程名称. 三.Memcache工作原理 memcached是以守护程序方式运行于一个或多个服务器中,随时会接收客户端的连接和操作. 在没有安装memcache的时候网站工作的原理是:浏览

Java和Android的LRU缓存及实现原理

一.概述 Android提供了LRUCache类,可以方便的使用它来实现LRU算法的缓存.Java提供了LinkedHashMap,可以用该类很方便的实现LRU算法,Java的LRULinkedHashMap就是直接继承了LinkedHashMap,进行了极少的改动后就可以实现LRU算法. 二.Java的LRU算法 Java的LRU算法的基础是LinkedHashMap,LinkedHashMap继承了HashMap,并且在HashMap的基础上进行了一定的改动,以实现LRU算法. 1.Hash