谈谈LruCache算法的底层实现原理及其内部源码-白红宇

前言

我们在对数据进行操作的时候，为了避免流量或者性能的消耗，我们对于一些数据都会进行缓存处理，而对数据的缓存的要点不仅仅只有我们所熟悉的存储缓存和使用缓存，还有删除缓存。对于添加和获取缓存很好理解，那么为什么还要对缓存进行删除呐？原因很简单，因为我们的手机容量是有限的，如果我们拼命的写入缓存，那么终有一天内存会满导致程序奔溃，这显然不是我们想要的结果，于是我们在写入缓存的时候并非无脑写入，而是在写入之前会对内存空间进行一次判断，如果内存不足了，那么就移除掉一些缓存数据，从而达到内存不会爆掉的状态。

LruCache算法

根据上面所说的思想，android系统内部帮我们写了一个API——LruCache，来帮我们处理一些缓存。

LruCache（Least Recently Used）算法的核心思想就是最近最少使用算法。他在算法的内部维护了一个LinkHashMap的链表，通过put数据的时候判断是否内存已经满了，如果满了，则将最近最少使用的数据给剔除掉，从而达到内存不会爆满的状态。这么讲可能有些抽象，我从网上找了一张图来解释这个算法。

通过上面这张图，我们可以看到，LruCache算法内部其实是一个队列的形式在存储数据，先进来的数据放在队列的尾部，后进来的数据放在队列头部，如果要使用队列中的数据，那么使得之后将其又放在队列的头部，如果要存储数据并且发现数据已经满了，那么便将队列尾部的数据给剔除掉，从而达到我们使用缓存的目的。这里需要注意一点，队尾存储的数据就是我们最近最少使用的数据，也就是我们在内存满的时候需要剔除掉的数据。

这里有一个疑问，为什么LruCache内部原理的实现需要用到LinkHashMap来存储数据呐？

因为LinkHashMap内部是一个数组加双向链表的形式来存储数据，他能够保证插入时候的数据和取出来的时候数据的顺序的一致性。也就是说，我们以什么样的顺序插入数据，就会以什么样的顺序取出数据。并且更重要的一点是，当我们通过get方法获取数据的时候，这个获取的数据会从队列中跑到队列头来，从而很好的满足我们LruCache的算法设计思想。

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:03:34:45:56:61:12:2复制代码

可以看到，我们在插入的时候是0,1,2,3,4,5,6的形式插入的，然后调用get方法将1,2取出来。最后遍历LinkHashMap，发现最先出来的数据变成了2和1，其余的数据都在这两个数据之后取出来，这就达到了我们想要的结果和目的。

LruCache算法的使用

Bitmap bitmap = null;        //获取运行内存大小的八分之一        int memory = (int)Runtime.getRuntime().totalMemory() / 1024;        int cache = memory / 8;        bitmap = BitmapFactory.decodeResource(getResources(),R.mipmap.ic_launcher);        LruCache
    
      lruCache = new LruCache
     
      (cache){            @Override            protected int sizeOf(String key, Bitmap bitmap) {                return bitmap.getRowBytes() * bitmap.getHeight() / 1024;            }        };        //将数据存储进入缓存        lruCache.put("cacheBitmap",bitmap);         Bitmap cacheBitmap = lruCache.get("cacheBitmap");        //在使用的时候判断是否图片为空，因为有可能图片因为内存空间满了而被剔除        if (cacheBitmap != null){            //TODO        }复制代码

我们在使用LruCache算法的时候，首先会对其分配一下内存空间。一般情况下我们都是使用运行内存的八分之一作为内存空间来存储数据。之后实例化LruCache，覆写里面的一个方法sizeOf，里面返回的为你存储进入缓存的每一个数据的大小。注意，此处的单位必须和你一开始分配的内存空间大小的单位保持一致。

这里需要说一个题外话，我们如何获取一个bitmap的内存大小？获取bitmap内存大小的方式有两种，一种为 bitmap的高(bitmap.getHeight()，或者可以说为行数) * bitmap所占的字节数(bitmap.getRowByte()) 来获取，另外一种为直接调用bitmap.getByteCount()来获取。那么这两个有什么区别呐？其实区别就是bitmap.getRowByte()所支持的版本更低，而bitmap.getByteCount()内存的实现其实就是bitmap.getRowByte() * bitmap.getHeight()；

public final int getByteCount() {        // int result permits bitmaps up to 46,340 x 46,340        return getRowBytes() * getHeight();    }复制代码

初始化完成LruCache对象之后，我们通过put方法将需要进行缓存的数据通过key和value的形式放入分配的内存中，之后需要使用的时候再通过get方法用key找到我们缓存的对象。不过这里需要注意一点，我们在获取到我们的缓存对象之后，不要急着去使用他，而是去先进行一次非空判断，因为有可能图片因为内存空间不足而被剔除掉。

LruCache算法源码解析

分析完了上面的内部原理和使用注意事项之后，我们再来通过源码来加深一下对LruCache算法的理解。

我们先看下LruCache算法的构造方法。

public LruCache(int maxSize) {        if (maxSize <= 0) {            throw new IllegalArgumentException("maxSize <= 0");        }        this.maxSize = maxSize;        this.map = new LinkedHashMap
    
     (0, 0.75f, true);    }    复制代码

从构造方法的源码我们可以看到，在这端代码中我们主要做了两件事。第一是判断下传递来的最大分配内存大小是否小于零，如果小于零则抛出异常，因为我们如果传入一个小于零的内存大小就没有意义了。之后在构造方法内存就new了一个LinkHashMap集合，从而得知LruCache内部实现原理果然是基于LinkHashMap来实现的。

之后我们再来看下存储缓存的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) {            putCount++;            size += safeSizeOf(key, value);            previous = map.put(key, value);            if (previous != null) {                size -= safeSizeOf(key, previous);            }        }         if (previous != null) {            entryRemoved(false, key, previous, value);        }         trimToSize(maxSize);        return previous;    }复制代码

从代码中我们可以看到，这个put方法内部其实没有做什么很特别的操作，就是对数据进行了一次插入操作。但是我们注意到最后的倒数第三行有一个 trimToSize() 方法，那么这个方法是做什么用的呐？我们点进去看下。

public void trimToSize(int maxSize) {        while (true) {            K key;            V value;            synchronized (this) {                if (size < 0 || (map.isEmpty() && size != 0)) {                    throw new IllegalStateException(getClass().getName()                            + ".sizeOf() is reporting inconsistent results!");                }                 if (size <= maxSize) {                    break;                }                 Map.Entry
    
      toEvict = map.eldest();                if (toEvict == null) {                    break;                }                 key = toEvict.getKey();                value = toEvict.getValue();                map.remove(key);                size -= safeSizeOf(key, value);                evictionCount++;            }             entryRemoved(true, key, value, null);        }    }复制代码

我们可以看到，这个方法原来就是对内存做了一次判断，如果发现内存已经满了，那么就调用map.eldest()方法获取到最后的数据，之后调用map.remove(key)方法，将这个最近最少使用的数据给剔除掉，从而达到我们内存不炸掉的目的。

我们再来看看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++;        }复制代码

get方法看起来就是很常规的操作了，就是通过key来查找value的操作，我们再来看看LinkHashMap的中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()方法获得对应集合元素，同时会更新该元素到队头。