SparseArray到底哪点比HashMap好

sparsearray是android里为<interger,object>这样的hashmap而专门写的class,目的是提高效率，其核心是折半查找函数（binarysearch）。

所以android开发中官方推荐：当使用hashmap(k, v),如果k为整数类型时,使用sparsearray的效率更高。

那我们看源码来分析下，

和hashmap的数据结构不同,hashmap是使用数组+链表的数据结构存储键值对,而sparsearray只是用了两个数组进行存储。

我们知道链表的时间复杂度是很高的，这估计也是造成hashmap时间复杂度高的一个原因。

containerhelpers类提供了二分查找算法，这也一定程度上提高了查找的效率

put函数的逻辑：

通过二分查找算法,计算key的索引值.

如果索引值大于0,说明有key对应的value存在,直接替换value即可.

如果索引值小于0,对索引值取反,获取key应该插入的坐标i.

判断是否需要扩容:1.需要扩容,则先扩容; 2.不需要扩容,则利用system.arraycopy移动相应的元素,进行(key,value)键值对插入.

get函数就是利用二分查找获取key的下标,然后从object[] value数组中根据下标获取值. 

之所以sparsearray号称比hashmap有更好的性能:

sparsearray更加节约内存,一个int[]数组存储所有的key,一个object[] 数组存储所有的value.

hashmap遇到冲突时,时间复杂度为o(n).而sparsearray不会有冲突,采用二分搜索算法,时间复杂度为o(lgn).

通过上面的源码分析，我们不难得出：

正式因为sparsearray采用了数组这种形式，才使得我们的key在做hash运算的时候，通过二分查找时间复杂度降低了，从而提高了效率。

通过二分查找保证查询效率为o(lgn).而hashmap在未冲突的情况下是o(1),冲突的情况下是o(n).