Glide内存优化之GroupedLinkedMap
逍十一郎概述
相信很多人看到GroupedLinkedMap这个数据结构，觉得一脸懵，因为很少甚至都没有见到过这个数据结构。其实这个数据结构是 Glide 在实现 Bitmap 缓存池时，自己定义的一个数据结构，功能类似我们常用的 HashMap，但是又和 HashMap 不太一样，个哦能上做了一些修改。
这个数据结构虽然简单，但是它的实现思路和背后设计的原因还是很值得我们学习和研究的，所以今天我们就来看下这个结构。
本文基于
Glide 4.13.1源码版本学习(后续会持续更新《深入学习Glide的专栏》)
原理
先看这个类的定义，内部有两个变量，一个是双链表的头对象 LinkedEntry，一个保存数据用的 HashMap，这里也说明这个数据结构大致的功能和 HashMap 肯定是很像的，如下：
1class GroupedLinkedMap<K extends Poolable, V> {
2 // 链表头
3 private final LinkedEntry<K, V> head = new LinkedEntry<>();
4 private final Map<K, LinkedEntry<K, V>> keyToEntry = new HashMap<>();
5 ......
6}put 方法
我们看下它的put方法，通过这个方法来学习它是如何保存数据的。方法内容如下：
1 public void put(K key, V value) {
2 // 先从HashMap中查找对应Key的Entry是否存在
3 LinkedEntry<K, V> entry = keyToEntry.get(key);
4
5 if (entry == null) {
6 // 如果不存在，就创建一个新的LinkedEntry对象
7 entry = new LinkedEntry<>(key);
8 // 放到链表的尾部
9 makeTail(entry);
10 // 添加到HashMap中
11 keyToEntry.put(key, entry);
12 } else {
13 // 如果存在，就不去更新HashMap了，也就是这里不会替换相同key值的数据
14 key.offer();
15 }
16 // 把value添加到对应的LinkedEntry类中
17 entry.add(value);
18 }上面的 put 方法的逻辑是：
- 并不是直接把
key-value存放到HashMap中，而是把key-LinkedEntry类型保存到HashMap中，而这里的LinkedEntry类是一个对 key 和 value 的封装类型 - 存放数据时，如果具有相同 key，不会替换
HashMap中的数据，而是取出已经存在的数据，然后把value值添加到对应的LinkedEntry类中。这个就是和HashMap最大的区别，HashMap每次遇到相同 key 的数据，会替换并返回旧值。
所以接下来，我们看下 LinkedEntry 类的实现
1
2 private static class LinkedEntry<K, V> {
3 @Synthetic final K key;
4 private List<V> values;
5 // 双链表
6 LinkedEntry<K, V> next;
7 LinkedEntry<K, V> prev;
8
9 LinkedEntry() {
10 this(null);
11 }
12
13 LinkedEntry(K key) {
14 next = prev = this;
15 this.key = key;
16 }
17
18 @Nullable
19 public V removeLast() {
20 final int valueSize = size();
21 // 如果没有就返回null，有就返回集合最后一个
22 return valueSize > 0 ? values.remove(valueSize - 1) : null;
23 }
24
25 public int size() {
26 return values != null ? values.size() : 0;
27 }
28
29 public void add(V value) {
30 // 相同key的位置并不是一个值，而是一个链表
31 if (values == null) {
32 values = new ArrayList<>();
33 }
34 values.add(value);
35 }
36 }从上面可以看到 LinkedEntry 的一些特性
- 内部有 next 和 pre 变量，相当于 GroupedLinkedMap 自己维护了一个双链表，按照访问顺序维护着链表，并没有使用 LinkHashMap 来进行实现 LRU 的逻辑。
- 通过看
add方法，可以知道相同key的数据，都会用一个数组集合ArrayList进行保存，不会替换
所以综上，GroupedLinkedMap 保存数据的格式如下图所示：
get 方法
我们再来看下它的get方法，看他是如何获取数据的。
1 @Nullable
2 public V get(K key) {
3 LinkedEntry<K, V> entry = keyToEntry.get(key);
4 // 如果不存在，也会新建一条key-LinkedEntry的记录
5 // 并存放，只是没有value值
6 if (entry == null) {
7 entry = new LinkedEntry<>(key);
8 keyToEntry.put(key, entry);
9 } else {
10 key.offer();
11 }
12 // 放到双链表的头部中
13 makeHead(entry);
14 // 找到key对应的value，如果没有则返回null，否则返回数组集合的最后一个
15 return entry.removeLast();
16 }get 的逻辑就比较简单了，主要是：
- 到
HashMap中获取对应 key 的数据，如果没有，就先创建一个记录保存，只是这个记录LinkedEntry只有key，没有value值而已 - 把找到或者生成的
LinkedEntry放入链表的头部位置 - 返回
LinkedEntry中数组集合数据的最后一个，如果没有则返回 null
和 LinkedHashMap 的差异
从 GroupedLinkedMap 的实现来看，和我们常用的LinkedHashMap类很像，但是又有一些差异，具体表现为：
- 内部确实是利用了
HashMap来实现key-value的保存功能，但是对于相同 key 的数据处理不一样，GroupedLinkedMap会保存相同 key 的数据，都存在一个ArrayList的集合中，但是LinkedHashMap/HashMap会进行替换 GroupedLinkedMap具有 LRU 的功能，但是并不是和我们熟知的那样，利用LinkedHashMap来实现的，而是自己内部实现了一个类似LinkedHashMap的功能
为什么要自己实现这个数据结构
个人觉得这里之所以没有使用LinkedHashMap来实现，是因为和它的key有关。我们来看下在Glide图片缓存中的key是什么。因为这个类主要用在Bitmap缓存池中，我们看下其中一个策略的实现，SizeConfigStrategy#put方法：
1 // SizeConfigStrategy#put 方法
2 public void put(Bitmap bitmap) {
3 int size = Util.getBitmapByteSize(bitmap);
4 // 用内存大小和config创建一个key
5 Key key = keyPool.get(size, bitmap.getConfig());
6
7 groupedMap.put(key, bitmap);
8 ......
9 }
10 // Key的equal方法
11 public boolean equals(Object o) {
12 if (o instanceof Key) {
13 Key other = (Key) o;
14 // 当size和config相等时，就是相等的
15 return size == other.size && Util.bothNullOrEqual(config, other.config);
16 }
17 return false;
18 }从上面可以知道，Glide缓存Bitmap，是利用Bitmap对象的内存sizhe和config作为判断依据，如果两者相等，则说明Key相等。而在我们项目的实际开发中，一般都有一套规范，存在大量尺寸相等，配置相等的图，如果我们利用LinkedHashMap来实现，那么每种Key只能保存一个，也就是大小配置相等的Bitmap只能保存一份，这是不利于缓存的。如果命中不了缓存的Bitmap就无法复用，就要重新创建Bitmap对象。
而且在Android 4.4以下，Bitmap能复用的条件就是宽度和高度一样，inSimpleSize为1，这种情况下如果使用LinkedHashMap一样有上面说的问题。
所以综上面可能的原因，Glide自己实现了一个LRU的库。