内存优化之ArrayMap、SparseArray、Sparse

原文链接：https://juejin.im/post/6865980083388186637

1、前言

这几个数据结构呢，都是Android这家伙搞出来；为啥呢，打的旗号是节约内存，系统的很多地方都有他们的身影;为了追随google的脚步，也为了扩展自己对于数据结构的理解，我们有必要学习它；

这里先大致说下，ArrayMap是一个map，是为了解决HashMap存储数据浪费空间情况；SparseArray是数组，为稀疏数据准备的；SparseXXXArray,也是数组，也为稀疏数据准备，xxx是基本数据类型，这样使用时不存在自动拆装箱操作（就是基本类型和相对应类之间的自动转换）;SparseXXXArray的原理实现一致，这里只介绍SparseIntArray

2、存储结构

ArrayMap结构

两个数组来存储；key的hash数据，key-value组成的数组；通过index来映射，2倍位置为key， 2倍位置+1 为value；mHashes数据，是从小到大有序存储的

SparseArray结构

也是两个数组，存储数组索引的key，存储数据value，通过相等索引来映射；mKeys是从小到大有序存储的

从图来看，我觉得是结构思想整体是一致的；但他们的实现思路还是存在不同的地方

3、ArrayMap特点

3.1 hash计算

这里key是可以为null，null是hash值为0，不为空时，其计算方式与下面变量有关，这个可以仅可以在构造器中设置，默认为false

    final boolean mIdentityHashCode;
复制代码

计算区别如下：

    mIdentityHashCode ? System.identityHashCode(key) : key.hashCode()
复制代码

由于是以hash来排序，如果使用默认，那么我们的hashCode方法，要是每个对象固定，最好且是不同的

3.2 容器大小

我们有必要先介绍以下，申请内存缓存机制，这涉及到下面两个数组，其原理是一样的，只是容量不同；

static Object[] mBaseCache;
static int mBaseCacheSize;

static Object[] mTwiceBaseCache;
static int mTwiceBaseCacheSize;

private static final int CACHE_SIZE = 10;
private static final int BASE_SIZE = 4; // 是以mHashes的大小来算的
复制代码

mBaseCache的容量大小为8， mTwiceBaseCache容量大小为16；两个缓存每种最多缓存10个；缓存结构如下图，入量按照8来绘制的：

这里的容量是申请的数组容量，数据存储key-value，所以其能存储的数据个数为其一半；初始化、扩容都是根据存储个数来计算的

初始化

• 初始化容器大小小于0时，不允许申请内存，否则直接抛出异常
• 大小为0时，赋值空数组
• 大小为4个，优先从mBaseCache找有效数组
• 大小为8，优先从mTwiceBaseCache找有效数组
• 大于0时，或者缓存中没有时，直接申请，mHashes申请一倍大小，mArray申请两倍大小

扩容

调用下面两个方法时，可能会扩容

public void ensureCapacity(int minimumCapacity)
public V put(K key, V value)
复制代码

• put方法，容器中存储新数据时，数组已满；
• ensureCapacity方法，容量小于minimumCapacity个

数组的移动System.arraycopy方法处理，如果容器大小增加了，则废弃的数组；废弃的数组，进行回收，如果存储容量大小为4或者8，会放入缓存中

3.3 索引查找

查找可以插入或者替换数据的位置；查找思想:

1\. 进行二分查找，先查找到一个hash相等的位置；
2\. 根据查找的位置，若相等则返回查找位置
3\. 依据hash值相等，往后查找，若key相等，则返回，hash不等则结束；这时位置跟随hash相等而向后移动
4\. 依据hash值相等，往后查找，若key相等，则返回，hash不等则结束
5\. 没有找到，返回前面四步处理后的位置，并取非操作，返回负数值
复制代码

查找位置为正整数，说明此处有数据，可替换，负整数，表示无数据且取非表示可插入位置

3.4 添加数据

增加数据时，可能会扩容；如果数据未找到且容器存储个数已满，这时会进行扩容

 小于4时，扩容到4个；小于8个，扩容到8个；大于等于8时，进行1.5倍扩容
复制代码

3.5 删除数据

删除数据时，可能会进行容量缩减

1. 如果数组现有数据个数为1，删除后，数组置为空数组；原数组容量大小为4或者8，则被放入缓存

2. 如果数据容量大小大于8个，且存储数据个数小于容量的1/3，则容量大小需要重新计算

   1. 已有数据个数小于8时，新容量大小为8
   2. 大于等于8时，新容量大小为现有数据个数的1.5倍

4、SparseIntArray

如果你上面ArrayMap已经懂了，那么SparseIntArray其实已经很简单了；它存在下面的差异

1. list集合
2. 没有缓存机制
3. 扩容大小不同；如果小于等于4，变为8，否则2倍扩容
4. 排序以key排序，数据只存储int类型的value值，key为稀疏数组的索引；ArrayMap，是以key的hash排序，数据数组为key-value交替存储
5. 位置查找时，直接进行二分查找，找到即为插入位置
6. 删除数据时，对容量大小不做处理

5、SparseArray

SparseArray和SparseXXXArray那就更接近了；不过我们还是和ArrayMap做对比吧

1. list集合
2. 没有缓存机制
3. 扩容大小不同；如果小于等于4，变为8，否则2倍扩容
4. 排序以key排序，数据只存储Object类型的value值，key为稀疏数组的索引；ArrayMap，是以key的hash排序，数据数组为key-value交替存储
5. 位置查找时，直接进行二分查找，找到即为插入位置
6. 删除数据时，只是把value置为固定的一个删除标志值
7. 增加数据时，如果存储数据已满且存在删除数据标志，则调用gc方法
8. 如果在查找数据位置，获取数据大小，则都有可能调用gc方法

和SparseXXXArray区别就是：无gc方法机制、存储value值是类而不是基本数据

gc方法:如果有效数据前存在删除数据标志值DELETED，则后面把有效数据往前移位

有没有小伙伴在想，为何SparseXXXArray，没有这种gc行为呢，因为基本类型，存什么都无法标志其是无效数据啊；

技术变化都很快，但基础技术、理论知识永远都是那些；作者希望在余后的生活中，对常用技术点进行基础知识分享；如果你觉得文章写的不错，请给与关注和点赞；如果文章存在错误，也请多多指教！