SparseArray和ArrayMap是Android中的特有集合类数据结构。
一、SparseArray
SparseArray直译为稀疏数组，本质上是通过数组实现的、key为整型的键值对集合。刷过算法题的应该对类似的数据结构很熟悉。
1. SparseArray的用法
SparseArray的一般使用类似于key为整型的HashMap。如下：
SparseArray<String> arr = new SparseArray<>();
arr.put(1, "one");
arr.put(100, "one hundred");
arr.put(10000, "ten thousand");
arr.remove(100);
另外：
- 使用
append方法与put方法类似的添加元素；不过如果待添加的key大于当前所有元素，则直接加在末尾，少了二分查找的这一步，所以比put方法效率要高。 - 使用
indexOfKey(key)和indexOfValue(value)可以查找对应的key或者value在数组中的序号。 - 使用
keyAt(index)和valueAt(index)方法可以查找对应序号的key或者value。
2. SparseArray的实现原理
SparseArray的实现原理是通过整型数组mKeys和值数组mValues建立的一一对应关系，通过mSize属性来标记其键值对的数量（mSize对应的键值对是真实存在于集合中的元素，不包括已经删除的）。
mKeys数组是有序递增的，这样有助于进行二分查找。当往SparseArray中添加键值对时，会通过二分查找找到相应的位置并插入。当进行删除时，同样会通过二分查找找到相应的键值对，然后将mValues数组中对应的值赋为DELETED（DELETED是一个常量对象，无实际含义，只作为该键值对已经被删除的标记）。
查找
当查找元素时，会使用二分查找，所以SparseArray的查找时间复杂度是O(logN)。
删除
当删除元素时，会先查找到该元素；这时并不会立即把这个元素删除，而只是标记其值为DELETED，这是SparseArray的延时删除机制，可以提高执行效率。
添加
在使用put方法添加元素时，会先查找元素，如果找到对应的key，那么就直接修改对应的值；如果没有找到对应的key，那么就会添加新值。
在添加新值之前，会检查二分查找最接近的那个元素，如果该元素值为DELETED，则直接将该元素替换为待添加的元素；否则，在此处插入新元素。
在插入元素之前，如果键值对数量mSize已经大于等于mKeys数组长度，SparseArray会进行垃圾回收gc()。这里的垃圾回收不同于JVM的垃圾回收，而是删除所有值为DELETED的键值对，并将其后面的元素依次靠拢。在垃圾回收之后，如果mSize仍旧大于等于mKeys的长度，数组会进行扩容。
特别地，当使用append方法添加数据，且添加的key大于当前数组中所有元素时，则会直接插入在数组最后；其他情况下append会直接调用put方法。所以，使用SparseArray添加元素时，优先使用append方法而不是put。
如果没有特别指定，SparseArray的初始大小为10，每次扩容之后大小为之前的2倍。
3. 时间复杂度分析
查找：当查找元素时，会使用二分查找，所以SparseArray的查找时间复杂度是O(logN)。
删除：当删除元素时，会先查找该元素，然后标记值为DELETED，所以删除的时间复杂度也是O(logN)。
添加：当使用put方法添加元素时，会先查找元素，如果找到对应的key，或者最接近的元素value是DELETED，那么就直接赋值，这种情况的时间复杂度是O(logN)。
如果触发了垃圾回收或者扩容，那么时间复杂度就是O(N)，这是最坏时间复杂度。
当使用append方法添加数据，且数据为正序插入时，时间复杂度为O(1)，其他情况下时间复杂度同put。
4. 小结
- SparseArray用法类似于HashMap，但key恒定为整型。
- SparseArray通过
mKeys和mValues两个相等长度的数组来实现键值对的一一对应，其中mKeys是升序的。 - 时间复杂度分析：
因为查找元素使用二分法，所以SparseArray删改查平均时间复杂度均为O(logN)；添加元素由于垃圾回收gc()和插入元素insert都可能会进行数组复制的原因，时间复杂度最好是O(logN)，最坏是O(N)。 - 和HashMap相比，SparseArray的优势是：
1、使用int[]保存key，不用拆装箱，也没有复杂的运算，在数据量小时实际效率比较高；
2、除了数组没有额外的数据结构，节省空间；
劣势是：
1、在数据量较大以后，效率很低； - SparseArray可以看做是用时间换空间的数据结构。
二、ArrayMap
ArrayMap是将key和value保存在同一个数组中的集合类数据结构。
1. ArrayMap的用法
ArrayMap的用法也类似于SparseArray，就不多做赘述。
2. ArrayMap的原理
不同于SparseArray，ArrayMap将key和value储存在同一个数组mArray中，并使用升序数组mHashes保存了各个元素的哈希值。
其中，第i个元素的哈希值为mHashes[i]，key为mArray[2i]，value为mArray[2i+1]。元素的总数量为mSize。
查找
ArrayMap的核心在于查找，也就是如何找到对应的键值对在数组中的存放位置，对应的是ArrayMap的indexOf()方法。
由于mHashes是升序数组，所以先计算对应key的哈希值，通过二分法查找到mHashes中对应的哈希值。如果查找到的key与待查找的key不同，则在mArray中以当前key为中心，往左右依次匹配，直到查找到对应的key。
插入
在ArrayMap中插入新元素，首先检查容量是否达到上限，如果达到上限会进行扩容；扩容后的大小为原大小的1.5倍。
然后，通过System.arraycopy将待插入元素右侧的所有元素往右移动（mHashes移动一位，mArray移动两位），将元素插入。
插入后，mSize加一。
删除
删除存在的元素，首先找到该元素，然后通过System.arraycopy将数组右边的所有元素往左移动（mHashes移动一位，mArray移动两位）。如果删除元素之后，实际元素个数mSize小于阈值（mHashes数组长度的1/3），那么会进行减容；减容后的大小为mSize的1.5倍。
3. 时间复杂度分析
查找
查找元素要经历两次：第一次是通过二分查找在mHashes数组中找到对应的哈希值，第二次是通过第一次查找的结果在mArray中找到对应的key。
第一次查找时间复杂度为O(logN)，第二次查找根据哈希碰撞的情况，最好为O(1)，最坏为O(n)。所以总的时间复杂度最好为O(logN)，最坏为O(N)。因为实际情况下哈希碰撞不会经常出现，所以平均时间复杂度可以近似看做O(logN)。
插入
因为插入的过程会进行数组的复制，所以理论时间复杂度为O(N)。
删除
同插入。
4. 小结
- ArrayMap通过升序数组
mHashes数组保存了元素的哈希值，mArray数组保存了元素的key-value。其中，对于第i个元素，其哈希值为mHashes[i]，key为mArray[2i]，value为mArray[2i+1]。 - ArrayMap在添加元素和删除元素时，都会进行数组的复制。
- 与SparseArray类似，ArrayMap相对于HashMap节约了空间，但是降低了效率，是用时间换空间的数据结构。
三、总结
SparseArray和ArrayMap都是通过数组实现的数据结构，二者使用方式类似。其中SparseArray是通过两个数组分别保存key和value，且key只能是整型；而ArrayMap是通过一个数组保存哈希值，另一个数组同时保存key和value。二者查找元素都是通过二分查找实现。
SparseArray和ArrayMap与HashMap相比，都是用时间换空间的数据结构，可以节约运行内存，但是会降低效率。如果应用更追求占用较小的内存，且数据量小，则使用SparseArray/ArrayMap；追求更快的运行速度，或数据量大，则使用HashMap。
SparseArray有延迟删除的机制，可以有效的提高效率；ArrayMap即时删除，且有减容机制，可以有效的节省空间。
当使用SparseArray添加数据时，优先使用
append方法，而不是put方法。
