Android集合SparseArray、ArrayMap使用场景

SparseArray

1、SparseArray比HashMap更省内存

在某些条件下性能更好，主要是因为它

一：避免了对key的自动装箱（int转为Integer类型），它内部则是通过两个数组来进行数据存储的，一个存储key，另外一个存储value，为了优化性能，它内部对数据还采取了

二：压缩的方式来表示稀疏数组的数据，从而节约内存空间，我们从源码中可以看到key和value分别是用数组表示：

    private int[] mKeys;
    private Object[] mValues;

我们可以看到，SparseArray只能存储key为int类型的数据。

2、查找速度慢了，由于依赖于二分查找，所以数据量不要太大

同时，SparseArray在存储和读取数据时候，使用的是二分查找法，时间复杂度是log2N

也就是在put添加数据的时候，会使用二分查找法和之前的key比较当前我们添加的元素的key的大小，然后按照从小到大的顺序排列好，所以，SparseArray存储的元素都是按元素的key值从小到大排列好的。 而在获取数据的时候，也是使用二分查找法判断元素的位置，时间复杂度是log2N，所以，在获取数据的时候非常快，比HashMap快的多，因为HashMap获取数据是通过遍历Entry[]数组来得到对应的元素。

Q1：HashMap底层查找的时间复杂度？ 这个问题问的是查找的时间夫复杂度，考察的是HashMap底层数据的存储，我们直到java8之后，HashMap的存储结构为数组+链表+红黑树。所以结合HashMap的存储结构来进行回答。理想情况下，哈希不冲突，可以直接找到结果，所以O(1)在最差的情况下，HashMap保存的数据都在链表中保存，所以需要遍历链表，所以时间复杂度为O(n)。但是一个好的Hash函数，冲突是比较少的，且HashMap在达到阈值时，还会自动扩展。所以一般情况下，可以认为理想情况下的O(1)就是HashMap查找的时间复杂度。  

Q2：Bundle内部是由ArrayMap实现的

面试：bundle传输相关_沙漠一只雕得儿得儿的博客-CSDN博客_bundle大小限制

1、Bundle内部是由ArrayMap实现的，在操作速度和内存占用上都具有优势，因此使用Bundle来传递数据，可以保证更快的速度和更少的内存占用。

2、HashMap使用Serializable进行序列化，而Bundle则是使用Parcelable进行序列化。而在Android平台中，更推荐使用Parcelable实现序列化，虽然写法复杂，但是开销更小。 

SparseArray应用场景：

虽说SparseArray性能比较好，但是由于其添加、查找、删除数据都需要先进行一次二分查找，所以在数据量大的情况下性能并不明显，将降低至少50%。

满足下面两个条件我们可以使用SparseArray代替HashMap：

• 数据量不大，最好在千级以内，如果在数据量比较大的情况下，那么它的性能将退化至少50%。
• key必须为int类型，这中情况下的HashMap可以用SparseArray代替

SparseArray和ArrayMap都差不多，使用哪个呢？

假设数据量都在千级以内的情况下：

1、如果key的类型已经确定为int类型，那么使用SparseArray，因为它避免了自动装箱的过程，如果key为long类型，它还提供了一个LongSparseArray来确保key为long类型时的使用

2、如果key类型为其它的类型，则使用ArrayMap

总结优缺点和应用场景 1.优点

避免了基本数据类型的装箱操作 会定期通过gc函数来清理内存，内存利用率高 数据量小的情况下，随机访问的效率更高

ArrayMap使用更少的存储单元存储元素 ArrayMap使用int类型的数组存储hash，使用Object类型数组存储k-v键值对，相较于HashMap使用Node存储节点，ArrayMap存储一个元素占用的内存更小。 ArrayMap在扩容时容量变化更小 HashMap在扩容的时候，通常会将容量扩大一倍，而ArrayMap在扩容的时候，如果元素个数超过8，最多扩大自己的1/2。

2.缺点

数据量巨大时，复制数组成本巨大，gc()成本也巨大，查询效率也会明显下降 插入操作需要复制数组，增删效率降低

存储大量（超过1000）元素时比较耗时 在对元素进行查找或者确定待插入元素的位置时使用二分查找，当元素较多时，耗时较长频繁扩容和缩容，可能会产生大量复制操作 ArrayMap在扩容和缩容时需要移动元素，且扩容时容量变化比HashMap小，扩容和缩容的频率可能更高，元素数量过多时，元素的移动可能会对性能产生影响。基于以上优缺点，google给出的建议是当元素数量小于1000时，建议使用Array代替HashMap，效率降低最多不会超过50%

3.应用场景

3.1 数量