catalog.png

一. 概述

有时候 UI 卡顿是因为发生了频繁的 GC 造成的，频繁的 GC 其实对应的内存情况就是内存抖动，而发生内存抖动一般都是因为在循环里面或者频繁被调用的方法（比如 View.onDraw() 方法）里面创建对象造成的，面对这种情况，一般有两种做法：

1. 避免在循环里面或者频繁被调用的方法里面创建对象，在循环或者被频繁调用的方法之外创建对象
2. 使用对象池缓存对象，在使用对象的时候，直接从对象池中取对象即可，避免频繁的创建对象

一般来讲，实现对象池有三种方法，对应的具体的数据结构即是数组、链表和 Map，下面我将通过示例分别介绍通过这三种数据结构实现的对象池

二. 对象池的实现

2.1 通过数组实现

在 Android 的 v4 包中有个类 Pools，其中定义了一个对象池接口 Pool<T>，具体的实现有两个 SimplePool<T> 和 SynchronizedPool<T>，这两个实现顾名思义，一个是非线程安全的，另一个是线程安全的。
Pools 类总共代码也不长，加上注释不到 200 行，接下来看下代码

2.1.1 接口定义

首先是 Pool<T> 接口定义，代码不难，如下所示，只有两个方法 acquire() 和 release(@NonNull T instance) 方法

• acquire()：从对象池中取一个对象，注意：有可能会返回 null
• release(@NonNull T instance)：将一个对象释放到对象池中，return true 表示对象成功放到对象池中了，return false 表示对象没有成功地放到对象池中，如果参数对象 instance 已经在对象池中，则会抛出 IllegalStateException 异常
• Note：如果一味的只从对象池中获取对象（调用 acquire()），而不向对象池中放入对象（调用release(@NonNull T instance)），那么通过 acquire() 得到的对象，有可能为 null，也有可能是 new 出来的，并没有达到缓存对象的目的，所以在使用完对象以后，要调用 release(@NonNull T instance) 及时地将对象释放到对象池中国

    /**
     * Interface for managing a pool of objects.
     *
     * @param <T> The pooled type.
     */
    public interface Pool<T> {

        /**
         * @return An instance from the pool if such, null otherwise.
         */
        @Nullable
        T acquire();

        /**
         * Release an instance to the pool.
         *
         * @param instance The instance to release.
         * @return Whether the instance was put in the pool.
         *
         * @throws IllegalStateException If the instance is already in the pool.
         */
        boolean release(@NonNull T instance);
    }

2.1.2 非线程安全类

接下来我们看下 Pool<T> 接口的非线程安全的实现类 SimplePool<T>，代码如下
其中声明了两个类变量，数组 Object[] mPool 用于缓存对象，这也应证了我之前提到的在 Pools 中是使用数组实现对象池的；另一个变量 int mPoolSize 表示此时对象池中缓存了多少个对象
下面的 acquire() 和 release(@NonNull T instance) 方法实现也不难，我在注释中加以说明即可

    public static class SimplePool<T> implements Pool<T> {
        private final Object[] mPool;

        private int mPoolSize;

        /**
         * SimplePool 的构造方法，参数 maxPoolSize 是数组 mPool 的长度，也表示此对象池最大可以缓存多少个对象，如果 maxPoolSize <= 0 则会抛出异常
         */
        public SimplePool(int maxPoolSize) {
            if (maxPoolSize <= 0) {
                throw new IllegalArgumentException("The max pool size must be > 0");
            }
            mPool = new Object[maxPoolSize];
        }

        /**
         * acquire() 方法，首先判断此时对象池中有没有缓存的对象
         *      如果有，则从 mPool 数组中取最后一个缓存对象并返回，同时将数组最后一个引用置为 null，mPoolSize --
         *      如果没有，则直接返回 null
         */
        @Override
        @SuppressWarnings("unchecked")
        public T acquire() {
            if (mPoolSize > 0) {
                final int lastPooledIndex = mPoolSize - 1;
                T instance = (T) mPool[lastPooledIndex];
                mPool[lastPooledIndex] = null;
                mPoolSize--;
                return instance;
            }
            return null;
        }

        /**
         * release(@NonNull T instance) 方法，首先判断此对象是不是已经缓存在对象池中，如果已经在对象池中则直接抛出异常
         * 如果缓存的对象个数没有超过 mPool 数组的长度，则将对象放到 mPool 数组的最后一位，并将 mPoolSize++ return true
         * 如果缓存的对象个数超过 mPool 数组的长度，则直接 return false，参数对象 instance 也并不会放入到缓存数据 mPool 中
         */
        @Override
        public boolean release(@NonNull T instance) {
            if (isInPool(instance)) {
                throw new IllegalStateException("Already in the pool!");
            }
            if (mPoolSize < mPool.length) {
                mPool[mPoolSize] = instance;
                mPoolSize++;
                return true;
            }
            return false;
        }

        /**
         * 通过遍历数组 mPool 的方式，判断参数 instance 对象是否已经在对象池中，这个方法是 private 的，只在 release(@NonNull T instance) 方法中用到了
         */
        private boolean isInPool(@NonNull T instance) {
            for (int i = 0; i < mPoolSize; i++) {
                if (mPool[i] == instance) {
                    return true;
                }
            }
            return false;
        }
    }

2.1.3 线程安全类

线程安全的实现类是非线程安全的实现类 SimplePool<T> 的子类，只是在构造方法、acquire() 和 release(@NonNull T element) 方法中，通过 synchronized 加锁实现线程安全的，没有太多可说的，代码如下所示

    public static class SynchronizedPool<T> extends SimplePool<T> {
        private final Object mLock = new Object();

        public SynchronizedPool(int maxPoolSize) {
            super(maxPoolSize);
        }

        @Override
        public T acquire() {
            synchronized (mLock) {
                return super.acquire();
            }
        }

        @Override
        public boolean release(@NonNull T element) {
            synchronized (mLock) {
                return super.release(element);
            }
        }
    }

2.1.4 使用示例

Pools 的使用主要是通过 SimplePool<T> 和 SynchronizedPool<T> 这两个实现类使用的，使用也很简单。他们都有泛型参数 T，所以可以充当任意对象的对象池，下面以 Pools 中的注释示例代码说明

public class MyPooledClass {
    private static final SynchronizedPool<MyPooledClass> sPool = new SynchronizedPool<MyPooledClass>(10);

    public static MyPooledClass obtain() {
        MyPooledClass instance = sPool.acquire();
        return (instance != null) ? instance : new MyPooledClass();
    }

    public void recycle() {
         // Clear state if needed.
         sPool.release(this);
    }

    . . .

}

2.2 通过链表实现

上面介绍了通过数组的方式实现对象池的 Pools 类，下面接着介绍通过链表的方式实现对象池的例子 Message。

对于做 Android 开发的朋友来说，Message 类应该是很熟悉了，也都知道通过 Message.obtain() 方法是从缓存（其实就是从 Message 对象池）中获取 Message 对象的，但是这样的理解是片面的，为什么这样说呢？因为如果只是通过 Message.obtain() 得到 Message 对象，然后使用 Message 对象，用完就完了，这样的使用方式也并没有达到缓存 Message 对象的作用，正确的做法是，在使用完 Message 对象以后，还应该主动地调用 message.recycle() 方法回收 Message 对象，将 Message 对象回收进 Message 对象池中，这样以后才可以通过 Message.obtain() 继续复用这个 Message 对象。

接下来，我们就分析一下 Message 类中的对象池是如何实现的

2.2.1 Message 源码分析

首先，我们来看一下 Message 类中和 Message 对象池相关的方法和变量。

• obtain() 方法大家应该很熟悉，它的作用是通过调用 obtain() 得到一个在 Message 对象池中的 Message 对象，避免通过 new 的方式新建 Message对象。底层是通过一个单链表 sPool 对象实现的，这个 sPool 单链表和我们平时使用的单链表略有不同，不同之处在于 sPool 是在链表的头部插入和删除链表节点的，而不是在尾部

• recycle() 方法，它的作用是将 Message 对象回收进 Message 对象池，其实真正起作用的是 recycleUnchecked() 方法，在 recycleUnchecked() 开始会将 Message 中的变量复位，包括 flags = FLAG_IN_USE 以表明此对象现在正在使用中，然后同步地将此 Message 对象插入到 sPool 链表的头部，并将头节点指向此 Message 对象，最后将 sPoolSize++

• 同步是通过 sPoolSync 变量和 synchronized 实现的

• Note：其中几个关键的变量 链表 sPool、链表长度 sPoolSize 都是 static 的，表明在整个 Android 应用中共享此 Message 对象池，而且 Message 对象最大长度是 50 个

public final class Message implements Parcelable {
    ......

    /*package*/ Message next;
    private static final Object sPoolSync = new Object();
    private static Message sPool;
    private static int sPoolSize = 0;

    private static final int MAX_POOL_SIZE = 50;

    ......

    public static Message obtain() {
        synchronized (sPoolSync) {
            if (sPool != null) {
                Message m = sPool;
                sPool = m.next;
                m.next = null;
                m.flags = 0; // clear in-use flag
                sPoolSize--;
                return m;
            }
        }
        return new Message();
    }

    ......

    public void recycle() {
        if (isInUse()) {
            if (gCheckRecycle) {
                throw new IllegalStateException("This message cannot be recycled because it "
                        + "is still in use.");
            }
            return;
        }
        recycleUnchecked();
    }

    /**
     * Recycles a Message that may be in-use.
     * Used internally by the MessageQueue and Looper when disposing of queued Messages.
     */
    void recycleUnchecked() {
        // Mark the message as in use while it remains in the recycled object pool.
        // Clear out all other details.
        flags = FLAG_IN_USE;
        what = 0;
        arg1 = 0;
        arg2 = 0;
        obj = null;
        replyTo = null;
        sendingUid = -1;
        when = 0;
        target = null;
        callback = null;
        data = null;

        synchronized (sPoolSync) {
            if (sPoolSize < MAX_POOL_SIZE) {
                next = sPool;
                sPool = this;
                sPoolSize++;
            }
        }
    }
}

好了，通过链表的方式实现对象池的例子就介绍到这里，接下来接着介绍通过 Map 实现对象池的例子

2.3 Glide 中通过 Map 实现 BitmapPool

通过 Map 的方式实现对象池，这里用 Glide 中缓存 Bitmap 的 BitmapPool 说明。

大家都知道 Glide 是用于加载图片的库，提到图片肯定绕不开 Bitmap，而 Bitmap 又是吃内存的能手，所以使用 BitmapPool 缓存 Bitmap 对象，避免重复创建 Bitmap 过渡消耗内存就变得十分重要了。

先看一下 Glide 中的目录结构，如下图所示，从名字也可以看出，用红色框起来的几个类都是和 BitmapPool 相关的类，我们一一加以分析。

glide-catalog.png

2.3.1 BitmapPool 接口定义

首先看一下，BitmapPool 接口，其定义如下所示，下面有详细的注释说明

public interface BitmapPool {

  /**
   * 返回当前 BitmapPool 的最大容量，单位是 byte 字节
   */
  long getMaxSize();

  /**
   * 可以通过此方法设置一个因子，此因子会乘以最开始设置的最大容量，将结果作为新的最大容量
   * 上步计算完成以后，如果 BitmapPool 的当前实际容量比当前最大容量大，则会清除 BitampPool 中的对象，直到当前实际容量小于当前最大容量
   * Note：开发者可以通过此方法动态地、同步地调整 BitmapPool 最大容量
   */
    void setSizeMultiplier(float sizeMultiplier);

  /**
   * 将此 Bitmap 对象添加到对象池中
   * 如果符合条件，BitmapPool 会修改并重用，否则会调用 Bitmap.recycle() 方法抛弃此 Bitmap 对象
   * Note：调用此方法将此 Bitmap 对象添加到对象池中以后，此 Bitmap 对象就不能再被使用了
   */  
  void put(Bitmap bitmap);

  /**
   * 通过此方法可以得到一个，width、height、config 参数都符合条件的 Bitmap，此 Bitmap 对象中只包含透明度的色值
   * 如果 BitmapPool 中没有符合此条件的 Bitmap 缓存对象，则会创建一个新的 Bitmap 对象并返回
   * Note：通过此对象得到的 Bitmap 对象，会调用 bitmap.eraseColor(Color.TRANSPARENT) 方法清除 bitmap 中所有的像素，只保留透明度像素
   *       这也是和 `getDirty(int width, int height, Bitmap.Config config)` 方法的主要区别
   */
  @NonNull
  Bitmap get(int width, int height, Bitmap.Config config);

  /**
   * 见 get(int width, int height, Bitmap.Config config) 方法注释
   */  
  @NonNull
  Bitmap getDirty(int width, int height, Bitmap.Config config);

  /**
   * 清除 BitmapPool 中的所有 Bitmap 缓存对象
   */    
  void clearMemory();

  /**
   * 根据给定的 level 参数，不同程度地清除 BitmapPool 中的大小，比如：可以清除所有的 Bitmap 缓存对象，也可以清除一半的 Bitmap 缓存对象
   */     
  void trimMemory(int level);
}

2.3.2 BitmapPool 的实现类

BitmapPool 是个接口，定义了通用的方法，在 Glide 中有两个 BitmapPool 的实现类：BitmapPoolAdapter 和 LruBitmapPool。

• BitmapPoolAdapter 类是一个空实现类，其中没有什么逻辑，对于每个添加进 BitmapPoolAdapter 缓存池的 Bitmap 都会抛弃，从 BitmapPoolAdapter 缓存池中取到的每个 Bitmap 都是新创建的。
• 这里详细分析一下 LruBitmapPool，在介绍 LruBitmapPool 之前，首先介绍另外几个类：LruPoolStrategy、Key 和 KeyPool。

2.3.2.1 LruPoolStrategy

LruPoolStrategy 是针对 LruBitmapPool 类定义的一个策略接口，其中包括一些存放、获取、移除 Bitmap 的方法，具体如下所示

• 可以看到 LruPoolStrategy 接口是没有权限修饰符的，即说明 LruPoolStrategy 只可以在 Glide 包内部使用

interface LruPoolStrategy {
  // 存放 Bitmap 对象
  void put(Bitmap bitmap);

  // 根据 width、height、config 属性获取对应的 Bitmap 对象
  @Nullable
  Bitmap get(int width, int height, Bitmap.Config config);

  // 移除最后一个 Bitmap 对象
  @Nullable
  Bitmap removeLast();

  // 获取 Bitmap 对象的用于打印的信息
  String logBitmap(Bitmap bitmap);

  // 同 logBitmap(Bitmap bitmap)
  String logBitmap(int width, int height, Bitmap.Config config);

  // 得到一个 Bitmap 对象的大小
  int getSize(Bitmap bitmap);
}

在 Glide 内部 LruPoolStrategy 接口有三个实现类，分别是 AttributeStrategy、SizeConfigStrategy 和 SizeStrategy 类，这三个类是通过不同维度的条件缓存 Bitmap 的，具体如下

• AttributeStrategy 是通过 Bitmap 的 width、height、config 三个条件缓存 Bitmap 对象
• SizeConfigStrategy 是通过 Bitmap 的 size、config 两个条件缓存 Bitmap 对象
• SizeStrategy 是通过 Bitmap 的 size 条件缓存 Bitmap 对象

可能有人会有疑问了，在 BitmapPool 和 LruPoolStrategy 接口中定义的都是 Bitmap get(int width, int height, Bitmap.Config config) 方法，传入的都是 width、height、config 三个条件，为什么可以通过不同的条件缓存 Bitmap 对象呢？

2.3.2.2 Key & KeyPool

这个时候就需要引入 Key 和 KeyPool 这两个类了。

BitmapPool 和 LruPoolStrategy 都只是接口定义，其底层的实现类其实都是使用了 Map 数据结构。大家都知道 Map 是以 <K, V> 键值对的形式在 K 和 V 之间形成一一映射的，我们的 V 不用多说，自然就是 Bitmap 对象了，而 K 的话就可以是不同形式的了。在 Glide 中，具体的 K 是 Key 这样的一个类，而为了避免每次存放、获取 Bitmap 对象而新建 Key 对象，引入了 KeyPool 的概念。

Glide 中，LruPoolStrategy 有三个不同的实现类 AttributeStrategy、SizeConfigStrategy 和 SizeStrategy，他们是通过不同维度的条件缓存 Bitmap，这三个不同维度的条件具体就体现在它们各自内部的实现类 Key 上。

以 AttributeStrategy 为例，AttributeStrategy 是通过 Bitmap 的 width、height、config 三个条件缓存 Bitmap 对象，所以 AttributeStrategy 内部类 Key 的实现如下

• 在 AttributeStrategy.Key 类中包含 width、height 和 config 三个属性，且通过 init(int width, int height, Bitmap.Config config) 方法初始化
• 作为 Map 的 K，自然要重写 equals(Object o) 和 hashCode() 方法，且其中都用到了 width、height、config 三个属性
• 在 LruPoolStrategy 另外两个类 SizeConfigStrategy 和 SizeStrategy 中 Key 也是类似的实现，这里就不多说了

class AttributeStrategy implements LruPoolStrategy {

  ......

  @VisibleForTesting
  static class Key implements Poolable {
    private final KeyPool pool;
    private int width;
    private int height;
    // Config can be null :(
    private Bitmap.Config config;

    public Key(KeyPool pool) {
      this.pool = pool;
    }

    public void init(int width, int height, Bitmap.Config config) {
      this.width = width;
      this.height = height;
      this.config = config;
    }

    @Override
    public boolean equals(Object o) {
      if (o instanceof Key) {
        Key other = (Key) o;
        return width == other.width && height == other.height && config == other.config;
      }
      return false;
    }

    @Override
    public int hashCode() {
      int result = width;
      result = 31 * result + height;
      result = 31 * result + (config != null ? config.hashCode() : 0);
      return result;
    }

    @Override
    public String toString() {
      return getBitmapString(width, height, config);
    }

    @Override
    public void offer() {
      pool.offer(this);
    }
  }
}

说完 Key，接下来说一下 KeyPool 类，Glide 为了避免每次存放、获取 Bitmap 对象都新建 Key 对象，引入了 KeyPool 的概念

因为不同的缓存策略对应不同的 Key，不同的 Key 自然要对应不同的 KeyPool 了，有三种缓存策略，所以也有三种 Key 和 KeyPool 了。

先介绍三种 KeyPool 的基类 BaseKeyPool 类，如下所示

• BaseKeyPool 类是个泛型类，只要是实现了 Poolable 接口的类的对象，都可以通过 BaseKeyPool 对象池缓存
• 在 BaseKeyPool 类中是通过一个队列 Queue 实现缓存的，对多可以缓存 20 个对象
• BaseKeyPool 也是默认修饰符的，只可以在 Glide 包内部使用

abstract class BaseKeyPool<T extends Poolable> {
  private static final int MAX_SIZE = 20;
  private final Queue<T> keyPool = Util.createQueue(MAX_SIZE);

  // 通过 get() 方法可以得到一个 T 对象，T 对象有可能是从缓存队列中取的，也有可能是通过 create() 方法新建的
  T get() {
    T result = keyPool.poll();
    if (result == null) {
      result = create();
    }
    return result;
  }

  // 通过 offer(T key) 方法将 T 对象加入到缓存队列中，前提是缓存队列没有满
  public void offer(T key) {
    if (keyPool.size() < MAX_SIZE) {
      keyPool.offer(key);
    }
  }

  // 因为不同的缓存对象有不同形式的新建方式，所以 create() 方法需要是抽象的
  abstract T create();
}

介绍完 BaseKeyPool 基类以后，接着介绍一下在 AttributeStrategy 中应用的 KeyPool 类，其定义如下

• AttributeStrategy.KeyPool 中缓存的 Key 都是 AttributeStrategy.Key 对象

class AttributeStrategy implements LruPoolStrategy {

  ......

  @VisibleForTesting
  static class KeyPool extends BaseKeyPool<Key> {
    Key get(int width, int height, Bitmap.Config config) {
      Key result = get();
      result.init(width, height, config);
      return result;
    }

    @Override
    protected Key create() {
      return new Key(this);
    }
  }

  ......

}

2.3.2.2 AttributeStrategy

其实介绍完 AttributeStrategy.KeyPool 和 AttributeStrategy.Key 以后，AttributeStrategy 剩下的代码也不多了，其代码如下

• GroupedLinkedMap 类似于 LinkedHashMap，其实用 HashMap、List 和双向链表实现了 LRU 算法，后面会详细介绍。
• 可以看到在 put(Bitmap bitmap) & get(int width, int height, Bitmap.Config config) 时，都是先从 KeyPool 中得到对应的 Key 以后，再去操作 groupedMap 的

class AttributeStrategy implements LruPoolStrategy {
  private final KeyPool keyPool = new KeyPool();
  private final GroupedLinkedMap<Key, Bitmap> groupedMap = new GroupedLinkedMap<>();

  @Override
  public void put(Bitmap bitmap) {
    final Key key = keyPool.get(bitmap.getWidth(), bitmap.getHeight(), bitmap.getConfig());

    groupedMap.put(key, bitmap);
  }

  @Override
  public Bitmap get(int width, int height, Bitmap.Config config) {
    final Key key = keyPool.get(width, height, config);

    return groupedMap.get(key);
  }

  @Override
  public Bitmap removeLast() {
    return groupedMap.removeLast();
  }

  @Override
  public String logBitmap(Bitmap bitmap) {
    return getBitmapString(bitmap);
  }

  @Override
  public String logBitmap(int width, int height, Bitmap.Config config) {
    return getBitmapString(width, height, config);
  }

  @Override
  public int getSize(Bitmap bitmap) {
    return Util.getBitmapByteSize(bitmap);
  }

  ......

  @VisibleForTesting
  static class KeyPool extends BaseKeyPool<Key> {
    ......
  }

  @VisibleForTesting
  static class Key implements Poolable {
        ......
  }
}

2.3.2.3 LruBitmapPool

上面介绍了 LruBitmapPool 相关的几个非常重要的概念：LruPoolStrategy、Key 和 KeyPool，以及 LruPoolStrategy 实现类 AttributeStrategy，如果对上面介绍的内容都理解了，那么理解 LruBitmapPool 就更容易一些了

• 两个 public 的构造方法最后都会调用默认修饰符的构造方法，传入的 LruPoolStrategy strategy 参数是通过 getDefaultStrategy() 方法获取的，可以看到在 API 19 及以上使用的是 SizeConfigStrategy 缓存策略，在 API 19 以下则使用的 AttributeStrategy 缓存策略
• 在 put(Bitmap bitmap) 方法中，首先会做必要的条件检查，然后会调用 strategy.put(bitmap)，将 bitmap 对象缓存到对象池中，最后修改相关的参数，如 currentSize
• 在 get(int width, int height, Bitmap.Config config) 和 getDirty(int width, int height, Bitmap.Config config) 方法中，首先都会调用 getDirtyOrNull(int width, int height, @Nullable Bitmap.Config config) 方法从 strategy.get(width, height, config != null ? config : DEFAULT_CONFIG) 缓存对象池中获取 Bitmap，如果得到的 Bitmap 对象为空，则调用 createBitmap(int width, int height, @Nullable Bitmap.Config config) 方法创建一个新的 Bitmap 对象并返回

public class LruBitmapPool implements BitmapPool {
  private final LruPoolStrategy strategy;
  private final long initialMaxSize;

  ......

  private long maxSize;
  private long currentSize;

  // 默认修饰符的构造方法，另外两个构造方法最后都会调用此构造方法 
  LruBitmapPool(long maxSize, LruPoolStrategy strategy, Set<Bitmap.Config> allowedConfigs) {
    this.initialMaxSize = maxSize;
    this.maxSize = maxSize;
    this.strategy = strategy;
    this.allowedConfigs = allowedConfigs;
    this.tracker = new NullBitmapTracker();
  }

  public LruBitmapPool(long maxSize) {
    this(maxSize, getDefaultStrategy(), getDefaultAllowedConfigs());
  }

  public LruBitmapPool(long maxSize, Set<Bitmap.Config> allowedConfigs) {
    this(maxSize, getDefaultStrategy(), allowedConfigs);
  }

  @Override
  public long getMaxSize() {
    return maxSize;
  }

  @Override
  public synchronized void setSizeMultiplier(float sizeMultiplier) {
    maxSize = Math.round(initialMaxSize * sizeMultiplier);
    evict();
  }

  @Override
  public synchronized void put(Bitmap bitmap) {
    if (bitmap == null) {
      throw new NullPointerException("Bitmap must not be null");
    }
    if (bitmap.isRecycled()) {
      throw new IllegalStateException("Cannot pool recycled bitmap");
    }
    if (!bitmap.isMutable() || strategy.getSize(bitmap) > maxSize
        || !allowedConfigs.contains(bitmap.getConfig())) {
      if (Log.isLoggable(TAG, Log.VERBOSE)) {
        Log.v(TAG, "Reject bitmap from pool"
                + ", bitmap: " + strategy.logBitmap(bitmap)
                + ", is mutable: " + bitmap.isMutable()
                + ", is allowed config: " + allowedConfigs.contains(bitmap.getConfig()));
      }
      bitmap.recycle();
      return;
    }

    final int size = strategy.getSize(bitmap);
    strategy.put(bitmap);                                               // 关键，缓存进 strategy 对象池中
    tracker.add(bitmap);

    puts++;
    currentSize += size;

    if (Log.isLoggable(TAG, Log.VERBOSE)) {
      Log.v(TAG, "Put bitmap in pool=" + strategy.logBitmap(bitmap));
    }
    dump();

    evict();
  }

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

  @Override
  @NonNull
  public Bitmap get(int width, int height, Bitmap.Config config) {
    Bitmap result = getDirtyOrNull(width, height, config);
    if (result != null) {
      // Bitmaps in the pool contain random data that in some cases must be cleared for an image
      // to be rendered correctly. we shouldn't force all consumers to independently erase the
      // contents individually, so we do so here. See issue #131.
      result.eraseColor(Color.TRANSPARENT);                                             // 关键，将 Bitmap 对象的像素否复位为透明的
    } else {
      result = createBitmap(width, height, config);                             // 关键，若从缓存对象池中得到的 Bitmap 对象为空，则通过 createBitmap 方法创建新的 Bitmap 对象
    }

    return result;
  }

  @NonNull
  @Override
  public Bitmap getDirty(int width, int height, Bitmap.Config config) {
    Bitmap result = getDirtyOrNull(width, height, config);
    if (result == null) {
      result = createBitmap(width, height, config);                         // 关键，创建新的 Bitmap 对象
    }
    return result;
  }

  @NonNull
  private static Bitmap createBitmap(int width, int height, @Nullable Bitmap.Config config) {
    return Bitmap.createBitmap(width, height, config != null ? config : DEFAULT_CONFIG);
  }

    @Nullable
  private synchronized Bitmap getDirtyOrNull(
      int width, int height, @Nullable Bitmap.Config config) {
    assertNotHardwareConfig(config);
    // Config will be null for non public config types, which can lead to transformations naively
    // passing in null as the requested config here. See issue #194.
    final Bitmap result = strategy.get(width, height, config != null ? config : DEFAULT_CONFIG);        // 关键，从 strategy 中获取缓存的 Bitmap 对象
    if (result == null) {
      if (Log.isLoggable(TAG, Log.DEBUG)) {
        Log.d(TAG, "Missing bitmap=" + strategy.logBitmap(width, height, config));
      }
      misses++;
    } else {
      hits++;
      currentSize -= strategy.getSize(result);
      tracker.remove(result);
      normalize(result);
    }
    if (Log.isLoggable(TAG, Log.VERBOSE)) {
      Log.v(TAG, "Get bitmap=" + strategy.logBitmap(width, height, config));
    }
    dump();

    return result;
  }

  ......

  private static LruPoolStrategy getDefaultStrategy() {
    final LruPoolStrategy strategy;
    if (Build.VERSION.SDK_INT >= Build.VERSION_CODES.KITKAT) {
      strategy = new SizeConfigStrategy();
    } else {
      strategy = new AttributeStrategy();
    }
    return strategy;
  }

  ......

}

2.3.3 GroupedLinkedMap<K extends Poolable, V> 实现 LRU 算法

LruPoolStrategy 是缓存策略接口，具体的实现类有 AttributeStrategy、SizeConfigStrategy 和 SizeStrategy，这三个类是通过不同的条件来缓存 Bitmap 的，底层具体的实现都使用了 GroupedLinkedMap<K extends Poolable, V> 数据结构，而 GroupedLinkedMap<K extends Poolable, V> 实现了 LRU 算法，现在就详细介绍下它是如何实现 LRU 算法的

GroupedLinkedMap<K extends Poolable, V> 的类定义如下所示，其中有两个非常重要的属性 Map<K, LinkedEntry<K, V>> keyToEntry 和 LinkedEntry<K, V> head

GroupedLinkedMap.png

LinkedEntry<K, V> 是 GroupedLinkedMap<K extends Poolable, V> 的一个内部类，代码实现其实并不复杂

• 其中的 K key 属性对应于其在 GroupedLinkedMap<K extends Poolable, V> 的 K
• List<V> values 则是真正存储 V 的集合
• LinkedEntry<K, V> next 和 LinkedEntry<K, V> prev 则用于实现双向链表，而双向链表正是实现 LRU 算法真正的数据结构

class GroupedLinkedMap<K extends Poolable, V> {

  ......

  private static class LinkedEntry<K, V> {
    @Synthetic final K key;
    private List<V> values;
    LinkedEntry<K, V> next;
    LinkedEntry<K, V> prev;

    // Used only for the first item in the list which we will treat specially and which will not
    // contain a value.
    LinkedEntry() {
      this(null);
    }

    LinkedEntry(K key) {
      next = prev = this;
      this.key = key;
    }

    @Nullable
    public V removeLast() {
      final int valueSize = size();
      return valueSize > 0 ? values.remove(valueSize - 1) : null;
    }

    public int size() {
      return values != null ? values.size() : 0;
    }

    public void add(V value) {
      if (values == null) {
        values = new ArrayList<>();
      }
      values.add(value);
    }
  }
}

介绍完 LinkedEntry<K, V> 之后，再接着介绍一下 GroupedLinkedMap<K extends Poolable, V> 中非常重要的几个方法，如下所示

• put(K key, V value) 方法，首先根据 K key 从 Map<K, LinkedEntry<K, V>> keyToEntry = new HashMap<>() 中查找对应的 LinkedEntry<K, V>，如果查找结果为 null，则新建一个 LinkedEntry<K, V> 对象，并将此新建的 LinkedEntry<K, V> 对象插入到双向链表的尾部，然后将 V value（也就是 Bitmap 对象） 插入到 LinkedEntry<K, V> 对象的 List<V> values 中
• 调用 get(K key) 方法获取 Bitmap 对象时，会先通过 K key 从 Map<K, LinkedEntry<K, V>> keyToEntry 查找对应的 LinkedEntry<K, V> 对象，如果查找结果为 null，则新建一个 LinkedEntry<K, V> 对象，最后将此 LinkedEntry<K, V> 对象插入到双向链表的头部，然后从此 LinkedEntry<K, V> 对象的 List<V> values 中取一个 Bitmap 对象并返回
• V removeLast() 方法，则从双向链表尾部节点的 LinkedEntry<K, V> 中的 List<V> values 中移除最后一个 Bitmap 对象
• 从上面对 put(K key, V value) 方法和 get(K key) 方法分析可以明白，使用 LinkedEntry<K, V> 双向链表是为了支持 LRU 算法，最近使用过的 K key 以及对应的 LinkedEntry<K, V> 对象都在双向链表的头部，使用次数越少越靠近双向链表的尾部，如果要从此链表中移除一个 Bitmap，也是调用 removeLast() 方法从双向链表尾部节点的 LinkedEntry<K, V> 中的 List<V> values 中移除最后一个 Bitmap 对象

class GroupedLinkedMap<K extends Poolable, V> {
  private final LinkedEntry<K, V> head = new LinkedEntry<>();
  private final Map<K, LinkedEntry<K, V>> keyToEntry = new HashMap<>();

  public void put(K key, V value) {
    LinkedEntry<K, V> entry = keyToEntry.get(key);

    if (entry == null) {
      entry = new LinkedEntry<>(key);
      makeTail(entry);
      keyToEntry.put(key, entry);
    } else {
      key.offer();
    }

    entry.add(value);
  }

  @Nullable
  public V get(K key) {
    LinkedEntry<K, V> entry = keyToEntry.get(key);
    if (entry == null) {
      entry = new LinkedEntry<>(key);
      keyToEntry.put(key, entry);
    } else {
      key.offer();
    }

    makeHead(entry);

    return entry.removeLast();
  }

  @Nullable
  public V removeLast() {
    LinkedEntry<K, V> last = head.prev;

    while (!last.equals(head)) {
      V removed = last.removeLast();
      if (removed != null) {
        return removed;
      } else {
        // We will clean up empty lru entries since they are likely to have been one off or
        // unusual sizes and
        // are not likely to be requested again so the gc thrash should be minimal. Doing so will
        // speed up our
        // removeLast operation in the future and prevent our linked list from growing to
        // arbitrarily large
        // sizes.
        removeEntry(last);
        keyToEntry.remove(last.key);
        last.key.offer();
      }

      last = last.prev;
    }

    return null;
  }

  ......

}

最后贴一张 GroupedLinkedMap<K extends Poolable, V> 的示意图，相信对理解双向链表、Map、以及 List 实现 GroupedLinkedMap<K extends Poolable, V> 的方式会有所帮助

GroupedLinkedMap1.png

Glide 源码分析解读-缓存模块-基于最新版Glide 4.9.0

2.3.4 Glide 分析小结

• 因为在 Glide 中缓存的是 Bitmap 对象，而 Bitmap 对象又有不同的属性，比如 width、height、config（这些属性统称为 Key），所以就需要将属性 Key 和 Bitmap 实例对象一一映射。在 Glide 中也拥有两个对象池，分别是属性 Key 对象池和 Bitamp 实例对象池

• 属性 Key 对象池实现比较简单，是通过队列 Queue<T> keyPool = new ArrayDeque<> 实现的，对多可以缓存 20 个 Key 对象

• Bitmap 对象池实现就相对复杂，定义了 BitmapPool 接口，其实现类是 LruBitmapPool，而在 LruBitmapPool 中又可以通过不同的策略 LruPoolStrategy 缓存对象，LruPoolStrategy 有三个实现类 AttributeStrategy、SizeConfigStrategy 和 SizeStrategy，分别根据 Bitmap 的不同属性 Key（width、height、config）缓存 Bitmap 对象的。需要注意的是，在 API 19 及之后使用 SizeConfigStrategy 缓存策略，在 API 19 之前使用 AttributeStrategy 缓存策略

• 而在 AttributeStrategy、SizeConfigStrategy 和 SizeStrategy 这三个类中，底层的实现又依赖于 GroupedLinkedMap<K extends Poolable, V>，它通过双向链表的方法实现了 LRU 算法，最近使用的在双向链表的头部，使用次数越少的 Key 越靠近双向链表的尾部

最后，再贴一张 Glide 中 BitmapPool 的类关系图，相信对理解 Glide 中的 BitmapPool 知识会有所帮助

Glide.png

拆 Glide 系列之 - Bitmap 复用

三. 总结

本文从数据结构的角度，分别介绍了对象池的实现方式，数组、链表、Map 都可以实现对象池，可以根据不同的应用场景灵活地使用具体的数据结构来实现对象池。在 Glide 中应用的可以说是淋漓尽致，单说 BitmapPool 的实现就非常让人称赞了。
对于对象池，个人认为有以下几点是非常需要注意的

• 对象池的大小。对象池的目的是用于在内存中缓存对象，但是不能所有的对象都缓存，如果所有的对象都缓存，无疑对内存也是一个非常巨大的损耗。所以每个对象池都需要设置一个大小，从上面三个例子中也可以看到每个对象池都有默认的大小的，或者需要在调用构建方法的时候就设置大小
• 抽象 & 泛型。为了通用性，对象池一般都会先定义一个接口或者抽象基类，而且是泛型的接口或者基类，上面介绍的 Pool<T>、LruPoolStrategy、BaseKeyPool<T extends Poolable> 就是最好的例证，这两点有什么好处呢？接口或者抽象基类有利于扩展，实现不同的存放、获取的方法，而泛型则可以存储不同的对象
• 抽象方法定义。对象池一般有三个动作存放 put、获取 get 以及新建 create，所以在接口或者抽象基类中一般包含这三个方法即可

介绍了这么多关于对象池的内容，其实最终的目的都是为了避免频繁的创建和回收对象，从而保持内存的稳定。在优化内存时，对象池真是一个非常重要的武器。

四. 参考

拆 Glide 系列之 - Bitmap 复用
Glide 源码分析解读-缓存模块-基于最新版Glide 4.9.0
对象池Pools优化