看看人家 - Glide的LruCache

在android领域，glide是一个非常优秀的图片加载框架，优秀自然有优秀的道理，看github的star你会发现它非常受欢迎，今天有空来看看Glide中LruCache的实现，源码阅读我还是坚持这个原则：不着急关注细节，先抽取骨架，再薅皮毛

我们在使用LRU之类的实现框架的时候，这四个方法基本概况了所有日常，加锁的原因是为了保证线程安全和数据一致。

public class LruCache {
	
	
	public synchronized boolean contains(T key);

	
	public synchronized Y get(T key);
	
	
	public synchronized Y put(T key, Y item);

	
	public synchronized Y remove(T key);
	
}

我们都知道LRU大部分都使用链表这个基本数据结构来实现，但是链表的访问效率又不理想，使用linkedHasmap是个不错的选择，我们来看下LruCache的定义。

public class LruCache {
	
  private final Map> cache = new linkedHashMap<>(100, 0.75f, true);
  private final long initialMaxSize;
  private long maxSize;
  private long currentSize;
...

使用linkedHasmap兼顾了插入，删除，访问的效率。那么我们接下来观察一下细节，先看一下put的实现。

put分两种情况，一种是key不存在，是添加；另一种是key已经存在，就替换。

  public synchronized Y put(@NonNull T key, @Nullable Y item) {
  	//itemSize始终为1
    final int itemSize = getSize(item);
    //边界处理，我们的LruCache容量初始化的时候不能为1
    if (itemSize >= maxSize) {
    	//这个onItemEvicted方法，源码解释是一个回调，子类可以复写得到一个驱逐通知
      onItemEvicted(key, item);
      return null;
    }
	//当前容量+1
    if (item != null) {
      currentSize += itemSize;
    }
    //把item保存到linkedhasmap
    @Nullable Entry old = cache.put(key, item == null ? null : new Entry<>(item, itemSize));
    //old不为null，说明之前有相同key的item存在，这次put是替换了，
    if (old != null) {
      currentSize -= old.size;//所有size都是1，这里就是减1，currentSize和linkedhasmap的size应该是保持一致的。

      if (!old.value.equals(item)) {//之前的old和这次put的数据，key相同，value不一样
        onItemEvicted(key, old.value);//告诉子类，old被驱逐了
      }
    }
    evict();//这个稍后再看。

    return old != null ? old.value : null;
  }

就直接从linkedhasmap里面取了，好奇怪，为啥没有LRU算法的实现，最近使用的应该有一个移动操作才对，先不急，后面再说。

  public synchronized Y get(@NonNull T key) {
    Entry entry = cache.get(key);
    return entry != null ? entry.value : null;
  }

也基本是一个单纯的linkedhasmap的操作

  public synchronized Y remove(@NonNull T key) {
    Entry entry = cache.remove(key);
    if (entry == null) {
      return null;
    }
    currentSize -= entry.size;
    return entry.value;
  }

可以看到put，get，remove都基本是用linkedhasmap的api，那么我认为是linkedhasmap负责了链表数据的调整。所以要看一下它源码。

linkedHasmap 继承Hasmap，我们首先在Hasmap中找到了蛛丝马迹。

    // Callbacks to allow linkedHashMap post-actions
    void afterNodeAccess(Node p) { }//节点被访问之后调用了此方法
    void afterNodeInsertion(boolean evict) { }//节点被插入之后调用了此方法
    void afterNodeRemoval(Node p) { }//节点被移除之后调用了此方法

Hasmap并没有实现这三个方法，注释说的很明白了，保留给linkedHashMap来扩展，那么就可以看下linkedHashMap是怎么实现的。

节点访问后

	 
    void afterNodeAccess(Node e) { // move node to last
        linkedHashMapEntry last;
        if (accessOrder && (last = tail) != e) {
            linkedHashMapEntry p =
                (linkedHashMapEntry)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }

节点删除后

    void afterNodeRemoval(Node e) { // unlink
        linkedHashMapEntry p =
            (linkedHashMapEntry)e, b = p.before, a = p.after;
        p.before = p.after = null;//前后指针断开
        if (b == null)//如果原本是头节点，直接删除头节点
            head = a;
        else
            b.after = a;//b后驱指向a，稍后再把a前驱指向b,即可删除p
        if (a == null)//如果原本是尾节点，把前驱当尾节点接口删除p
            tail = b;
        else 
            a.before = b;//a前驱指向b完成重建
    }

新增节点后，要不要删除头节点，头节点其实就是旧节点。要不要删除？就要看removeEldestEntry的返回值

    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        linkedHashMapEntry first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }

linkedHashMap的removeEldestEntry默认返回false，就是说，每次插入不会主动删除最旧的数据。

 protected boolean removeEldestEntry(Map.Entry eldest) {
        return false;
    }

其实LRU应该要删除才对，那么复写这个方法，返回true就可以了，但是Glide的作者没有这么做。那么他是怎么删除旧数据的呢？还记得 LruCache 中 evict() 这个方法吗？

  
  protected synchronized void trimToSize(long size) {
    Map.Entry> last;
    Iterator>> cacheIterator;
    while (currentSize > size) {
      cacheIterator = cache.entrySet().iterator();
      last = cacheIterator.next();
      final Entry toRemove = last.getValue();
      currentSize -= toRemove.size;
      final T key = last.getKey();
      cacheIterator.remove();
      onItemEvicted(key, toRemove.value);
    }
  }

  private void evict() {
    trimToSize(maxSize);
  }

对，自己选择了手动管理，当超过maxSize的时候，就遍历linkedHashMap找到最旧的数据，也就是链表头节点，进行删除。

今天关注了一下Glide内部LruCache的实现细节，可以看出并没有太深奥的东西，源码也比较简洁，总共就208行，但同时也感叹这么一个简单的lru组件，居然也可以把单元测试写的那么完善，也是自己和人家的差距体现吧。

Glide都在用的LruCache，你学会了吗？

HashMap中afterNodeInsertion方法有什么作用呢

关于linkedHashMap中accessOrder属性的理解