⏰ : 全文字数：4700+
: 内容关键字：Glide内存优化，GroupedLinkedMap，Bitmap缓存池
: 公_众_号：七郎的小院
: 更多文章,博客：blog.softgeek.cn
概述
相信很多人看到GroupedLinkedMap这个数据结构，觉得一脸懵，因为很少乃至都没有见到过这个数据结构。其实这个数据结构是 Glide 在完成 Bitmap 缓存池时，自己定义的一个数据结构，功用相似咱们常用的 HashMap，可是又和 HashMap 不太相同，个哦能上做了一些修改。
这个数据结构虽然简略，可是它的完成思路和背面设计的原因还是很值得咱们学习和研究的，所以今日咱们就来看下这个结构。
本文基于
Glide 4.13.1源码版本学习(后续会继续更新《深入学习Glide的专栏》)
原理
先看这个类的定义，内部有两个变量，一个是双链表的头目标 LinkedEntry，一个保存数据用的 HashMap，这儿也阐明这个数据结构大致的功用和 HashMap 肯定是很像的，如下：
class GroupedLinkedMap<K extends Poolable, V> {
// 链表头
private final LinkedEntry<K, V> head = new LinkedEntry<>();
private final Map<K, LinkedEntry<K, V>> keyToEntry = new HashMap<>();
......
}
put 办法
咱们看下它的put办法，通过这个办法来学习它是如何保存数据的。办法内容如下：
public void put(K key, V value) {
// 先从HashMap中查找对应Key的Entry是否存在
LinkedEntry<K, V> entry = keyToEntry.get(key);
if (entry == null) {
// 假如不存在，就创立一个新的LinkedEntry目标
entry = new LinkedEntry<>(key);
// 放到链表的尾部
makeTail(entry);
// 添加到HashMap中
keyToEntry.put(key, entry);
} else {
// 假如存在，就不去更新HashMap了，也便是这儿不会替换相同key值的数据
key.offer();
}
// 把value添加到对应的LinkedEntry类中
entry.add(value);
}
上面的 put 办法的逻辑是：
- 并不是直接把
key-value寄存到HashMap中，而是把key-LinkedEntry类型保存到HashMap中，而这儿的LinkedEntry类是一个对 key 和 value 的封装类型 - 寄存数据时，假如具有相同 key，不会替换
HashMap中的数据，而是取出现已存在的数据，然后把value值添加到对应的LinkedEntry类中。这个便是和HashMap最大的区别，HashMap每次遇到相同 key 的数据，会替换并回来旧值。
所以接下来，咱们看下 LinkedEntry 类的完成
private static class LinkedEntry<K, V> {
@Synthetic final K key;
private List<V> values;
// 双链表
LinkedEntry<K, V> next;
LinkedEntry<K, V> prev;
LinkedEntry() {
this(null);
}
LinkedEntry(K key) {
next = prev = this;
this.key = key;
}
@Nullable
public V removeLast() {
final int valueSize = size();
// 假如没有就回来null，有就回来调集最终一个
return valueSize > 0 ? values.remove(valueSize - 1) : null;
}
public int size() {
return values != null ? values.size() : 0;
}
public void add(V value) {
// 相同key的方位并不是一个值，而是一个链表
if (values == null) {
values = new ArrayList<>();
}
values.add(value);
}
}
从上面能够看到 LinkedEntry 的一些特性
- 内部有 next 和 pre 变量，相当于 GroupedLinkedMap 自己维护了一个双链表，按照访问次序维护着链表，并没有运用 LinkHashMap 来进行完成 LRU 的逻辑。
- 通过看
add办法，能够知道相同key的数据，都会用一个数组调集ArrayList进行保存，不会替换
所以综上，GroupedLinkedMap 保存数据的格局如下图所示：
get 办法
咱们再来看下它的get办法，看他是如何获取数据的。
@Nullable
public V get(K key) {
LinkedEntry<K, V> entry = keyToEntry.get(key);
// 假如不存在，也会新建一条key-LinkedEntry的记录
// 并寄存，仅仅没有value值
if (entry == null) {
entry = new LinkedEntry<>(key);
keyToEntry.put(key, entry);
} else {
key.offer();
}
// 放到双链表的头部中
makeHead(entry);
// 找到key对应的value，假如没有则回来null，否则回来数组调集的最终一个
return entry.removeLast();
}
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办法：
// SizeConfigStrategy#put 办法
public void put(Bitmap bitmap) {
int size = Util.getBitmapByteSize(bitmap);
// 用内存巨细和config创立一个key
Key key = keyPool.get(size, bitmap.getConfig());
groupedMap.put(key, bitmap);
......
}
// Key的equal办法
public boolean equals(Object o) {
if (o instanceof Key) {
Key other = (Key) o;
// 当size和config持平时，便是持平的
return size == other.size && Util.bothNullOrEqual(config, other.config);
}
return false;
}
从上面能够知道，Glide缓存Bitmap，是运用Bitmap目标的内存sizhe和config作为判断依据，假如两者持平，则阐明Key持平。而在咱们项目的实际开发中，一般都有一套标准，存在很多尺度持平，装备持平的图，假如咱们运用LinkedHashMap来完成，那么每种Key只能保存一个，也便是巨细装备持平的Bitmap只能保存一份，这是不利于缓存的。假如射中不了缓存的Bitmap就无法复用，就要重新创立Bitmap目标。
而且在Android 4.4以下，Bitmap能复用的条件便是宽度和高度相同，inSimpleSize为1，这种情况下假如运用LinkedHashMap相同有上面说的问题。
所以综上面可能的原因，Glide自己完成了一个LRU的库。
