SparseArray、ArrayMap、HashMap 之间的

本文主要是从数据结构、内存优化、性能、缓存、扩容等几个方面对SparseArray、ArrayMap 和 HashMap 做一个比较，具体的实现原理可以点击下面的链接进行查看。

• SparseArray
• ArrayMap
• HashMap

数据结构

SparseArray 和 ArrayMap 采用的都是两个数组，而 HashMap 采用的是 数组 + 链表 + 红黑树（1.7 版本以上）。

内存优化

• SparseArray 比 ArrayMap 节省 1/3 的内存，但 SparseArray 只能存储 key 为 int 类型的 Map。
• ArrayMap 比 HashMap 更节省内存，综合性能方面再数据量不大的情况下，推荐使用 ArrayMap。
• HashMap 需要创建一个额外的数据结构 Node，且容量的利用率比 ArrayMap 低，整体更消耗内存。

性能方面

• SparseArray 查找的时间复杂度为 O(logN)，适合频繁删除和插入来回执行的场景，性能比较好。
• ArrayMap 查找时间复杂度也是 O(logN)，ArrayMap 增加、删除操作需要移动成员，速度比较慢，对于个数小于 1000 的情况下，性能基本没有明显差异。
• 缓存机制。
• SparseArray 有延迟回收机制，提供删除效率（标记为DELETED），同时减少数组成员来回拷贝的次数。
• HashMap 没有缓存机制。

扩容机制

• SparseArray 容量满时触发扩容机制，如果当前容量小于等于 4 则扩容 为 8，否则扩容容量为原容量的 2 倍。
• ArrayMap 容量满时将容量扩大至原来的 1.5 倍，在容量不足 1/3 时触发内存收缩至原来的 0.5 倍。
• HashMap 在容量 > 容量 * 负载因子（默认0.75）时将容量扩大至原来的 2 倍，且没有内存收缩机制。

参考

深度解读ArrayMap优势与缺陷