SparseArray与ArrayMap

SparseArray

继承自Object，实现了 Cloneable

千以内的数据，使用SparseArray 替代HashMap<Integer,Object> 以略微性能的代价 来降低内存消耗。

==特点==：

• 将整数与对象建立映射，与普通的对象数组相比，其允许索引间隙（如：1，3，5这种存储）；
• 避免了使用 HashMap<Integer,Object> 的自动装箱，而且相对Entry存储减少了额外的对象开销；
• 其对元素的存储根据key值进行升序自动排序。通过keyAt 与 valueAt 利用for 循环，可以对其进行遍历。
• 每次添加or删除元素时，都需要进行二分法查找，当数据量比较大时性能比较低。所以SparseArray仅限于在千以内的数据量时使用，此时的性能差异不显著，小于50%。以此 换来更节省的内存。
• 为了提高性能，在删除一个元素时做了一个优化：调用 remove 方法时，并没有马上从数组中将其删除，而是将其标记为DELETE，等待触发任何一种需要遍历key的操作（如：put，keyAy,valueAt等）时，才会通过自定义的gc方法，将DELETE标记的元素回收（真正删除DELETE的元素并将后面的元素进行移位处理）。

翻译：

SparseArrays将整数映射到对象。与普通的对象数组不同，SparArray的索引中可能有间隙。它的目的是比使用HashMap将整数映射到对象更节省内存，这是因为它避免了key的自动装箱，而且它的数据结构不依赖于每个映射的额外条目对象。

注意，这个容器将其映射保存在数组数据结构中，使用二分查找key。该实现不适合可能包含大量数据的场景。它通常比传统的HashMap慢，因为查找需要二进制搜索，添加和删除需要插入和删除数组中的条目。对于容纳数百件物品的容器，性能差异不显著，小于50%。

为了提高性能，容器在删除key时包含了一个优化:它没有立即压缩数组，而是将删除的条目标记为deleted。然后，可以对同一个key重用该条目，或者稍后在所有已删除条目的单个垃圾收集步骤中压缩该条目。在任何需要增长数组或检索映射大小或条目值的时候，都需要执行此垃圾收集。

可以使用keyAt(int)和valueAt(int)对容器中的项进行迭代。使用带有索引升序值的keyAt(int)遍历键，将按升序返回key，或者在valueAt(int)的情况下，按升序返回与key对应的value。

ArrayMap

继承 Object ，实现 Map<K,V>

• 允许 null key，null value
• 内部实现使用了两个数组：一个保存hash的数组，一个是保存key、value的数组（数组中每个key值索引+1的位置存储着value）
• 初始默认容量为0，当存入第一个数据时，其会自动扩容为 4，其后是8，8之后则是1.5倍的扩容。
• 适用于数据了千级别以内

翻译：

ArrayMap是一个通用键->值映射数据结构，它的设计比传统的{@link java.util.HashMap}内存效率更高。它将其映射保存在数组数据结构中——每个项的哈希码整数数组和键/值对的对象数组。这允许它来避免为每个条目创建一个额外的对象放在map上,并试图控制这些数组的大小更积极的增长(增长因为他们只需要复制条目数组,而不是重建一个散列映射)。

注意，这个容器将其映射保存在数组数据结构中，使用二分查找key。该实现不适合可能包含大量数据的场景。它通常比传统的HashMap慢，因为查找需要二进制搜索，添加和删除需要插入和删除数组中的条目。对于容纳数百件物品的容器，性能差异不显著，小于50%。

由于这个容器的目的是更好地平衡内存使用，因此与大多数其他标准Java容器不同，它将在从数组中删除项时收缩数组。目前，您无法控制这种收缩——如果您设置了一个容量，然后删除了一个项，它可能会减少容量，以便更好地匹配当前的大小。在未来，一个明确的要求设置容量应该关闭这种激进的收缩行为。

关于ArrayMap的存储原理

• 计算key的hash值，根据key的hash值计算出其在 mHashes 中的索引index；

• 这个hash的index 对应着 key、value具体对象在 mArray 中的索引

  • index << 1 对应 key 的索引
  • index << 1 + 1 对应 value 的索引