Android缓存机制详解

一、android中的缓存策略

一般来说，缓存策略主要包含缓存的添加、获取和删除这三类操作。如何添加和获取缓存这个比较好理解，那么为什么还要删除缓存呢？这是因为不管是内存缓存还是硬盘缓存，它们的缓存大小都是有限的。当缓存满了之后，再想其添加缓存，这个时候就需要删除一些旧的缓存并添加新的缓存。

因此lru(least recently used)缓存算法便应运而生，lru是近期最少使用的算法，它的核心思想是当缓存满时，会优先淘汰那些近期最少使用的缓存对象。采用lru算法的缓存有两种：lrhcache和dislrucache，分别用于实现内存缓存和硬盘缓存，其核心思想都是lru缓存算法。

二、lrucache的使用

lrucache是android 3.1所提供的一个缓存类，所以在android中可以直接使用lrucache实现内存缓存。而dislrucache目前在android 还不是android sdk的一部分，但android官方文档推荐使用该算法来实现硬盘缓存。

1.lrucache的介绍

lrucache是个泛型类，主要算法原理是把最近使用的对象用强引用（即我们平常使用的对象引用方式）存储在 linkedhashmap 中。当缓存满时，把最近最少使用的对象从内存中移除，并提供了get和put方法来完成缓存的获取和添加操作。

2.lrucache的使用

lrucache的使用非常简单，我们就已图片缓存为例。

 int maxmemory = (int) (runtime.getruntime().totalmemory()/1024);
        int cachesize = maxmemory/8;
        mmemorycache = new lrucache(cachesize){
            @override
            protected int sizeof(string key, bitmap value) {
                return value.getrowbytes()*value.getheight()/1024;
            }
        };

①设置lrucache缓存的大小，一般为当前进程可用容量的1/8。
②重写sizeof方法，计算出要缓存的每张图片的大小。

注意：缓存的总容量和每个缓存对象的大小所用单位要一致。

三、lrucache的实现原理

lrucache的核心思想很好理解，就是要维护一个缓存对象列表，其中对象列表的排列方式是按照访问顺序实现的，即一直没访问的对象，将放在队尾，即将被淘汰。而最近访问的对象将放在队头，最后被淘汰。

如下图所示：

 

那么这个队列到底是由谁来维护的，前面已经介绍了是由linkedhashmap来维护。

而linkedhashmap是由数组+双向链表的数据结构来实现的。其中双向链表的结构可以实现访问顺序和插入顺序，使得linkedhashmap中的对按照一定顺序排列起来。,value>

通过下面构造函数来指定linkedhashmap中双向链表的结构是访问顺序还是插入顺序。

public linkedhashmap(int initialcapacity,
                         float loadfactor,
                         boolean accessorder) {
        super(initialcapacity, loadfactor);
        this.accessorder = accessorder;
    }

其中accessorder设置为true则为访问顺序，为false，则为插入顺序。

以具体例子解释：
当设置为true时

public static final void main(string[] args) {
        linkedhashmap map = new linkedhashmap<>(0, 0.75f, true);
        map.put(0, 0);
        map.put(1, 1);
        map.put(2, 2);
        map.put(3, 3);
        map.put(4, 4);
        map.put(5, 5);
        map.put(6, 6);
        map.get(1);
        map.get(2);

        for (map.entry entry : map.entryset()) {
            system.out.println(entry.getkey() + ":" + entry.getvalue());

        }
    }

输出结果：

0:0
3:3
4:4
5:5
6:6
1:1
2:2

即最近访问的最后输出，那么这就正好满足的lru缓存算法的思想。可见lrucache巧妙实现，就是利用了linkedhashmap的这种数据结构。

下面我们在lrucache中具体看看，怎么应用linkedhashmap来实现缓存的添加，获得和删除的。

 public lrucache(int maxsize) {
        if (maxsize <= 0) {
            throw new illegalargumentexception("maxsize <= 0");
        }
        this.maxsize = maxsize;
        this.map = new linkedhashmap(0, 0.75f, true);
    }

从lrucache的构造函数中可以看到正是用了linkedhashmap的访问顺序。

put()方法

public final v put(k key, v value) {
         //不可为空，否则抛出异常
        if (key == null || value == null) {
            throw new nullpointerexception("key == null || value == null");
        }
        v previous;
        synchronized (this) {
            //插入的缓存对象值加1
            putcount++;
            //增加已有缓存的大小
            size += safesizeof(key, value);
           //向map中加入缓存对象
            previous = map.put(key, value);
            //如果已有缓存对象，则缓存大小恢复到之前
            if (previous != null) {
                size -= safesizeof(key, previous);
            }
        }
        //entryremoved()是个空方法，可以自行实现
        if (previous != null) {
            entryremoved(false, key, previous, value);
        }
        //调整缓存大小(关键方法)
        trimtosize(maxsize);
        return previous;
    }

可以看到put()方法并没有什么难点，重要的就是在添加过缓存对象后，调用 trimtosize()方法，来判断缓存是否已满，如果满了就要删除近期最少使用的算法。
trimtosize()方法

 public void trimtosize(int maxsize) {
        //死循环
        while (true) {
            k key;
            v value;
            synchronized (this) {
                //如果map为空并且缓存size不等于0或者缓存size小于0，抛出异常
                if (size < 0 || (map.isempty() && size != 0)) {
                    throw new illegalstateexception(getclass().getname()
                            + ".sizeof() is reporting inconsistent results!");
                }
                //如果缓存大小size小于最大缓存，或者map为空，不需要再删除缓存对象，跳出循环
                if (size <= maxsize || map.isempty()) {
                    break;
                }
                //迭代器获取第一个对象，即队尾的元素，近期最少访问的元素
                map.entry toevict = map.entryset().iterator().next();
                key = toevict.getkey();
                value = toevict.getvalue();
                //删除该对象，并更新缓存大小
                map.remove(key);
                size -= safesizeof(key, value);
                evictioncount++;
            }
            entryremoved(true, key, value, null);
        }
    }

trimtosize()方法不断地删除linkedhashmap中队尾的元素，即近期最少访问的，直到缓存大小小于最大值。

当调用lrucache的get()方法获取集合中的缓存对象时，就代表访问了一次该元素，将会更新队列，保持整个队列是按照访问顺序排序。这个更新过程就是在linkedhashmap中的get()方法中完成的。

先看lrucache的get()方法

get()方法

public final v get(k key) {
        //key为空抛出异常
        if (key == null) {
            throw new nullpointerexception("key == null");
        }

        v mapvalue;
        synchronized (this) {
            //获取对应的缓存对象
            //get()方法会实现将访问的元素更新到队列头部的功能
            mapvalue = map.get(key);
            if (mapvalue != null) {
                hitcount++;
                return mapvalue;
            }
            misscount++;
        }

其中linkedhashmap的get()方法如下：

public v get(object key) {
        linkedhashmapentry e = (linkedhashmapentry)getentry(key);
        if (e == null)
            return null;
        //实现排序的关键方法
        e.recordaccess(this);
        return e.value;
    }

调用recordaccess()方法如下：

 void recordaccess(hashmap m) {
            linkedhashmap lm = (linkedhashmap)m;
            //判断是否是访问排序
            if (lm.accessorder) {
                lm.modcount++;
                //删除此元素
                remove();
                //将此元素移动到队列的头部
                addbefore(lm.header);
            }
        }

由此可见lrucache中维护了一个集合linkedhashmap，该linkedhashmap是以访问顺序排序的。当调用put()方法时，就会在结合中添加元素，并调用trimtosize()判断缓存是否已满，如果满了就用linkedhashmap的迭代器删除队尾元素，即近期最少访问的元素。当调用get()方法访问缓存对象时，就会调用linkedhashmap的get()方法获得对应集合元素，同时会更新该元素到队头。

以上便是lrucache实现的原理，理解了linkedhashmap的数据结构就能理解整个原理。如果不懂，可以先看看linkedhashmap的具体实现。