Lru算法之LruCache

Lru算法（Least recently used，最近最少使用），其思想核心是最新操作（添加、读取）的数据，使用频率最高。

算法原理

算法原理图

通常实现是通过链表结构实现

• 链表头部写入数据
• 如果当前缓存数量大于最大缓存书，则删除链表尾部数据
• 读取缓存数据时将该数据移动到链表顶部

LruCache实现

内部数据结构

LruCache 内部创建一个LinkedHashMap永存存数缓存数据，为什么要使用这个类呢？

• LinkedHashMap构造函数
  public LinkedHashMap(int initialCapacity, float loadFactor,boolean accessOrder)
  • initialCapacity 容量
  • loadFactor 容量不足时，扩容倍数
  • accessOrder false还是基于插入 顺寻排序ture基于访问顺序
    LruCache显然是基于访问顺序排序

• 内部数据结构
  内部实现采用LinkedHashMapEntry实现双链表结构，可以记录添加顺序，新增数据添加到双链表的尾部

• 添加和读取数据
  执行get和put方法的，条件满足是都会会调用this.recordAccess方法（LinkedHashMap重写了recordAccess方法），以保证访问顺序排序，会将数据插入或者移动到链表的尾部

• 遍历顺序
  LinkedHashMap遍历顺序是从头到尾，这样可以保证删除最老的数据

好像与上面的原理图并不一样，不过是添加数据的时候添加到链表尾部，遍历的时候从尾到头遍历实际上效果还是一样的

核心代码

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 || map.isEmpty()) {
                    break;
                }
                //当前缓存已缓存数量大于最大缓存数，遍历获取map中第一个
                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);
        }
    }