详细介绍：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中的某个元素进行增删改操作的时候，是不能保证数据的一致性的。

底层数据结构

• 红黑树是一个自平衡的二叉查找树，也就是说红黑树的查找效率是非常的高，查找效率会从链表的o(n)降低为o(logn)。

  
  image.png