从面试题《设计图片缓存框架》来看缓存和Bitmap的优化

作者: Marco黑八 | 来源:发表于2018-06-03 16:17 被阅读0次

近日看到安卓群里探讨了两个问题，一个是Leakcanary的实现原理，一个是图片缓存框架设计。看了大佬们的讨论瞬间觉得这两者有藕断丝连的关系，借着这个机会也学习并总结一下。

本文主要从以下几点分别进行总结，先整理一些必要的先行知识，最后贴上自己图片缓存框架的设计类图

LruCache实现原理
内存的回收及引用
Bitmap的优化
Leakcanary原理
图片缓存框架的设计

LruCache实现原理

谈到图片缓存，可能首先大家想到的是内存缓存，关于内存缓存的方式多种多样，这里主要探讨利用LruCache实现缓存的方法及原理。

打开LruCache的源码会发现LruCache本质上是对LinkedHashMap进行了一层封装。

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

那为什么利用LinkedHashMap就能巧妙的实现Least recently used（最近最少使用算法）？

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
{
    /**
     * The head of the doubly linked list.
     */
    private transient LinkedHashMapEntry<K,V> header;

    public V get(Object key) {
        LinkedHashMapEntry<K,V> e = (LinkedHashMapEntry<K,V>)getEntry(key);
        if (e == null)
            return null;
        e.recordAccess(this);
        return e.value;
    }
       /**
     * LinkedHashMap entry.
     */
    private static class LinkedHashMapEntry<K,V> extends HashMapEntry<K,V> {
        // These fields comprise the doubly linked list used for iteration.
        LinkedHashMapEntry<K,V> before, after;

        LinkedHashMapEntry(int hash, K key, V value, HashMapEntry<K,V> next) {
            super(hash, key, value, next);
        }

        /**
         * Removes this entry from the linked list.
         */
        private void remove() {
            before.after = after;
            after.before = before;
        }

        /**
         * Inserts this entry before the specified existing entry in the list.
         */
        private void addBefore(LinkedHashMapEntry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

        /**
         * This method is invoked by the superclass whenever the value
         * of a pre-existing entry is read by Map.get or modified by Map.set.
         * If the enclosing Map is access-ordered, it moves the entry
         * to the end of the list; otherwise, it does nothing.
         */
        void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if (lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }
        //...
    }
    
 }

先来看看LinkedHashMap如何实现的，其本质就是一个双向链表。HashMap的优势在于随机访问速度快，而LinkedHashMap在其之上进行扩展，使其具有了有序性。

首先可以看到LinkedHashMap继承自HashMap，并且LinkedHashMapEntry继承自HashMapEntry，在LinkedHashMap内部会存储一个名为header的头指针。同时注意get方法中调用了recordAccess方法，下文会提到该方法。

image

对于一个容器的使用，无外乎增删改查，那我们从put方法来看看这个LinkedHashMap干了些什么。在LinkedHashMap中，并没有put方法，该方法继承自父类HashMap，看一下该方法。

    public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
        int i = indexFor(hash, table.length);
        for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);//此处会调用到HashMapEntry的recordAccess方法
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

可以看到，如果节点不存在则添加节点，如果节点存在在修改值之后会调用到recordAccess方法，而这个方法由子类LinkedHashMapEntry重写。再次贴上几个关键方法的实现。

        /**
         * Removes this entry from the linked list.
         */
        private void remove() {
            before.after = after;
            after.before = before;
        }

        /**
         * Inserts this entry before the specified existing entry in the list.
         */
        private void addBefore(LinkedHashMapEntry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

        /**
         * This method is invoked by the superclass whenever the value
         * of a pre-existing entry is read by Map.get or modified by Map.set.
         * If the enclosing Map is access-ordered, it moves the entry
         * to the end of the list; otherwise, it does nothing.
         */
        void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if (lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }

可以看到这段逻辑中先后调用了remove和addBefore方法。remove方法用于将节点从链表中删除，并连接删除节点的前后节点。addBefore方法则用于将这个节点置于整个双向链表的表头。get、remove方法也采用类似的方式实现。

就是说每一次你访问数据的时候，都会将节点置于整个双向链表的表头。将最近使用的节点置于链表前面，链表末端自然是很久没访问的节点。这样也就实现了LruCache算法。

内存中的引用类型

关于引用类型主要列出强、软、弱、虚四种引用类型的特征，并且介绍一下api，这里就不探讨虚拟机回收的问题了。

引用类型		特征
强引用	StrongReference	不会回收
软引用	SoftReference	当内存不足时会回收
弱引用	WeakReference	当发生gc的时候会回收
虚引用	PhantomReference	任何时候都会被回收

WeakReference和SoftReference都继承自Reference，这个类有两个构造方法。以软引用的构造方法为例，public SoftReference(T referent, ReferenceQueue<? super T> q)。第二个参数传入引用队列，当软引用或弱引用被回收的时候，会把这个软引用或弱引用加入引用队列。LeakCanary就是利用了这个特点，思想类似于设置一个回收成功的监听。

public abstract class Reference<T> {
    /* -- Constructors -- */

    Reference(T referent) {
        this(referent, null);
    }

    Reference(T referent, ReferenceQueue<? super T> queue) {
        this.referent = referent;
        this.queue = queue;
    }
}

Bitmap的优化

内存大小计算

内存大小计算公式 = 宽 * 高 * 单位像素所占字节数

配置	单位像素所占字节数
ARGB_8888	4
ARGB_4444	2
RGB_565	2

Bitmap加载到内存中的大小，与图片文件大小无关，与图片格式无关，只与图片的分辨率有关。而图片加载到内存中的尺寸与像素密度有关，这个像素密度会根据drawable的目录变化而变化。

	inDensity值
drawable-ldpi	120
drawable-mdpi	160
drawable-hdpi	240
drawable-xhdpi	320
drawable-xxhdpi	480

PS:以1.5倍递增

图片压缩及内存复用

通常把资源加载到内存，都会进行压缩，当图片本身的尺寸超过显示控件的尺寸时，加载过大的图片也会浪费内存。关于压缩很常见了，以下代码还提供了内存复用。还可以增加一个alpha通道的标志位，如果不需要alpha通道将图片格式设置为options.inPreferredConfig = Bitmap.Config.RGB_565;即可。

    public static Bitmap resizeBitmap(Resources resources, int id, int toW, int toH) {
        return resizeBitmap(resources, id, toW, toH, null);
    }

    public static Bitmap resizeBitmap(Resources resources, int id, int toW, int toH, Bitmap reusable) {
        BitmapFactory.Options options = new BitmapFactory.Options();
        options.inJustDecodeBounds = true;
        BitmapFactory.decodeResource(resources, id, options);
        int fromW = options.outWidth;
        int fromH = options.outHeight;
        options.inSampleSize = calculateInSampleSize(fromW, fromH, toW, toH);
        options.inJustDecodeBounds = false;
        if (reusable != null) {
            options.inMutable = true;//是否复用内存
            options.inBitmap = reusable;//复用内存
        }
        return BitmapFactory.decodeResource(resources, id, options);
    }

    public static int calculateInSampleSize(int fromW, int fromH, int toW, int toH) {
        int inSampleSize = 1;
        while (fromW > toW && fromH > toH) {
            inSampleSize *= 2;
            fromW /= inSampleSize;
            fromH /= inSampleSize;
        }
        return inSampleSize;
    }

关于内存复用，存在版本兼容问题，在此做个总结

Android 4.4之前版本(api < 19)

4.4之前的版本图片格式只有jpg和png，必须同等宽高且inSampleSize为1才可以复用bitmap。且被复用的Bitmap#inPreferredConfig会覆盖新设置待分配内存的Bitmap#inPreferredConfig

Android 4.4及之后版本(api >= 19)

复用的Bitmap的内存必须大于等于待分配内存的Bitmap

getByteCount 和 getAllocationByteCount的区别

如果被复用的Bitmap比待分配内存的Bitmap要大，那么getByteCount表示待分配内存的大小，实际大小可能更大。getAllocationByteCount表示被复用的Bitmap的大小。

Leakcanary监控泄漏原理

先看一下监控的工作机制，转载自LeakCanary 中文使用说明。

RefWatcher.watch() 创建一个 KeyedWeakReference 到要被监控的对象。
然后在后台线程检查引用是否被清除，如果没有，调用GC。

  /**
   * Watches the provided references and checks if it can be GCed. This method is non blocking,
   * the check is done on the {@link Executor} this {@link RefWatcher} has been constructed with.
   *
   * @param referenceName An logical identifier for the watched object.
   */
  public void watch(Object watchedReference, String referenceName) {
    checkNotNull(watchedReference, "watchedReference");
    checkNotNull(referenceName, "referenceName");
    if (debuggerControl.isDebuggerAttached()) {
      return;
    }
    final long watchStartNanoTime = System.nanoTime();
    String key = UUID.randomUUID().toString();
    retainedKeys.add(key);
    final KeyedWeakReference reference =
        new KeyedWeakReference(watchedReference, key, referenceName, queue);

    watchExecutor.execute(new Runnable() {
      @Override public void run() {
        ensureGone(reference, watchStartNanoTime);
      }
    });
  }

  void ensureGone(KeyedWeakReference reference, long watchStartNanoTime) {
    long gcStartNanoTime = System.nanoTime();

    long watchDurationMs = NANOSECONDS.toMillis(gcStartNanoTime - watchStartNanoTime);
    removeWeaklyReachableReferences();
    if (gone(reference) || debuggerControl.isDebuggerAttached()) {
      return;
    }
    gcTrigger.runGc();
    removeWeaklyReachableReferences();
    if (!gone(reference)) {
      long startDumpHeap = System.nanoTime();
      long gcDurationMs = NANOSECONDS.toMillis(startDumpHeap - gcStartNanoTime);

      File heapDumpFile = heapDumper.dumpHeap();

      if (heapDumpFile == null) {
        // Could not dump the heap, abort.
        return;
      }
      long heapDumpDurationMs = NANOSECONDS.toMillis(System.nanoTime() - startDumpHeap);
      heapdumpListener.analyze(
          new HeapDump(heapDumpFile, reference.key, reference.name, watchDurationMs, gcDurationMs,
              heapDumpDurationMs));
    }
  }

每个KeyedWeakReference都和一个唯一的UUID映射，RefWatcher内部通过Set<String> retainedKeys保存所有弱引用的UUID。

watchExecutor对象是一个AndroidWatchExecutor实例，其会利用IdleHandler在主线程空闲的时候向后台线程发送一个延迟消息，检查该弱引用是否被清除。首先要明白如果该弱引用被清除了，会被加入到引用队列中。所以检测步骤如下

循环该队列并清除映射表中对应的UUID
利用UUID检查该弱引用是否存在，如果存在触发GC。如果不存在表明清除成功。
触发GC后，再次循环队列清除UUID
如果引用依然没清除，表明内存泄漏，进行分析

  private boolean gone(KeyedWeakReference reference) {
    return !retainedKeys.contains(reference.key);
  }

  private void removeWeaklyReachableReferences() {
    // WeakReferences are enqueued as soon as the object to which they point to becomes weakly
    // reachable. This is before finalization or garbage collection has actually happened.
    KeyedWeakReference ref;
    while ((ref = (KeyedWeakReference) queue.poll()) != null) {
      retainedKeys.remove(ref.key);
    }
  }

所以LeakCanary其实就是为检测对象生成一个弱引用，利用弱引用发生gc时会被回收，且被回收后会加入引用队列中的特点，来检测是否发生了内存泄漏。

图片缓存框架的设计

上一下整体设计的类图、流程图、时序图，画的比较生疏，可能存在错误。代码已经传到Github了，这里就不贴了，里面的技术点基本就是上面整理的。框架的健壮性和设计还有待提高，功能也并不完善，不足之处希望大佬指出。

业务流程图

业务流程

缓存框架类图

缓存框架类图

缓存时序图

缓存时序图

从面试题《设计图片缓存框架》来看缓存和Bitmap的优化

LruCache实现原理

内存中的引用类型

Bitmap的优化

内存大小计算

图片压缩及内存复用

Leakcanary监控泄漏原理

图片缓存框架的设计

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

Android开发