【转】图片缓存之内存缓存技术LruCache、软引用 比较

时间：2024-05-25 22:36:44

每当碰到一些大图片的时候，我们如果不对图片进行处理就会报OOM异常，
这个问题曾经让我觉得很烦恼，后来终于得到了解决，
那么现在就让我和大家一起分享一下吧。
这篇博文要讲的图片缓存机制，我接触到的有两钟，一种是软引用，另一种是内存缓存技术。
先来看下两者的使用方式，再来作比较。
除了加载图片时要用到缓存处理，还有一个比较重要的步骤要做，就是要先压缩图片。

1、压缩图片
至于要压缩到什么状态就要看自己当时的处境了，压缩图片的时候既要达到一个小的值，又不能让其模糊
，更不能拉伸图片。

  1. /**
  2. * 加载内存卡图片
  3. */
  4. BitmapFactory.Options options = new BitmapFactory.Options();
  5. options.inJustDecodeBounds = true; // 设置了此属性一定要记得将值设置为false
  6. Bitmap bitmap = null;
  7. bitmap = BitmapFactory.decodeFile(url, options);
  8. int be = (int) ((options.outHeight > options.outWidth ? options.outHeight / 150
  9. : options.outWidth / 200));
  10. if (be <= 0) // 判断200是否超过原始图片高度
  11. be = 1; // 如果超过，则不进行缩放
  12. options.inSampleSize = be;
  13. options.inPreferredConfig = Bitmap.Config.ARGB_4444;
  14. options.inPurgeable = true;
  15. options.inInputShareable = true;
  16. options.inJustDecodeBounds = false;
  17. try {
  18. bitmap = BitmapFactory.decodeFile(url, options);
  19. } catch (OutOfMemoryError e) {
  20. System.gc();
  21. Log.e(TAG, "OutOfMemoryError");
  22. }

2、软引用：
只要有足够的内存，就一直保持对象，直到发现内存吃紧且没有Strong Ref时才回收对象。
我们可以这样定义：map里面的键是用来放图片地址的，既可以是网络上的图片地址，也可以SDcard上的图片地址，
map里面的值里面放的是持有软引用的Bitmap，当然如果你要放Drawable，那也是可以的。

  1. private Map<String, SoftReference<Bitmap>> imageMap
  2. = new HashMap<String, SoftReference<Bitmap>>();

接下来就让我再介绍一下如何具体加载图片：
步骤：（1）先通过URL查看缓存中是否有图片，如果有，则直接去缓存中取得。
           如果没有，就开线程重新去网上下载。
      （2）下载完了之后，就把图片放在缓存里面，方便下次可以直接从缓存中取得。

  1. public Bitmap loadBitmap(final String imageUrl,final ImageCallBack imageCallBack) {
  2. SoftReference<Bitmap> reference = imageMap.get(imageUrl);
  3. if(reference != null) {
  4. if(reference.get() != null) {
  5. return reference.get();
  6. }
  7. }
  8. final Handler handler = new Handler() {
  9. public void handleMessage(final android.os.Message msg) {
  10. //加入到缓存中
  11. Bitmap bitmap = (Bitmap)msg.obj;
  12. imageMap.put(imageUrl, new SoftReference<Bitmap>(bitmap));
  13. if(imageCallBack != null) {
  14. imageCallBack.getBitmap(bitmap);
  15. }
  16. }
  17. };
  18. new Thread(){
  19. public void run() {
  20. Message message = handler.obtainMessage();
  21. message.obj = downloadBitmap(imageUrl);
  22. handler.sendMessage(message);
  23. }
  24. }.start();
  25. return null ;
  26. }
  27. // 从网上下载图片
  28. private Bitmap downloadBitmap (String imageUrl) {
  29. Bitmap bitmap = null;
  30. try {
  31. bitmap = BitmapFactory.decodeStream(new URL(imageUrl).openStream());
  32. return bitmap ;
  33. } catch (Exception e) {
  34. e.printStackTrace();
  35. return null;
  36. }
  37. }
  1. public interface ImageCallBack{
  2. void getBitmap(Bitmap bitmap);
  3. }

2、内存缓存技术
另外一种图片缓存的方式就是内存缓存技术。在Android中，有一个叫做LruCache类专门用来做图片缓存处理的。
它有一个特点，当缓存的图片达到了预先设定的值的时候，那么近期使用次数最少的图片就会被回收掉。
步骤：（1）要先设置缓存图片的内存大小，我这里设置为手机内存的1/8,
           手机内存的获取方式：int MAXMEMONRY = (int) (Runtime.getRuntime() .maxMemory() / 1024);
      （2）LruCache里面的键值对分别是URL和对应的图片
      （3）重写了一个叫做sizeOf的方法，返回的是图片数量。

  1. private LruCache<String, Bitmap> mMemoryCache;
  2. private LruCacheUtils() {
  3. if (mMemoryCache == null)
  4. mMemoryCache = new LruCache<String, Bitmap>(
  5. MAXMEMONRY / 8) {
  6. @Override
  7. protected int sizeOf(String key, Bitmap bitmap) {
  8. // 重写此方法来衡量每张图片的大小，默认返回图片数量。
  9. return bitmap.getRowBytes() * bitmap.getHeight() / 1024;
  10. }
  11. @Override
  12. protected void entryRemoved(boolean evicted, String key,
  13. Bitmap oldValue, Bitmap newValue) {
  14. Log.v("tag", "hard cache is full , push to soft cache");
  15. }
  16. };
  17. }

（4）下面的方法分别是清空缓存、添加图片到缓存、从缓存中取得图片、从缓存中移除。
          移除和清除缓存是必须要做的事，因为图片缓存处理不当就会报内存溢出，所以一定要引起注意。

  1. public void clearCache() {
  2. if (mMemoryCache != null) {
  3. if (mMemoryCache.size() > 0) {
  4. Log.d("CacheUtils",
  5. "mMemoryCache.size() " + mMemoryCache.size());
  6. mMemoryCache.evictAll();
  7. Log.d("CacheUtils", "mMemoryCache.size()" + mMemoryCache.size());
  8. }
  9. mMemoryCache = null;
  10. }
  11. }
  12. public synchronized void addBitmapToMemoryCache(String key, Bitmap bitmap) {
  13. if (mMemoryCache.get(key) == null) {
  14. if (key != null && bitmap != null)
  15. mMemoryCache.put(key, bitmap);
  16. } else
  17. Log.w(TAG, "the res is aready exits");
  18. }
  19. public synchronized Bitmap getBitmapFromMemCache(String key) {
  20. Bitmap bm = mMemoryCache.get(key);
  21. if (key != null) {
  22. return bm;
  23. }
  24. return null;
  25. }
  26. /**
  27. * 移除缓存
  28. *
  29. * @param key
  30. */
  31. public synchronized void removeImageCache(String key) {
  32. if (key != null) {
  33. if (mMemoryCache != null) {
  34. Bitmap bm = mMemoryCache.remove(key);
  35. if (bm != null)
  36. bm.recycle();
  37. }
  38. }
  39. }

4、两者的比较
说到这里，我觉得有必要来进行一下比较了。
网上有很多人使用软引用加载图片的多 ，但是现在已经不再推荐使用这种方式了，
（1）因为从 Android 2.3 (API Level 9)开始，垃圾回收器会更倾向于回收持有软引用或弱引用的对象，
     这让软引用和弱引用变得不再可靠。
（2）另外，Android 3.0 (API Level 11)中，图片的数据会存储在本地的内存当中，
     因而无法用一种可预见的方式将其释放，这就有潜在的风险造成应用程序的内存溢出并崩溃，
所以我这里用得是LruCache来缓存图片，当存储Image的大小大于LruCache设定的值，系统自动释放内存，
这个类是3.1版本中提供的，如果你是在更早的Android版本中开发，则需要导入android-support-v4的jar包。

下面说一下LRUCache：

【百度知道：

内存缓存技术对那些大量占用应用程序宝贵内存的图片提供了快速访问的方法。其中最核心的类是LruCache (此类在android-support-v4的包中提供) 。这个类非常适合用来缓存图片，它的主要算法原理是把最近使用的对象用强引用存储在 LinkedHashMap 中，并且把最近最少使用的对象在缓存值达到预设定值之前从内存中移除。

　　在过去，我们经常会使用一种非常流行的内存缓存技术的实现，即软引用或弱引用 (SoftReference or WeakReference)。但是现在已经不再推荐使用这种方式了，因为从 Android 2.3 (API Level 9)开始，垃圾回收器会更倾向于回收持有软引用或弱引用的对象，这让软引用和弱引用变得不再可靠。另外，Android 3.0 (API Level 11)中，图片的数据会存储在本地的内存当中，因而无法用一种可预见的方式将其释放，这就有潜在的风险造成应用程序的内存溢出并崩溃。

　　为了能够选择一个合适的缓存大小给LruCache, 有以下多个因素应该放入考虑范围内，例如：

　　你的设备可以为每个应用程序分配多大的内存？

　　设备屏幕上一次最多能显示多少张图片？有多少图片需要进行预加载，因为有可能很快也会显示在屏幕上？

　　你的设备的屏幕大小和分辨率分别是多少？一个超高分辨率的设备（例如 Galaxy Nexus) 比起一个较低分辨率的设备（例如 Nexus S），在持有相同数量图片的时候，需要更大的缓存空间。

　　图片的尺寸和大小，还有每张图片会占据多少内存空间。

　　图片被访问的频率有多高？会不会有一些图片的访问频率比其它图片要高？如果有的话，你也许应该让一些图片常驻在内存当中，或者使用多个LruCache 对象来区分不同组的图片。

　　你能维持好数量和质量之间的平衡吗？有些时候，存储多个低像素的图片，而在后台去开线程加载高像素的图片会更加的有效。

　　并没有一个指定的缓存大小可以满足所有的应用程序，这是由你决定的。你应该去分析程序内存的使用情况，然后制定出一个合适的解决方案。一个太小的缓存空间，有可能造成图片频繁地被释放和重新加载，这并没有好处。而一个太大的缓存空间，则有可能还是会引起 java.lang.OutOfMemory 的异常。】

【转】链接：http://www.cnblogs.com/lzrabbit/p/3734850.html（里面介绍LRUcache的实现机制）

【转】http://blog.jobbole.com/30940/（里面讲Java 缓存的各种算法，后面附原文）

【转】http://www.cnblogs.com/jerehedu/p/4263649.html（介绍封装好的ACache这个类的细节）

为什么我们需要缓存？

很久很久以前，在还没有缓存的时候……用户经常是去请求一个对象，而这个对象是从数据库去取，然后，这个对象变得越来越大，这个用户每次的请求时间也越来越长了，这也把数据库弄得很痛苦，他无时不刻不在工作。所以，这个事情就把用户和数据库弄得很生气，接着就有可能发生下面两件事情：

１.用户很烦，在抱怨，甚至不去用这个应用了（这是大多数情况下都会发生的）

２.数据库为打包回家，离开这个应用，然后，就出现了大麻烦（没地方去存储数据了）（发生在极少数情况下）

上帝派来了缓存

在几年之后，IBM（60年代）的研究人员引进了一个新概念，它叫“缓存”。

什么是缓存？

正如开篇所讲，缓存是“存贮数据（使用频繁的数据）的临时地方，因为取原始数据的代价太大了，所以我可以取得快一些。”

缓存可以认为是数据的池，这些数据是从数据库里的真实数据复制出来的，并且为了能别取回，被标上了标签（键 ID）。太棒了

programmer one 已经知道这点了，但是他还不知道下面的缓存术语。

【转】图片缓存之内存缓存技术LruCache、软引用 比较

命中：

当客户发起一个请求（我们说他想要查看一个产品信息），我们的应用接受这个请求，并且如果是在第一次检查缓存的时候，需要去数据库读取产品信息。

如果在缓存中，一个条目通过一个标记被找到了，这个条目就会被使用、我们就叫它缓存命中。所以，命中率也就不难理解了。

Cache Miss：

但是这里需要注意两点：

１.　如果还有缓存的空间，那么，没有命中的对象会被存储到缓存中来。

２.　如果缓存慢了，而又没有命中缓存，那么就会按照某一种策略，把缓存中的旧对象踢出，而把新的对象加入缓存池。而这些策略统称为替代策略（缓存算法），这些策略会决定到底应该提出哪些对象。

存储成本：

当没有命中时，我们会从数据库取出数据，然后放入缓存。而把这个数据放入缓存所需要的时间和空间，就是存储成本。

索引成本：

和存储成本相仿。

失效：

当存在缓存中的数据需要更新时，就意味着缓存中的这个数据失效了。

替代策略：

当缓存没有命中时，并且缓存容量已经满了，就需要在缓存中踢出一个老的条目，加入一条新的条目，而到底应该踢出什么条目，就由替代策略决定。

最优替代策略：

最优的替代策略就是想把缓存中最没用的条目给踢出去，但是未来是不能够被预知的，所以这种策略是不可能实现的。但是有很多策略，都是朝着这个目前去努力。

Java 街恶梦：

当 programmer one 在读这篇文章的时候，他睡着了，并且做了个恶梦（每个人都有做恶梦的时候）。

programmer one：nihahha，我要把你弄失效！（疯狂的状态）

缓存对象：别别，让我活着，他们还需要我，我还有孩子。

programmer one：每个缓存对象在失效之前都会那样说。你从什么时候开始有孩子的？不用担心，现在就永远消失吧！

哈哈哈哈哈……programmer one 恐怖的笑着，但是警笛打破了沉静，警察把 programmer one 抓了起来，并且控告他杀死了（失效）一个仍需被使用的缓存对象，他被押到了*。

programmer one 突然醒了，他被吓到了，浑身是汗，他开始环顾四周，发现这确实是个梦，然后赶紧继续阅读这篇文章，努力的消除自己的恐慌。

在programmer one 醒来之后，他又开始阅读文章了。

缓存算法

没有人能说清哪种缓存算法优于其他的缓存算法

Least Frequently Used（LFU）：

大家好，我是 LFU，我会计算为每个缓存对象计算他们被使用的频率。我会把最不常用的缓存对象踢走。

Least Recently User（LRU）：

我是 LRU 缓存算法，我把最近最少使用的缓存对象给踢走。

我总是需要去了解在什么时候，用了哪个缓存对象。如果有人想要了解我为什么总能把最近最少使用的对象踢掉，是非常困难的。

浏览器就是使用了我（LRU）作为缓存算法。新的对象会被放在缓存的顶部，当缓存达到了容量极限，我会把底部的对象踢走，而技巧就是：我会把最新被访问的缓存对象，放到缓存池的顶部。

所以，经常被读取的缓存对象就会一直呆在缓存池中。有两种方法可以实现我，array 或者是 linked list。

我的速度很快，我也可以被数据访问模式适配。我有一个大家庭，他们都可以完善我，甚至做的比我更好（我确实有时会嫉妒，但是没关系）。我家庭的一些成员包括 LRU2 和 2Q，他们就是为了完善 LRU 而存在的。

Least Recently Used 2（LRU2）：

我是 Least Recently Used 2，有人叫我最近最少使用 twice，我更喜欢这个叫法。我会把被两次访问过的对象放入缓存池，当缓存池满了之后，我会把有两次最少使用的缓存对象踢走。因为需要跟踪对象2次，访问负载就会随着缓存池的增加而增加。如果把我用在大容量的缓存池中，就会有问题。另外，我还需要跟踪那么不在缓存的对象，因为他们还没有被第二次读取。我比LRU好，而且是 adoptive to access 模式 。

Two Queues（2Q）：

我是 Two Queues；我把被访问的数据放到 LRU 的缓存中，如果这个对象再一次被访问，我就把他转移到第二个、更大的 LRU 缓存。

我踢走缓存对象是为了保持第一个缓存池是第二个缓存池的1/3。当缓存的访问负载是固定的时候，把 LRU 换成 LRU2，就比增加缓存的容量更好。这种机制使得我比 LRU2 更好，我也是 LRU 家族中的一员，而且是 adoptive to access 模式 。

Adaptive Replacement Cache（ARC）：

我是 ARC，有人说我是介于 LRU 和 LFU 之间，为了提高效果，我是由2个 LRU 组成，第一个，也就是 L1，包含的条目是最近只被使用过一次的，而第二个 LRU，也就是 L2，包含的是最近被使用过两次的条目。因此， L1 放的是新的对象，而 L2 放的是常用的对象。所以，别人才会认为我是介于 LRU 和 LFU 之间的，不过没关系，我不介意。

我被认为是性能最好的缓存算法之一，能够自调，并且是低负载的。我也保存着历史对象，这样，我就可以记住那些被移除的对象，同时，也让我可以看到被移除的对象是否可以留下，取而代之的是踢走别的对象。我的记忆力很差，但是我很快，适用性也强。

Most Recently Used（MRU）：

我是 MRU，和 LRU 是对应的。我会移除最近最多被使用的对象，你一定会问我为什么。好吧，让我告诉你，当一次访问过来的时候，有些事情是无法预测的，并且在缓存系统中找出最少最近使用的对象是一项时间复杂度非常高的运算，这就是为什么我是最好的选择。

我是数据库内存缓存中是多么的常见！每当一次缓存记录的使用，我会把它放到栈的顶端。当栈满了的时候，你猜怎么着？我会把栈顶的对象给换成新进来的对象！

First in First out（FIFO）：

我是先进先出，我是一个低负载的算法，并且对缓存对象的管理要求不高。我通过一个队列去跟踪所有的缓存对象，最近最常用的缓存对象放在后面，而更早的缓存对象放在前面，当缓存容量满时，排在前面的缓存对象会被踢走，然后把新的缓存对象加进去。我很快，但是我并不适用。

Second Chance：

大家好，我是 second chance，我是通过 FIFO 修改而来的，被大家叫做 second chance 缓存算法，我比 FIFO 好的地方是我改善了 FIFO 的成本。我是 FIFO 一样也是在观察队列的前端，但是很FIFO的立刻踢出不同，我会检查即将要被踢出的对象有没有之前被使用过的标志（1一个 bit 表示），没有没有被使用过，我就把他踢出；否则，我会把这个标志位清除，然后把这个缓存对象当做新增缓存对象加入队列。你可以想象就这就像一个环队列。当我再一次在队头碰到这个对象时，由于他已经没有这个标志位了，所以我立刻就把他踢开了。我在速度上比 FIFO 快。

CLock：

我是 Clock，一个更好的 FIFO，也比 second chance 更好。因为我不会像 second chance 那样把有标志的缓存对象放到队列的尾部，但是也可以达到 second chance 的效果。

我持有一个装有缓存对象的环形列表，头指针指向列表中最老的缓存对象。当缓存 miss 发生并且没有新的缓存空间时，我会问问指针指向的缓存对象的标志位去决定我应该怎么做。如果标志是0，我会直接用新的缓存对象替代这个缓存对象；如果标志位是1，我会把头指针递增，然后重复这个过程，知道新的缓存对象能够被放入。我比 second chance 更快。

Simple time-based：

我是 simple time-based 缓存算法，我通过绝对的时间周期去失效那些缓存对象。对于新增的对象，我会保存特定的时间。我很快，但是我并不适用。

Extended time-based expiration：

我是 extended time-based expiration 缓存算法，我是通过相对时间去失效缓存对象的；对于新增的缓存对象，我会保存特定的时间，比如是每5分钟，每天的12点。

Sliding time-based expiration：

我是 sliding time-based expiration，与前面不同的是，被我管理的缓存对象的生命起点是在这个缓存的最后被访问时间算起的。我很快，但是我也不太适用。

其他的缓存算法还考虑到了下面几点：

成本：如果缓存对象有不同的成本，应该把那些难以获得的对象保存下来。

容量：如果缓存对象有不同的大小，应该把那些大的缓存对象清除，这样就可以让更多的小缓存对象进来了。

时间：一些缓存还保存着缓存的过期时间。电脑会失效他们，因为他们已经过期了。

根据缓存对象的大小而不管其他的缓存算法可能是有必要的。

电子邮件！

在读完这篇文章之后，programmer one 想了一会儿，然后决定给作者发封邮件，他感觉作者的名字在哪听过，但是已经想不起来了。不管怎样，他还是把邮件发送出来了，他询问了作者在分布式环境中，缓存是怎么样工作的。

文章的作者收到了邮件，具有讽刺意味的是，这个作者就是面试 programmer one 的人  ，作者回复了……

在这一部分中，我们来看看如何实现这些著名的缓存算法。以下的代码只是示例用的，如果你想自己实现缓存算法，可能自己还得加上一些额外的工作。

LeftOver 机制

在 programmer one 阅读了文章之后，他接着看了文章的评论，其中有一篇评论提到了 leftover 机制——random cache。

Random Cache

我是随机缓存，我随意的替换缓存实体，没人敢抱怨。你可以说那个被替换的实体很倒霉。通过这些行为，我随意的去处缓存实体。我比 FIFO 机制好，在某些情况下，我甚至比 LRU 好，但是，通常LRU都会比我好。

现在是评论时间

当 programmer one 继续阅读评论的时候，他发现有个评论非常有趣，这个评论实现了一些缓存算法，应该说这个评论做了一个链向评论者网站的链接，programmer one顺着链接到了那个网站，接着阅读。

看看缓存元素（缓存实体）

1
2
3
4
5
6
7
public class CacheElement
 {
     private Object objectValue;
     private Object objectKey;
     private int index;
     private int hitCount;　// getters and setters
 }

这个缓存实体拥有缓存的key和value，这个实体的数据结构会被以下所有缓存算法用到。

缓存算法的公用代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public final synchronized void addElement(Object key, Object value)
{
    int index;
    Object obj;
    // get the entry from the table
    obj = table.get(key);
    // If we have the entry already in our table
    // then get it and replace only its value.
    obj = table.get(key);
    if (obj != null)
    {
        CacheElement element;
        element = (CacheElement) obj;
        element.setObjectValue(value);
        element.setObjectKey(key);
        return;
    }
｝

上面的代码会被所有的缓存算法实现用到。这段代码是用来检查缓存元素是否在缓存中了，如果是，我们就替换它，但是如果我们找不到这个 key 对应的缓存，我们会怎么做呢？那我们就来深入的看看会发生什么吧！

现场访问

今天的专题很特殊，因为我们有特殊的客人，事实上他们是我们想要听的与会者，但是首先，先介绍一下我们的客人：Random Cache，FIFO Cache。让我们从 Random Cache开始。

看看随机缓存的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public final synchronized void addElement(Object key, Object value)
{
    int index;
    Object obj;
    obj = table.get(key);
    if (obj != null)
    {
        CacheElement element;// Just replace the value.
        element = (CacheElement) obj;
        element.setObjectValue(value);
        element.setObjectKey(key);
        return;
    }// If we haven't filled the cache yet, put it at the end.
    if (!isFull())
    {
        index = numEntries;
        ++numEntries;
    }
    else { // Otherwise, replace a random entry.
        index = (int) (cache.length * random.nextFloat());
        table.remove(cache[index].getObjectKey());
    }
    cache[index].setObjectValue(value);
    cache[index].setObjectKey(key);
    table.put(key, cache[index]);
}

看看FIFO缓算法的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public final synchronized void addElement(Objectkey, Object value)
{
    int index;
    Object obj;
    obj = table.get(key);
    if (obj != null)
    {
        CacheElement element; // Just replace the value.
        element = (CacheElement) obj;
        element.setObjectValue(value);
        element.setObjectKey(key);
        return;
    }
    // If we haven't filled the cache yet, put it at the end.
    if (!isFull())
    {
        index = numEntries;
        ++numEntries;
    }
    else { // Otherwise, replace the current pointer,
           // entry with the new one.
        index = current;
        // in order to make Circular FIFO
        if (++current >= cache.length)
            current = 0;
        table.remove(cache[index].getObjectKey());
    }
    cache[index].setObjectValue(value);
    cache[index].setObjectKey(key);
    table.put(key, cache[index]);
}
看看LFU缓存算法的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public synchronized Object getElement(Object key)
{
    Object obj;
    obj = table.get(key);
    if (obj != null)
    {
        CacheElement element = (CacheElement) obj;
        element.setHitCount(element.getHitCount() + 1);
        return element.getObjectValue();
    }
    return null;
}
public final synchronized void addElement(Object key, Object value)
{
    Object obj;
    obj = table.get(key);
    if (obj != null)
    {
        CacheElement element; // Just replace the value.
        element = (CacheElement) obj;
        element.setObjectValue(value);
        element.setObjectKey(key);
        return;
    }
    if (!isFull())
    {
        index = numEntries;
        ++numEntries;
    }
    else
    {
        CacheElement element = removeLfuElement();
        index = element.getIndex();
        table.remove(element.getObjectKey());
    }
    cache[index].setObjectValue(value);
    cache[index].setObjectKey(key);
    cache[index].setIndex(index);
    table.put(key, cache[index]);
}
public CacheElement removeLfuElement()
{
    CacheElement[] elements = getElementsFromTable();
    CacheElement leastElement = leastHit(elements);
    return leastElement;
}
public static CacheElement leastHit(CacheElement[] elements)
{
    CacheElement lowestElement = null;
    for (int i = 0; i < elements.length; i++)
    {
        CacheElement element = elements[i];
        if (lowestElement == null)
        {
            lowestElement = element;
        }
        else {
            if (element.getHitCount() < lowestElement.getHitCount())
            {
                lowestElement = element;
            }
        }
    }
    return lowestElement;
}

今天的专题很特殊，因为我们有特殊的客人，事实上他们是我们想要听的与会者，但是首先，先介绍一下我们的客人：Random Cache, FIFO Cache。让我们从 Random Cache开始。

最重点的代码，就应该是 leastHit 这个方法，这段代码就是把
hitCount 最低的元素找出来，然后删除，给新进的缓存元素留位置。

看看LRU缓存算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
private void moveToFront(int index)
{
    int nextIndex, prevIndex;
    if(head != index)
    {
        nextIndex = next[index];
        prevIndex = prev[index];
        // Only the head has a prev entry that is an invalid index
        // so we don't check.
        next[prevIndex] = nextIndex;
        // Make sure index is valid. If it isn't, we're at the tail
        // and don't set prev[next].
        if(nextIndex >= 0)
            prev[nextIndex] = prevIndex;
        else
            tail = prevIndex;
        prev[index] = -1;
        next[index] = head;
        prev[head] = index;
        head = index;
    }
}
public final synchronized void addElement(Object key, Object value)
{
    int index;Object obj;
    obj = table.get(key);
    if(obj != null)
    {
        CacheElement entry;
        // Just replace the value, but move it to the front.
        entry = (CacheElement)obj;
        entry.setObjectValue(value);
        entry.setObjectKey(key);
        moveToFront(entry.getIndex());
        return;
    }
    // If we haven't filled the cache yet, place in next available
    // spot and move to front.
    if(!isFull())
    {
        if(_numEntries > 0)
        {
            prev[_numEntries] = tail;
            next[_numEntries] = -1;
            moveToFront(numEntries);
        }
        ++numEntries;
    }
    else { // We replace the tail of the list.
        table.remove(cache[tail].getObjectKey());
        moveToFront(tail);
    }
    cache[head].setObjectValue(value);
    cache[head].setObjectKey(key);
    table.put(key, cache[head]);
}

这段代码的逻辑如 LRU算法 的描述一样，把再次用到的缓存提取到最前面，而每次删除的都是最后面的元素。

结论

我们已经看到 LFU缓存算法 和 LRU缓存算法的实现方式，至于如何实现，采用数组还是 LinkedHashMap，都由你决定，不够我一般是小的缓存容量用数组，大的用 LinkedHashMap。

相关文章