Android SparseArray

SparseArray（稀疏数组）

SparseArray是Android系统中独有的数据结构，在标准的JDK中并不存在。该结构在Android内部被用来替代HashMap<Integer,E>的实现形式。相较于常规方式，SparseArray在内存使用上更加高效。虽然其功能与Map相似，但具体的实现机制却与HashMap存在显著差异。SparseArray采用两个一维数组分别存储键（int类型）和值，而HashMap则依赖于一维数组加单链表的结构。

由于SparseArray没有额外的Entry对象，因此其占用的内存空间相对较小。对于数据量较少的情况，其性能通常比HashMap高出0—50%。

该结构具备以下几个重要特征：

①以键值对的形式进行存储，并基于二分查找算法实现检索功能，因此查找的时间复杂度为O(LogN)；

②SparseArray直接使用int作为键，避免了HashMap中Integer类型的装箱和拆箱操作，从而提升了运行效率，并且int类型的存储开销远小于Integer；（不支持任意类型的键，仅允许使用int类型作为键）

③键值始终按照升序排列，无论经历了多少次插入操作，键数组中的元素总是从小到大排序；（键值之间可能并不连续）

④采用了延迟删除机制（这是为了优化数组删除和扩容时带来的开销问题）；

SparseArray适用于数据量不大、并且键为数字