认识一下Android中的SparseArray与ArrayMap，它们有何区别？

认识SparseArray

SparseArray是用来存储key-value数据的,与HashMap类似.但它只存储key为int类型的key-value数据,这样避免了key的装箱操作和分配空间. 建议平时用SparseArray<V>替换HashMap<Integer,V>.

SparseArray是专门设计来节省空间开销的,所以数据存储得较为紧凑.key和value是单独用一个数组来存储的,且数组是按大小排好序,每次增删改查等操作都用二分查找来进行，效率高.

代码示例

SparseArray<String> sparseArray = new SparseArray<>();
sparseArray.put(39998, "0000");
sparseArray.put(26, "0000");
sparseArray.put(11, "1000");
sparseArray.put(13, "1000");

执行完成,在内存中的情况如下:

可以知道

• 有2个数组用来存储数据,mKeys和mValues
• key数组是从前往后存储数据,且中间没有空隙
• key数组是有序的
• key与value数组一一对应

小结

SparseArray是Android中特有的数据结构，用来替代HashMap。 数据结构中有两个数组，一个是int[]数组存放key，一个是Object[]数组存放value。

SparseArray比HashMap少了基本数据的自动装箱操作，且不需要额外的结构体，单个元素存储成本低，在数据量小的情况下，随机访问的效率很高。但缺点也显而易见，增删的效率比较低，在数据量比较大的时候，调用gc拷贝数组工作量大。

另外Android还提供了SparseIntArray(int:int)， SparseBooleanArray(int:boolean)， SparseLongArray(int:long)等，就是把对应的value换成基本数据类型。

认识ArrayMap

ArrayMap是一种通用的key-value映射的数据结构,与上面SparseArray类似.但SparseArray只能存储int类型的key,而ArrayMap可以存储其他类型的key.所熟悉的Bundle底层就是用的它存储数据的.

ArrayMap与HashMap不同,它数据结构是两个数组,一个数组(mHashes)用来存放key的hashcode,一个数组(mArray)用来存放key和value. 底层数据结构用图展示出来如下:

为了减少频繁的创建和回收Map对象,ArrayMap采用两个大小为10的缓存队列来分别保存大小为4和8的ArrayMap对象.为节省内存,它还有内存扩张和内存收缩策略.

缓存机制是很有必要的，ArrayMap 的使用量蛮大的，因为Bundle 的底层就是用 ArrayMap 来存数据的。 那Bundle 为啥用 ArrayMap 而不用 SparseArray 呢？

除put 方法，ArrayMap 和 SparseArray 都有 append 方法，和 put 很相似，append 的差异在于该方法不会去做扩容操作，是一个轻量级的插入方法。在明确知道肯定会插入队尾的情况下使用 append 性能更好，put 是二分查找，时间复杂度 O(logn)，而 append 时间复杂度为 O(1)。

另外 ArraySet 也是 Android 特有数据结构，用来替代 HashSet ，与ArrayMap 几乎一致，包含了缓存机制、扩容机制等。