这篇文章将讲述在 Android 开发中为什么以及什么时候用ArrayMap和SparseArray替代 HashMap。
在需要存储 key -> value 键值数据时，最先想到的就是HashMap。但是在使用 HashMap 时，Android Studio 会提示用 ArrayMap 替换 HashMap，下面就让我们探索 ArrayMap 的内部原理，以便知道什么时候用 ArrayMap 更好。
HashMap vs ArrayMap
HashMap 所在包：java.util.HashMap
ArrayMap 所在包：android.util.ArrayMap 和 android.support.v4.util.ArrayMap
support.v4 包中的是为 android 低版本提供兼容的。
HashMap 和 ArrayMap 都支持 key 为 null，都是线程不安全的。
下面是 ArrayMap 源码中的文档说明：
ArrayMap is a generic key->value mapping data structure that is designed to be more memory efficient than a traditional HashMap. It keeps its mappings in an array data structure — an integer array of hash codes for each item, and an Object array of the key/value pairs. This allows it to avoid having to create an extra object for every entry put in to the map, and it also tries to control the growth of the size of these arrays more aggressively (since growing them only requires copying the entries in the array, not rebuilding a hash map).
Note that this implementation is not intended to be appropriate for data structures that may contain large numbers of items. It is generally slower than a traditional HashMap, since lookups require a binary search and adds and removes require inserting and deleting entries in the array. For containers holding up to hundreds of items, the performance difference is not significant, less than 50%.
中文大致为：
ArrayMap 是一种泛型键值映射的数据结构，比传统的 HashMap 更节省内存。它通过数组来存储映射关系 – 一个 int 数组存储 key 的 hash code，一个 Object 数组存储 key/value 对。这种设计可以避免在插入元素到 map 时创建额外的对象，并且可以更方便地控制这些数组长度的增长（因为长度的增长只需要复制数组中的元素，而不用重新创建一个 hash map）。
注意这种实现不适合大容量的数据结构，它会比传统的 HashMap 更慢，因为查询利用二分法查找，新增删除元素需要插入和删除数组中值。对于容量最多上百个的数据来说，性能的差别并不大，低于50%.
HashMap
HashMap 基本上就是一个 HashMapEntry 的数组。HashMapEntry 类的内部属性有：
final 的 key
final 的 hash 值
value
下一个 Entry 的指针
key/value 键值对插入到 HashMap 中的内部过程：
计算 key 的 hash code，并把 hash 值保存到 HashMapEntry 类
根据 hash 值得到 entry 存放的位置
如果该位置已经有元素（即单向链表），那么把新元素插入到该链表的最后；如果没有元素的话，直接插入到该位置
当你根据 key 查询 value 时，时间复杂度为 O(1)。
这个设计最主要的是牺牲更多的空间来换取时间。更详细的 HashMap 内部原理请看 Java HashMap 的工作原理
缺点：
每次插入都要封装额外的 HashMapEntry 对象，这会影响内存使用和 GC。
每次 HashMap 扩容时都要重新排列数组，这是一个很重的操作。
在 Android 中，对于大型应用来说内存非常重要，因为持续的分配或重新分配内存时，GC 会产生，这会导致 android 应用的卡顿。
GC 会影响应用的性能
在 GC 过程中你的应用是会被阻塞的，最终就会导致应用的掉帧或卡顿。
ArrayMap
ArrayMap 内部用 2 个数组，Object[] mArray 存放对象，int[] mHashes 存放 hash值。当一个键值对插入时：
key/value 为基本类型时，会被自动装箱
key 对象插入到 mArray 数组的下一个可用位置
value 对象也插入到 mArray 数组中 key 位置的下一个位置
计算 key 的 hash 值，并插入到 mHashes 数组的下一个可用位置
查询 key 时：
计算 key 的 hash 值
根据 hash 值用二分法查找查询 mHashes 数组，时间复杂度为 O(logN)
获取 hash 值的 index 后，key 在 mArray 的位置就是 2 index，value 的位置就是 2 index + 1
虽然对比 HashMap 时间负责度从 O(1) 增长到 O(logN)，但是更节省内存。当数据容量大约为 100 时，时间的差别并不大，然而内存消耗更低。
Android 中推荐数据结构
ArrayMap<K, V>替代HashMap<K, V>ArraySet<K, V>替代HashSet<K, V>SparseArray<V>替代HashMap<Integer, V>SparseBooleanArray替代HashMap<Integer, Boolean>SparseIntArray替代HashMap<Integer, Integer>SparseLongArray替代HashMap<Integer, Long>LongSparseArray<V>替代HashMap<Long, V>
…
原文链接：Android App Optimization Using ArrayMap and SparseArray
