ArrayMap,SparseArray,HashMap特性VS

本篇是入门教程，旨在短小精悍，简略介绍概要设计，面对源码时也知如何下手，深入理解细节请阅读源码。

HashMap

用得多，不解释。

SimpleArrayMap

关键代码

int[] mHashes;
Object[] mArray;
int mSize;

无父类，先看图。

ArrayMap

hash值按顺序装在二分排序数组中，其中hash1<hash2<hash3。

数组的index用于查找目标key对象和value对象。

有一个小知识点

~0 = -1;
~1 = -2;

ArrayMap

在SimpleArrayMap的基础上通过MapCollections增加Iterator。

SparseArray

关键代码

private int[] mKeys;
private Object[] mValues;
private int mSize;

无父类，看图

SparseArray

key是int型，按顺序装在二分排序数组中，其中k1<k2<k3<k。

一个key对应一个object。

SparseIntArray,SparseLongArray,SpaesrBooleanArray

与SparseArray类似， mValues数组换成简单类型，由此节省了三种对象(Entry,Key,Value)。

总结&对比

HashMap

• 包装类型的key和value
• 计算对象的哈希值
• 包含下一个Entry的指针

缺点

自动装拆箱的操作会对内存和GC有影响。

HashMapEntry是一层额外的封装

每次扩容时会重新排列（参考HashMap.transfer方法）

Hash算法不佳导致退化成链表

ArrayMap

API 19（Kitkat）中新增，低版本可以用Support库里的代替

• Object数组是自动装箱的（不包括hash数组）
• Object数组key和value是相邻的
• key的哈希值放在hash数组内
• 二分查找的时间复杂度是O(logN)
• hash数组的index * 2是对应Object数组的值

对比HashMap，并没有解决自动装箱问题，但对于大多数app而言，使用时间复杂度来赢取空间复杂度是值得的。

SparseArray

• values数组仍是自动装箱
• 二分查找的时间复杂度是O(logN)
• keys数组的index直接对应values数组

与HashMap对比，没了Entry和key对象，而且放弃了hash转而使用二分查找，对于扩容来说更轻量了。

总而言之，SparseArray和ArrayMap减少了对象的创建，对于集合数量比较少（千以下）的的性能提升有限，而且并不保证插入顺序。