SparseArray 源码解析

LruCache 是什么东西？

LRU 咋一看这么熟悉，操作系统里面内存管理，页面置换时替换算法之一，英文全拼为Least Recently Used 以为最近最少使用，简单来说，就是替换掉最老的数据。其核心思想为如果数据最近被访问过，那么将来被访问的几率也更高。另外一个比较简单的算法是 FIFO，First In First Out 先进先出，就是淘汰最先使用的，也就是说留下最近使用的，看似这两个很像，实际上区别还是很大的，当缓存命中时，LRU会将元素移到队首，而FIFO不会变 我觉得这是对于 LRU 和 FIFO 比较正确的定义，就实现方式来说，FIFO 相对简单些

前世今生

// 很干净，没有父类（Object 除外）
public class LruCache<K, V> {}

使用场景

主要是用于缓存数据的场景，节约内存，比如图片的缓存

实现原理大白话

他的实现还是很简单，很清晰的，使用一个 LinkedHashMap 作为数据存储结构，你使用这个东西的时候可以当一个 Key-Value 内存数据库使用。只不过，它主要是为了缓存，当数据量达到阈值值，会根据LRU删除数据，那有的同学可能会问，为什么要删啊？其实这就是使用它原因，删掉一部分可能不使用的数据，节约出宝贵的内存，要是你不管内存的话，那就另当别论了

存储数据格式

head -> node -> node ->  node -> node -> node -> tail
node = <Key, Value>

源码分析

属性

// 数据存储
private final LinkedHashMap<K, V> map;

/** Size of this cache in units. Not necessarily the number of elements. */
private int size;
// 阈值设置，超过阈值就会抛弃
private int maxSize;
/**
  * 下面的统计数据主要是用来评估的
  */
// 调用 put 的次数
private int putCount;
// 创建 key 的次数
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;
    // 在这里初始化 cache ，默认大小为 0
    // true 这个很关键，代表 access-order，
    // true 则链表的顺序是为访问顺序，刚好符合LRU的特性
    // false 则 插入顺序 
    this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}

put 存数据

/**
 * Caches {@code value} for {@code key}. The value is moved to the head of
 * the queue.
 *
 * @return the previous value mapped by {@code key}.
 */
  public final V put(K key, V value) {
    // 注意不允许为空，HashMap 是可以允许你 Key Value 为空的
    if (key == null || value == null) {
        throw new NullPointerException("key == null || value == null");
    }

    V previous;
    // 锁住自身的对象，线程安全
    synchronized (this) {
        putCount++;
        // 计算存入数据的大小
        size += safeSizeOf(key, value);
        // 存入数据，如果 key 重复，则返回旧数据
        // 具体实现可查看 HashMap 的putVal函数
        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;
}

调整大小函数

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;
              }

              // remove the head
              // head -> next -> next -> tail
              // 获取队首数据
              Map.Entry<K, V> toEvict = map.eldest();
              if (toEvict == null) {
                  break;
              }

              key = toEvict.getKey();
              value = toEvict.getValue();
              // 删除
              map.remove(key);
              // 减小
              size -= safeSizeOf(key, value);
              // 擦除加1
              evictionCount++;
          }
          // 可重写，监听清除
          entryRemoved(true, key, value, null);
      }
  }

get 刚开始的时候你可能会困惑，说好的 lru 怎么没看到

public final V get(K key) {
        if (key == null) {
            throw new NullPointerException("key == null");
        }

        V mapValue;
        synchronized (this) {
            // 拿到数据直接返回了
            // 更换节点的工作，LinkedHashMap 帮我们做了
            mapValue = map.get(key);
            if (mapValue != null) {
                hitCount++;
                return mapValue;
            }
            missCount++;
        }

        /*
         * Attempt to create a value. This may take a long time, and the map
         * may be different when create() returns. If a conflicting value was
         * added to the map while create() was working, we leave that value in
         * the map and release the created value.
         */
        // 缓存失效
        // 或者不存在key，同样 create 也是空方法，使用者根据自己需求去实现
        V createdValue = create(key);
        if (createdValue == null) {
            return null;
        }
        // 就是一个 put 操作
        synchronized (this) {
            createCount++;
            mapValue = map.put(key, createdValue);

            if (mapValue != null) {
                // There was a conflict so undo that last put
                map.put(key, mapValue);
            } else {
                size += safeSizeOf(key, createdValue);
            }
        }

        if (mapValue != null) {
            entryRemoved(false, key, createdValue, mapValue);
            return mapValue;
        } else {
            trimToSize(maxSize);
            return createdValue;
        }
    }

看完这几个函数，大概知道了原理

再来看一个非常重要的函数，内存大小的计算，通常也是需要使用者自己重写

private int safeSizeOf(K key, V value) {
    int result = sizeOf(key, value);
    if (result < 0) {
        throw new IllegalStateException("Negative size: " + key + "=" + value);
    }
    return result;
}

/**
 * Returns the size of the entry for {@code key} and {@code value} in
 * user-defined units.  The default implementation returns 1 so that size
 * is the number of entries and max size is the maximum number of entries.
 *
 * <p>An entry's size must not change while it is in the cache.
 */
// 子类可重写，默认返回1，根据使用情况自己计算
// 扯一句，关于 Java 对象在内存的大小如何计算，请自行去查找
protected int sizeOf(K key, V value) {
    return 1;
}

总结

HashMap 是个很重要的东西，下一次我们在慢慢分析
今天跟大家分享了一个很简单的数据结构，也是你可以效仿的对象，还是那句，Read the fucking source code

纯属个人观点，如果有错，欢迎指正。