我正在参加「启航方案」

认识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");

执行完结,在内存中的状况如下:

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

能够知道

  • 有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. 底层数据结构用图展现出来如下:

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

为了减少频频的创建和回收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 几乎一致，包含了缓存机制、扩容机制等。