SparseArray和ArrayMap

SparseArray

1. 以双数组键值分开的形式存储，基于二分查找获取数据；
2. 采用int作为Key，避免了HashMap的装箱拆箱操作，同时它的数据结构不需要额外的Entry对象
3. 采用了延迟删除的机制（针对数组删除位移问题的优化），在remove时把目标值标记为delete，在下次有符合的值直接放到该位置，就没有位移了

SparseArray与HashMap比较

1. 查询效率：在少量数据上区别不大，但在数量以万为单位时，HashMap更优一点
2. 正序插入：效率比HashMap更快且更省内存
3. 倒序插入：为保证有序，需要对数组里的数据后移，效率最差，HashMap无论正序还是倒序都只需要处理哈希冲突，效率更高

总结

SparseArray是以时间换空间的一种存储方式，在key为整形、元素相对较少的情况下建议使用

ArrayMap

为了节省内存有更加保守的内存扩张以及内存收缩策略

1. 同样采用双数组的形式存储，mHashes记录所有key的hashcode组成的数组，从小到大排序，采用二分查找
2. mArray记录着key-value键值组成的数组，为mHashes大小的2倍；
3. 以追加的形式解决追加的方式，后面的数据全部后移一位
4. 有两个缓存数组：mBaseCache（大小为4）、mTwiceBaseCacheSize（大小为8），都是分别超过10个不再缓存