sparse Android数据结构之SparseArray

而SparseArray的底层数据结构更简单，只有int[] mKeys和Object[] mValues两个数组。那这里就有个问题了：不同于HashMap专门用一个Entry的类存放key跟value，SpareArray里key和value分别存放在两个数组里，那key和value是怎么对应上的？

答案就是，是根据index对应的，mKeys和mValues中index一样的key和value就是相互对应的。所以SparseArray实际存储的数据看起来是这样的：

HashMap的取操作在hash分桶时时间复杂度为O(1)，但是在发生hash冲突的时候最后会在链表中顺序查找，而SparseArray的取操作完全依赖于二分查找，时间复杂度理论上总是O(nlogn)，没有hash冲突导致访问慢的问题；不过HashMap的hash冲突一般很少，总体来说SparseArray总是比HashMap慢些；而且二分查找的时间复杂度也决定了SparseArray不适合大量数据的场景。

删/gc

SparseArray删除数据是通过delete(int key)方法删除的。在删除一条数据的时候，不是直接执行实际的删除操作，而是先把要删除的数据标记为DELETE状态，在需要获取size、扩容、取数据的时候，会执行gc，一次性真正把前面标记的所有删除数据删掉。

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

不过需要注意的是，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不行

最后

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

转载自今日头条 Android架构师丨小熊