概述

相信很多人看到GroupedLinkedMap这个数据结构，觉得一脸懵，因为很少甚至都没有见到过这个数据结构。其实这个数据结构是 Glide 在实现 Bitmap 缓存池时，自己定义的一个数据结构，功能类似我们常用的 HashMap，但是又和 HashMap 不太一样，个哦能上做了一些修改。

这个数据结构虽然简单，但是它的实现思路和背后设计的原因还是很值得我们学习和研究的，所以今天我们就来看下这个结构。

本文基于Glide 4.13.1 源码版本学习(后续会持续更新《深入学习Glide的专栏》)

原理

先看这个类的定义，内部有两个变量，一个是双链表的头对象 LinkedEntry，一个保存数据用的 HashMap，这里也说明这个数据结构大致的功能和 HashMap 肯定是很像的，如下：

1
2
3
4
5
6

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方法，通过这个方法来学习它是如何保存数据的。方法内容如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

  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 类的实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

  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 保存数据的格式如下图所示： 无标题绘图 (1).png

get 方法

我们再来看下它的get方法，看他是如何获取数据的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

  @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方法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

  // 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的库。