Android容器类小结

相较于其他设备，移动设备有自己的特点，内存小是一个很突出的问题，Google针对android设备的这一特点，开发了一套容器框架，目的就是为了更加高效地利用内存。接下来就对这些容器进行一下总结。

组织结构

以上是android中容器的实现继承结构，简单梳理一下：

• ArraySet 实现了 Set 和 Collections 接口，在api 23中添加
• ArrayMap 实现了 Map 接口，在api 19中添加
• SparseArray ， SparseIntArray ， SparseBooleanArray 实现了 Cloneable 接口，在api 1中添加
• SparseLong 实现了 Cloneable 接口，在api 18中添加

分类

从** 功能 **上划分，可以将以上容器划分为两类：

• 存储元素

  ArraySet 优化了 HashSet 对元素的存储

• 存储键值对 相较于 HashMap ，具体的优化方向如下：

  ArrayMap 优化了 HashMap 存储 Object --> Object 的键值存储;

  SparseArray 优化了 int --> Object 的键值存储;

  SparseIntArray 优化了 int --> int 的键值存储;

  SparseBooleanArray 优化了 int --> boolean 的键值存储;

  SparseLongArray 优化了 int --> long 的键值存储。

优化方法

从组织结构可以看出，可以将这些容器分为3类： ArraySet , ArrayMap 和剩余的容器。通过前面的分析可以知道， ArraySet 和 ArrayMap 使用的相同的优化方式， SparseArray 在进行优化的时候使用 gc 垃圾回收策略，故从优化方法上进行分类的话可以分一下三类：

• ArraySet , ArrayMap 使用数组 mKeys 存储 key 的hash值，hash值在 mKeys 的位置为 index ，并将value存储到 mValues 数组对应下标的位置（ ArrayMap 中 key 和 value 分别在 mValues 的 index * 2 和 index * 2 + 1 的位置）。查找或者修改元素时，使用二分查找在 mKeys 中找到元素在 mValues 的下标，然后进行修改或者返回。
• SparseArray 使用 int 类型的 mKeys 数组存储 int 类型的键，下标为 index ，将 Object 类型的 value 存储在在 Object 类型的数组 mValues 的 index 位置，在查找和修改时，使用二分查找在 mKeys 中找到元素在 mValues 的下标，然后进行修改或者返回。在删除 value 时， SparseArray 并不直接进行数组元素的移动，而是将待删除的 value 标记为 DELETED 状态，在 gc 的过程中将所有非 DELETED 状态的元素移动到数组的最前面，从而减少二分查找的时间。
• SparseIntArray , SparseLongArray , SparseBooleanArray 这3个容器可以理解成专用容器，使用 int 类型数组和对应类型的数组；使用二分查找快速查找元素，然后进行删除，修改，添加操作。

优化共同点与差异

虽然这些容器存储的元素类型不同，但是通过分析可以发现他们在内存优化中的共同点，接下来就分析下这些容器在优化上存在的共同点和差异。

共同点

• 数据结构

  

  这里的数据结构是指容器的底层存储结构，虽然在 ArrayMap 中mValues的长度是mKeys的2倍，但也仅仅是数组长度上的差异，底层存储使用的思想仍然是一样的； int 类型的数组 mKeys 里的元素时按照升序进行排列的。相较于 HashMap 使用 Node 结构存储，这样的存储方式使用更小的存储空间存储 k-v

  ，同时避免了原始数据类型的自动装箱。

• 查找方法 在组织结构中列出的容器，他们在进行元素查找时，都会先在 mKeys 数组中利用二分查找找到元素的下标 index ，然后使用 index 到 mValues 数组中对 value 进行操作。

• 获取带插入下标 在进行元素插入时，会首先使用二分查找在 mKeys 数组中查找元素的下标，如果元素不存在，则二分查找会返回元素待插入位置的取反。

不同点

• 对 key 的处理 ArraySet , ArrayMap 底层实现时，会计算待插入元素的hash值，根据hash值，在 mKeys 找到待插入位置； SparseArray 和 SparseXXXArray 存储的时候直接使用 key 值，不会进行hash计算。
• 对 null 的处理 ArraySet 和 ArrayMap 允许插入 key 为 null 的元素， key 的hash值为0； SparseArray 和 SparseXXXArray 存储的时由于直接使用int类型的数据作为 key ，故不存在 key 为 null 的情况。
• 缓存 为了避免频繁的内存回收， ArraySet 和 ArrayMap 添加了缓存结构， SparseArray 和 SparseXXXArray 没有缓存
• 扩容规则 ArraySet 和 ArrayMap 在进行扩容的时，容量的变化规则为 4, 8 , size * 2 / 3 ， SparseArray 和 SparseXXXArray 使用 ArrayUtils.newUnpaddedArray 建立新的数据，将原来的数据拷贝到新数组中。

使用建议

虽然这些容器在Android设备上可以更高效地利用内存，但是还是存在使用使用限制。

ArrayMap
HashMap

总结

前面说了很多，其实android容器优化的根本思想就是使用 int 到其他类型的映射，使用数组保存着两个映射，用以优化 HashMap 对 k-v 的存储。这种优化适用于元素数量较少（少于1000）的情况。