android开发常用的缓存策略详解（2）- 先进先出(FIFO)置换算法

那么什么是FIFO算法呢？

这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO 算法并不能保证这些页面不被淘汰。

1. 新访问的数据插入FIFO队列尾部，数据在FIFO队列中顺序移动；
2. 淘汰FIFO队列头部的数据；

由于本算法涉及到LinkedList 那么小编在这介绍一下：

inkedList与ArrayList一样实现List接口，LinkedList是List接口链表的实现。基于链表实现的方式使得LinkedList在插入和删除时更优于ArrayList，而随机访问则比ArrayList逊色些。LinkedList实现所有可选的列表操作，并允许所有的元素包括null。除了实现 List 接口外，LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。

下面以ImageLoader中的FIFOLimitedMemoryCache 进行分析：

public abstract class LimitedMemoryCache<K, V> extends BaseMemoryCache<K, V> {
    private static final int MAX_NORMAL_CACHE_SIZE_IN_MB = 16;
    private static final int MAX_NORMAL_CACHE_SIZE = 16777216;
    private final int sizeLimit;
    private final AtomicInteger cacheSize;
    private final List<V> hardCache = Collections.synchronizedList(new LinkedList());

    public LimitedMemoryCache(int sizeLimit) {
        this.sizeLimit = sizeLimit;
        //AtomicInteger提供原子操作来进行Integer的使用，因此十分适合高并发情况下的使用。
        this.cacheSize = new AtomicInteger();
        if(sizeLimit > 16777216) {
            L.w("You set too large memory cache size (more than %1$d Mb)", new Object[]{Integer.valueOf(16)});
        }

    }

    public boolean put(K key, V value) {
        boolean putSuccessfully = false;
        int valueSize = this.getSize(value); //获取当前文件的大小
        int sizeLimit = this.getSizeLimit();//获取最大允许的大小
        int curCacheSize = this.cacheSize.get();//获取当前的大小
        if(valueSize < sizeLimit) {  //判断当前文件是否小于最大允许的大小
            while(true) {   
                if(curCacheSize + valueSize <= sizeLimit) {  //判断是是否大于最大允许值
                    this.hardCache.add(value);  //放入到LinkedList集合中
                    this.cacheSize.addAndGet(valueSize);//计算当前文件的缓存大小
                    putSuccessfully = true;
                    break;
                }

                Object removedValue = this.removeNext(); //查找到最先存储的值，并删除  子类的实现方法：(Bitmap)this.queue.remove(0);
                if(this.hardCache.remove(removedValue)) {
                    curCacheSize = this.cacheSize.addAndGet(-this.getSize(removedValue));//计算移除后的大小
                }
            }
        }
        //进行存储到对应位置
        super.put(key, value);
        return putSuccessfully;
    }

    public void remove(K key) {
        Object value = super.get(key);//获取到当前对应的对象
        if(value != null && this.hardCache.remove(value)) {
            this.cacheSize.addAndGet(-this.getSize(value));//计算存储对象的大小并移除
        }

        super.remove(key);
    }

    public void clear() {
        this.hardCache.clear();
        this.cacheSize.set(0);
        super.clear();
    }

    protected int getSizeLimit() {
        return this.sizeLimit;
    }

    protected abstract int getSize(V var1);

    protected abstract V removeNext();
}

从put方法中可以看出，本算法在存储前先计算对应的存储空间的大小，如果存储空间不满足需求，则删除最先进入的。新访问的数据插入FIFO队列尾部，数据在FIFO队列中顺序移动；