LRU Cache理解

LRU Cache

1. 概念解析，LRU Cache算法

1. Lru Cache算法就是Least Recently Used，按照字面意思就是最近最少使用，用这种算法来实现缓存就比较合适了，当缓存满了的时候，不经常使用的就直接删除，挪出空间来缓存新的对象；
2. 实现缓存的最关键的操作就是，添加和读取以及删除等操作了
3. LRU 实现使用LinkedHashMap永久的缓存数据，那为什么要用这个呢？
   1. LinkedHashMap是双向列表实现的，刚好在内部具有排序的功能，内部的accessorder代表了两种模式，插入模式和访问模式，false为访问模式按照顺序来实现（默认就是false），所以按照此种思路，则链表的最后段就是最少使用的缓存，比较方便来实现；
   2. LinkedHashMap是双向循环列表来实现，默认容量大小16、负载因子0.75以及按照插入顺序排序，不用我们管理扩容等问题；
   3. 添加和读取数据：保证访问顺序排序，会将数据插入或者移动到链表的尾部，而且链表的删除和增加速度比较快；
   4. LinkedHashMap遍历顺序是从头到尾，这样可以保证删除最老的数据；

2. LRU cache的简单使用

    int maxMemory = (int) (Runtime.getRuntime().totalMemory()/1024);
    int cacheSize = maxMemory/8;
    mMemoryCache = new LruCache<String,Bitmap>(cacheSize){
        @Override
        protected int sizeOf(String key, Bitmap value) {
            return value.getRowBytes()*value.getHeight()/1024;
        }
    };

1. 获取到当前虚拟机的最大内存值，然后取1/8来当缓存；
2. 注意单位的一致性sizeof（）和cacheSize的单位要一直，上面为kb；
3. sizeOf()是为了计算缓存对象大小的计算；
4. 使用的时候你就可以当做一个map去使用就好了，只不过自动添加了扩容，缓存，以及帮你防止OOM的情况；

3. LRU Cache源码解析

1. 分析源码主要从几个方面来分析，创建，存取，删除这三个方面来：

2. 创建：

    public class LruCache<K, V> {
    private final LinkedHashMap<K, V> map;
    /** Size of this cache in units. Not necessarily the number of elements. */
    private int size;
    private int maxSize;
   
    private int putCount;
    private int createCount;
    private int evictionCount;
    private int hitCount;
    private int missCount;
   
   
    public LruCache(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("maxSize <= 0");
        }
        this.maxSize = maxSize;
        this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
    }
   
    }
   

   构建特别简单，相当于创建了一个LinkedHashMap；

3. put方法是把内容放入到缓存中去

    //给对应key缓存value，该value将被移动到队头。
    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,记录 put 的次数
        putCount++;
        //增加已有缓存的大小,拿到键值对，计算出在容量中的相对长度，然后加上
        size += safeSizeOf(key, value);
       //向map中加入缓存对象,如果 之前存在key 则返回 之前key 的value,记录在 previous
        previous = map.put(key, value);
        //如果已有缓存对象，则缓存大小恢复到之前
        if (previous != null) {
            //   // 计算出 冲突键值 在容量中的相对长度，然后减去
            size -= safeSizeOf(key, previous);
        }
    }
    //entryRemoved()是个空方法，可以自行实现,如果上面发生冲突
    if (previous != null) {
    //previous值被剔除了，此次添加的 value 已经作为key的 新值,告诉 自定义 的 entryRemoved 方法
        entryRemoved(false, key, previous, value);
    }
    //调整缓存大小
    trimToSize(maxSize);
    return previous;
    }
   
   
     /*
     * 这是一个死循环，
     * 1.只有 扩容 的情况下能立即跳出
     * 2.非扩容的情况下，map的数据会一个一个删除，直到map里没有值了，就会跳出
     */
   
    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!");
                    }
                    // 如果是 扩容 或者 map为空了，就会中断，因为扩容不会涉及到丢弃数据的情况
                    //如果缓存大小size小于最大缓存，或者map为空，不需要再删除缓存对象，跳出循环
                    if (size <= maxSize || map.isEmpty()) {
                        break;
                    }
                    //迭代器获取第一个对象，即队尾的元素，近期最少访问的元素
                    Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
                    key = toEvict.getKey();
                    value = toEvict.getValue();
                    //删除该对象，并更新缓存大小
                    map.remove(key);
                     // 拿到键值对，计算出在容量中的相对长度，然后减去。
                    size -= safeSizeOf(key, value);
                    evictionCount++;
                }
                    //将最后一次删除的最少访问数据回调出去
                entryRemoved(true, key, value, null);
            }
        }
   

   put方法比较简单只是把对象存储，然后关键的方法是trimToSize()，调整缓存的，如果满了就删除然后更新

4. get获取缓存

    public final V get(K key) {
    //key为空抛出异常
    if (key == null) {
        throw new NullPointerException("key == null");
    }

    V mapValue;
    synchronized (this) {
        //获取对应的缓存对象
        //get()方法会实现将访问的元素更新到队列头部的功能,LinkHashMap 如果设置按照访问顺序的话，这里每次get都会重整数据顺序
        mapValue = map.get(key);
        if (mapValue != null) {
            hitCount++;
            return mapValue;
        }
        missCount++;
    }

    void recordAccess(HashMap<K,V> m) {
                LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
                //判断是否是访问排序
                if (lm.accessOrder) {
                    lm.modCount++;
                    //删除此元素
                    remove();
                    //将此元素移动到队列的头部
                    addBefore(lm.header);
                }
            }

5. 总结：
   1. LRUcache的源码相对简单，只要理解LinkedHashMap的原理，这个是非常简单的实现；关键代码是trimSize方法，每次添加完成之后调整缓存大小，get方法的也是调用的LinkedHashMap的get然后通过recordAcess来调整顺序；

带注释的LruCache
LruCache原理和用法与LinkedHashMap
LruCache 解析