详细介绍：http://gityuan.com/2019/01/13/arraymap/
SparseArray
SparseArray 是 Android 在 Android SdK 为我们提供的一个基础的数据结构，其功能类似于 HashMap。与 HashMap 不同的是它的 Key 只能是 int 值，不能是其他的类型。
- SparseArray采用了延迟删除的机制，通过将删除KEY的Value设置DELETED，方便之后对该下标的存储进行复用；
- 其内部主要通过 2 个数组来存储 key 和 value，分别是 int[] 和 Object[]。这也限定了其 key 只能为 int 类型，且 key 不能重复，否则会发生覆盖。
- 一切操作都是基于二分查找算法，将 key 以升序的方法 “紧凑” 的排列在一起，从而提高内存的利用率以及访问的效率。相比较 HashMap 而言，这是典型的时间换空间的策略。
- 使用二分查找，时间复杂度为O(LogN)，如果没有查找到，那么取反返回左边界，再取反后，左边界即为应该插入的数组下标；
- 如果无法直接插入，则根据mGarbage标识（是否有潜在延迟删除的无效数据），进行数据清除，再通过System.arraycopy进行数组后移，将目标元素插入二分查找左边界对应的下标；
- mSize 小于等于keys.length，二分查找的右边界以mSize为准；mSize包含了延迟删除后的元素个数；
- 查找数据的时候使用的是二分法，明显比通过hashcode慢，所以数据越大，查找速度慢的劣势越明显，所以SparseArray适于数据一千以内的场景中。
优点：
- 避免了基本数据类型的装箱操作
- 不需要额外的结构体，单个元素的存储成本更低
- 数据量小的情况下，随机访问的效率更高
缺点：
- 插入操作需要复制数组，增删效率降低
- 数据量巨大时，复制数组成本巨大，gc()成本也巨大
- 数据量巨大时，查询效率也会明显下降
HashMap
- HashMap最早是在jdk1.2中开始出现的，一直到jdk1.7一直没有太大的变化。但是到了jdk1.8突然进行了一个很大的改动。其中一个最显著的改动就是：之前jdk1.7的存储结构是数组+链表，到了jdk1.8变成了数组+链表+红黑树。另外，HashMap是非线程安全的，也就是说在多个线程同时对HashMap中的某个元素进行增删改操作的时候，是不能保证数据的一致性的。
底层数据结构
image.png
-
红黑树是一个自平衡的二叉查找树，也就是说红黑树的查找效率是非常的高，查找效率会从链表的o(n)降低为o(logn)。
image.png
