SparseArray 和 ArrayMap

ArrayMap

Android 专门针对内存优化而设计的，用于取代 Java API 中的 HashMap 数据结构。为了更进一步优化key 是 int 类型的 Map，Android 再次提供效率更高的数据结构 SparseArray，可避免自动装箱过程。对于 key 为其他类型则可使用 ArrayMap。
HashMap 的查找和插入时间复杂度为 O (1)的代价是牺牲大量的内存来实现的，而 SparseArray 和 ArrayMap性能略逊于 HashMap，但更节省内存。

源码分析

ArrayMap 的内部实现是两个数组，一个 int 数组存储 key 的哈希值，一个对象数组保存 key 和 value，内部使用二分法对 key 进行排序，所以在添加、删除、查找数据的时候，都会使用二分法查找，适合小数据量操作，如果在数据量比较大的情况下，那么它的性能将退化。而 HashMap 内部则是数组+链表结构，所以在数据量较小的时候，HashMap 的 Entry Array 比 ArrayMap 占用更多的内存。

在 Android 中，建议用 ArrayMap 来替换 HashMap。ArrayMap 和 HashMap 都是线程不安全的。

public class SimpleArrayMap<K, V> {

    int[] mHashes;	//由 key 的 hashCode 所组成的数组，从小到大排序
    Object[] mArray;	// 由key-value键值对所组成的数组，是mHashes大小的2倍；
    int mSize;	//
 }

• mArray 是一个记录着 key-value 键值对所组成的数组，是 mHashes 大小的2倍；
• 其中 mSize 记录着该 ArrayMap 对象中有多少对数据，执行 put 或者 append 操作，则 mSize 会加一，执行 remove，mSize 则减一。mSize 往往小于 mHashes. length，如果大于或等于，则说明需要扩容。

更多源码分析可以参考：深度解读ArrayMap优势与缺陷

• 扩容机制
  • ArrayMap 是在容量满的时机触发容量扩大至原来的1.5倍，在容量不足1/3时触发内存收缩至原来的0.5倍，更节省的内存扩容机制
  • HashMap 是在容量的0.75倍时触发容量扩大至原来的2倍，且没有内存收缩机制。HashMap 扩容过程有 hash 重建，相对耗时。所以能大致知道数据量，可指定创建指定容量的对象，能减少性能浪费。

ArrayMap 相比 HashMap 在内存占用方面更为节省的主要原因是其内部数据结构设计的差异。

内部数据结构设计：
- HashMap：HashMap 内部使用数组 + 链表/红黑树的结构来存储 key-value 对。在 HashMap 中，数组的大小（即容量）通常会选择一个比较大的值，以减少哈希冲突的概率，但这也会导致在数据量较小的情况下可能存在大量未被利用的空间。
- ArrayMap：ArrayMap 内部使用两个数组来分别存储 key 和 value，而且默认情况下 ArrayMap 使用稀疏数组进行存储，只有在必要时才会进行数组扩容操作。这种设计使得 ArrayMap 在数据量较小的情况下可以更加紧凑地存储 key-value 对，减少了不必要的内存消耗。

总的来说，由于 ArrayMap 的内部数据结构更为简单和紧凑，在数据量较小的情况下可以更有效地利用内存空间，相对于 HashMap 来说更为节省内存。但是在数据量较大或需要频繁进行插入、删除操作的情况下，HashMap 可能会更适合，因为其在处理大量数据时性能更为优秀。
[[HashMap、lru、散列表]]

ArraySet：和 ArrayMap 的目的类似，用来提高 HashSet 的效率。使用方法跟 HashSet 类似
ArrayMap 假设 key 类型为其他的类型，则使用 ArrayMap，获取数据简单
map. keyAt (0)
map. valueAt (0)

SparseArray

SparseArray 和 ArrayMap 类似，但是 SparseArray 只能存储 key 为 int 型的，它比 ArrayMap 少了计算 key 的哈希值，同时对象数组只需要存 value 即可，这也就避免了 key 的装箱操作和分配空间，，建议用 SparseArray<V> 替换 HashMap<Integer,V>。

类似的还有 SparseIntArray 代替 HashMap<Integer,Integer> 等。
SparseBooleanArray: 当 map 的结构为 Map<Integer,Boolean>的时候使用，效率较高。
SparseLongArray: 当 map 的结构为 Map<Integer,Long>的时候使用，效率较高。
LongSparseArray: 当 map 的结构为 Map<Long,Value>的时候使用，效率较高。

• SparseArray 的内部实现是两个数组，一个 int 数组是存储对象数据对应下标，一个对象数组保存 value，在 put 的通过二分法放 int 数组去，查找也是二分法查找
• 内部使用二分法对 key 进行排序，所以在添加、删除、查找数据的时候，都会使用二分法查找，只适合于小数据量操作，通常情况下要比传统的 HashMap 慢，因为查找是用二分查找法搜索，添加和删除需要对数组进行添加和删除。

源码分析

• key 是 int[]，比 hashmap 的 key 是对象，例如 Integer 8个字节，int 4个字节更耗内存，还得装箱拆箱
  
• 默认负载因子为0.75，必然会有空间的浪费，需要用来存数据，而 SparseArray 不会浪费空间
• 为了提高性能，该容器提供了一个优化：当删除 key 键时，不是立马删除这一项，而是留下需要删除的选项给一个删除的标记（放 object），避免数组的移动。该条目可以被重新用于相同的 key, 或者实际数据大于等于数组容量，都有可能会主动调用gc()方法来清理DELETE数据。
  好想法：如果已经删除，直接放进去（15删了，放16），删除的越多越好。
  
  

Android中的SparseArray你了解吗

public static int growSize(int currentSize) {
    return currentSize <= 4 ? 8 : currentSize * 2;
}

扩容：当前 Size <= 4 时恒定大小为8，否则就是 Size 的两倍了。

Bundle

Bundle 被用来传递数据，为什么不用 HashMap 代替

1. Bundle 内部是由 ArrayMap 实现的，ArrayMap 在设计上比传统的 HashMap 更多考虑的是内存优化。
2. Bundle 使用的是 Parcelable 序列化，而 HashMap 使用 Serializable 序列化。