Android数据结构之SparseArray( 二 ) _Android

看存操作的实现，注释说明了关键点：

文章插图

所以保证所有存储的数据都是有序排列的关键就在于每次插入的时候如何确定插入的新数据插入的位置。上面看到每次确定实际插入的位置是基于二分查找确定的。举个例子：

原先的数据是mIndexs = {1, 4, 6, 8}，size为4
要插入的key是7
第一次二分查找返回的index是-3，说明现在的数据中没有这个index，这个key应该被插入index为3的位置
调用GrowingArrayUtils.insert将7插入index为3的位置，实际会引发mKeys扩容到8，原先的key8往右移
最后的数据是mIndexs = {1, 4, 6 ,7, 8}，保持了有序

其实实际插入数据的过程类似于优化后的插入排序，确定了插入的位置后把这个位置后面的数据移动一位，然后把新数据放入空出来的位置。
取的过程很简单，同样是根据二分查找找到如果有这个key的话它应该在哪个位置，如果找到的index<0反过来就证明了没有这个key：

文章插图

HashMap的取操作在hash分桶时时间复杂度为O(1)，但是在发生hash冲突的时候最后会在链表中顺序查找，而SparseArray的取操作完全依赖于二分查找，时间复杂度理论上总是O(nlogn)，没有hash冲突导致访问慢的问题；不过HashMap的hash冲突一般很少，总体来说SparseArray总是比HashMap慢些；而且二分查找的时间复杂度也决定了SparseArray不适合大量数据的场景。
删/gc
SparseArray删除数据是通过delete(int key)方法删除的。在删除一条数据的时候，不是直接执行实际的删除操作，而是先把要删除的数据标记为DELETE状态，在需要获取size、扩容、取数据的时候，会执行gc，一次性真正把前面标记的所有删除数据删掉。

文章插图

gc的过程有点类似虚拟机的gc中的标记整理算法。具体就是遍历所有数据，收集所有没有被删除的数据移动到最前面。

文章插图

这样做的好处有两个：

如果在刚delete了一条数据后又放了一条相同key的数据进来，这条数据因为被覆盖了后面也不用执行真正的gc了，节省了操作时间
如果一次性delete多条数据，可以把真正的删除操作放在一次gc中而不是多次gc中，节省时间

文章插图

扩容/缩容
前面提到，在put数据的时候可能会引发扩容。扩容的时机很简单，当底层的数组没有空余的空间存放新的数据时就会引发扩容。扩容的算法很简单，基本上就是翻倍，GrowingArrayUtils#growSize：

文章插图

不过需要注意的是，growSize算出来size不一定是扩容操作后真正的size，因为扩容时新的数组是调用ArrayUtils#newUnpaddedArray生成新数组的，这个方法涉及内存对齐，实际返回的数组的size一般比要求的大小要大。
SparseArray是没有缩容机制的。假如前面存了大量的数据导致数组扩容到了1024，哪怕调用clear清空所有数据底层数组的大小还是1024 。所以先存放大量数据在删到只剩少量需要长期持有的数据场景下，用SpareArray可能会导致空间的浪费。
总结

建议使用SparseArray替换HashMap是因为得益于下面几点，SparseArray可能比HashMap更节省内存，而某些android设备上内存是紧缺资源：
避免了Integer的自动装箱
基于index建立的key和value的映射关系相比Map基于Entry结构建立key和value的映射关系节约内存
某些场景如hash冲突下访问速度可能优于hashmap；不适合数据集比较大的场景。
SparseArray没有缩容机制。某些场景下不适合使用，比如：大量地put后大量地delete，然后长久持有SparseArray，导致大量的空位置没法被虚拟机gc，浪费内存
SparseArray一般来说比Hashmap慢，因为二分查找比较慢，而且插入删除数据涉及数组的copy 。在数据集不大时不明显
SparseArray每次插入删除数据都保证了所有存储数据的排列有序
SparseArray可以通过index定位数据，Hashmap不行

最后
如果你看到了这里，觉得文章写得不错就给个赞呗！欢迎大家评论讨论！如果你觉得那里值得改进的，请给我留言。一定会认真查询，修正不足，定期免费分享技术干货。感兴趣的小伙伴可以点一下关注哦。谢谢！