一、概论
在移动设备端，内存资源很珍贵，HashMap 为实现快速查询带来了很大内存的浪费。为此，2013年5月20日 Google 工程师 Dianne Hackborn 在 Android 系统源码中新增 ArrayMap 类，从 Android 源码中发现有不少提交，专门把之前使用 HashMap 的地方改用 ArrayMap，不仅如此，大量的应用开发者中也广为使用。
ArrayMap 是 Android 专门针对内存优化而设计的，用于取代 Java API 中的 HashMap 数据结构。
为了更进一步优化 key 是 int 类型的 Map，Android 再次提供效率更高的数据结构 SparseArray，可避免自动装箱过程。对于 key 为其他类型，则可以使用 ArrayMap。
HashMap 的查找和插入时间复杂度为 O(1) 的代价是牺牲大量的内存来实现的，而 SparseArray 和 ArrayMap 性能略逊于 HashMap，但更节省内存。
接下来带着这几个问题来学习 ArrayMap的底层原理：
- 1）ArrayMap 与 HashMap 有什么差异
- 2）ArrayMap 的优点与缺点
- 3）ArrayMap 与 HashMap 的取舍
二、源码解析
2.1 基本成员变量
public final class ArrayMap<K, V> implements Map<K, V> {
private static final boolean CONCURRENT_MODIFICATION_EXCEPTIONS = true;
private static final int BASE_SIZE = 4; // 容量增量的最小值
private static final int CACHE_SIZE = 10; // 缓存数组的上限
static Object[] mBaseCache; // 用于缓存大小为 4 的 ArrayMap
static Object[] mTwiceBaseCache; // 用于缓存大小为 8 的 ArrayMap
static int mBaseCacheSize; // 缓存大小为 4 的 ArrayMap 的长度
static int mTwiceBaseCacheSize; // 缓存大小为 8 的 ArrayMap 的长度
final boolean mIdentityHashCode;
int[] mHashes; // 由 key 的 hashcode 所组成的数组
Object[] mArray; // 由 key-value 对所组成的数组，是 mHashes 大小的 2 倍
int mSize; // 成员变量的个数
}
ArrayMap 对象的数据储存格式如下图所示：
- mHashes 是一个记录所有 key 的 hashcode 值组成的数组，是从小到大的排序方式
-
mArray 是一个记录着 key-value 键值对所组成的数组，是 mHashes 大小的2倍
ArrayMap 对象的数据储存格式
其中 mSize 记录着该 ArrayMap 对象中有多少对数据，执行 put() 或者 append() 操作，则 mSize 会加 1，执行 remove()，则 mSize 会减 1。
mSize 往往小于 mHashes.length，如果 mSize 大于或等于 mHashes.length，则说明 mHashes 和 mArray 需要扩容。
ArrayMap 类有两个非常重要的静态成员变量 mBaseCache 和 mTwiceBaseCache，用于 ArrayMap 所在进程的全局缓存功能：
- mBaseCache：用于缓存大小为 4 的 ArrayMap，mBaseCacheSize 记录着当前已缓存的数量，超过 10 个则不再缓存
- mTwiceBaseCache：用于缓存大小为 8 的 ArrayMap，mTwiceBaseCacheSize 记录着当前已缓存的数量，超过 10 个则不再缓存。
为了减少频繁地创建和回收 Map 对象，ArrayMap 采用了两个大小为 10 的缓存队列来分别保存大小为 4 和 8 的 Map 对象。为了节省内存使用了更加保守的内存扩张以及内存收缩策略。 接下来分别说说缓存机制和扩容机制。
这也是 ArrayMap 所特有的，与HashMap不同，ArrayMap所具有的缓存机制。
2.2 缓存机制
ArrayMap 是专为 Android 优化而设计的 Map 对象，使用场景比较高频，很多场景可能起初都是数据很少，为了减少频繁地创建和回收，特意设计了两个缓存池，分别缓存大小为 4 和 8 的 ArrayMap 对象。要理解缓存机制，那就需要看看内存分配 (allocArrays) 和内存释放 (freeArrays)。
与其说这是两个缓存池，不如说是两个缓存链
2.2.1 ArrayMap.freeArrays
private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
if (hashes.length == (BASE_SIZE*2)) { // 当释放的是大小为 8 的对象
synchronized (ArrayMap.class) {
// 当大小为 8 的缓存池的数量小于 10 个，则将其放入缓存池
if (mTwiceBaseCacheSize < CACHE_SIZE) {
array[0] = mTwiceBaseCache; // array[0] 指向原来的缓存池
array[1] = hashes;
for (int i=(size<<1)-1; i>=2; i--) {
array[i] = null; // 清空其他数据
}
mTwiceBaseCache = array; // mTwiceBaseCache 指向新加入缓存池的 array
mTwiceBaseCacheSize++;
}
}
} else if (hashes.length == BASE_SIZE) { // 当释放的是大小为 4 的对象，原理同上
synchronized (ArrayMap.class) {
if (mBaseCacheSize < CACHE_SIZE) {
array[0] = mBaseCache;
array[1] = hashes;
for (int i=(size<<1)-1; i>=2; i--) {
array[i] = null;
}
mBaseCache = array;
mBaseCacheSize++;
}
}
}
}
- 最初 mTwiceBaseCache 和 mBaseCache 缓存池中都没有数据，
- 在 freeArrays 释放内存时，如果同时满足释放的 array 大小等于 4 或者 8
- 且相对应的缓冲池个数未达上限，则会把该 arrya 加入到缓存池中。
- 加入的方式是将数组 array 的第 0 个元素指向原有的缓存池，
- 第 1 个元素指向 hashes 数组的地址，
- 第 2 个元素以后的数据全部置为 null。
- 再把缓存池的头部指向最新的 array 的位置，并将该缓存池大小执行加 1 操作。具体如下所示。
dn.net/liuwg1226/article/details/118885316
从这个步骤模型可以看出这是一个缓存链，每个数组的第0个元素都保存上一次的缓存。
ArrayMap 的 freeArrays() 的触发条件：
- 当执行 removeAt() 移除最后一个元素的情况
- 当执行 clear() 清理的情况
- 当执行 ensureCapacity() 在当前容量小于预期- 容量的情况下，先执行 allocArrays，再执行 freeArrays
- 当执行 put() 在容量满的情况下，先执行 allocArrays，再执行 freeArrays
2.2.1 ArrayMap.allocArrays
private void allocArrays(final int size) {
if (size == (BASE_SIZE*2)) { // 当分配大小为 8 的对象，先查看缓存池
synchronized (ArrayMap.class) {
if (mTwiceBaseCache != null) { // 当缓存池不为空时
final Object[] array = mTwiceBaseCache;
mArray = array; // 从缓存池中取出 mArray
mTwiceBaseCache = (Object[])array[0]; // 将缓存池指向上一条缓存地址
mHashes = (int[])array[1]; // 从缓存中 mHashes
array[0] = array[1] = null;
mTwiceBaseCacheSize--; // 缓存池大小减 1
return;
}
}
} else if (size == BASE_SIZE) { // 当分配大小为 4 的对象，原理同上
synchronized (ArrayMap.class) {
if (mBaseCache != null) {
final Object[] array = mBaseCache;
mArray = array;
mBaseCache = (Object[])array[0];
mHashes = (int[])array[1];
array[0] = array[1] = null;
mBaseCacheSize--;
return;
}
}
}
// 分配大小除了 4 和 8 之外的情况，则直接创建新的数组
mHashes = new int[size];
mArray = new Object[size<<1];
}
当 allocArrays 分配内存时，如果所需要分配的大小等于 4 或者 8，且相对应的缓冲池不为空，则会从相应缓存池中取出缓存的 mArray 和 mHashes。
从缓存池取出缓存的方式是：
- 将当前缓存池赋值给 mArray，
- 将缓存池指向上一条缓存地址，
- 将缓存池的第 1 个元素赋值为 mHashes，
- 再把 mArray 的第 0 和第 1 个位置的数据置为 null
-
并将该缓存池大小执行减 1 操作，具体如下所示。
缓存链条获取
ArrayMap 的 allocArrays 的触发时机：
- 当执行 ArrayMap 的构造函数的情况
- 当执行 removeAt() 在满足容量收紧机制的情况
- 当执行 ensureCapacity() 在当前容量小于预期容量的情况下，先执行 allocArrays，再执行 freeArrays
- 当执行 put() 在容量满的情况下，先执行 allocArrays，再执行 freeArrays
这里需要注意的是只有大小为 4 或者 8 的内存分配，才有可能从缓存池取数据，因为 freeArrays 过程放入缓存池的大小只有 4 或 8，对于其他大小的内存分配则需要创建新的数组。
优化小技巧，对于分配数据不超过 8 的对象的情况下，一定要创建 4 或者 8 大小，否则浪费了缓存机制。比如 ArrayMap[7] 就是不友好的写法，建议写成 ArrayMap[8]。
2.3 容量机制
2.3.1 容量扩张
public V put(K key, V value) {
final int osize = mSize;
if (osize >= mHashes.length) { // 当 mSize 大于或等于 mHashes 数组长度时需要扩容
final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))
: (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
allocArrays(n); // 分配更大的内存【小节2.2.2】
}
}
当 mSize 大于或等于 mHashes 数组长度时，则扩容，完成扩容后需要将老的数组拷贝到新分配的数组，并释放老的数组内存。
- 当 map 个数满足条件 osize<4 时，则扩容后的大小为 4
- 当 map 个数满足条件 4<= osize < 8 时，则扩容后的大小为 8
- 当 map 个数满足条件 osize>=8 时，则扩容后的大小为原来的 1.5 倍
可见 ArrayMap 大小在不断增加的过程，size 的取值一般情况依次会是 4，8，12，18，27，40，60，…
2.3.2 容量收紧
public V removeAt(int index) {
final int osize = mSize;
final int nsize;
if (osize > 1) { // 当 mSize 大于 1 的情况，需要根据情况来决定是否要收紧
nsize = osize - 1;
if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
final int n = osize > (BASE_SIZE*2) ? (osize + (osize>>1)) : (BASE_SIZE*2);
allocArrays(n); // 分配更小的内存【小节2.2.2】
}
}
}
当 mHashes 的大小大于 8，且已存储数据的个数 mSize 小于数组空间大小的 1/3 的情况下，需要收紧数据的内容容量，分配新的数组，老的内存靠虚拟机自动回收。
- 如果 mSize<=8，则设置新大小为 8
-
如果 mSize> 8，则设置新大小为 mSize 的1.5倍
也就是说在 mHashes.length 较大的情况下，当 使用量（mSize）不足 1/3 的情况下，内存数组会收紧。
2.4 基本成员方法
2.4.1 构造方法
public ArrayMap() {
this(0, false);
}
// 指定初始容量大小
public ArrayMap(int capacity) {
this(capacity, false);
}
/** {@hide} */ 这是一个隐藏方法
public ArrayMap(int capacity, boolean identityHashCode) {
mIdentityHashCode = identityHashCode;
if (capacity < 0) {
mHashes = EMPTY_IMMUTABLE_INTS;
mArray = EmptyArray.OBJECT;
} else if (capacity == 0) {
mHashes = EmptyArray.INT;
mArray = EmptyArray.OBJECT;
} else {
allocArrays(capacity); // 分配内存【小节2.2.2】
}
mSize = 0; //初始值为0
}
public ArrayMap(ArrayMap<K, V> map) {
this();
if (map != null) {
putAll(map);
}
}
public void putAll(Map<? extends K, ? extends V> map) {
// 确保 map 的大小至少为 mSize + map.size()，如果默认已满足条件则不用扩容
ensureCapacity(mSize + map.size());
for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
put(entry.getKey(), entry.getValue());
}
}
针对构造方法，如果指定大小则会去分配相应大小的内存，如果没有指定默认为 0，当需要添加数据的时候再扩容。
2.4.2 put()
public V put(K key, V value) {
final int osize = mSize; // osize 记录当前 map 大小
final int hash;
int index;
if (key == null) {
hash = 0;
index = indexOfNull();
} else {
// 默认 mIdentityHashCode=false
hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
// 采用二分查找法，从 mHashes 数组中查找值等于 hash 的 key
index = indexOf(key, hash);
}
// 当 index 大于零，则代表的是从数据 mHashes 中找到相同的 key，执行的操作等价于修改相应位置的 value
if (index >= 0) {
index = (index<<1) + 1; // index 的 2 倍 +1 所对应的元素存在相应 value 的位置
final V old = (V)mArray[index];
mArray[index] = value;
return old;
}
// 当 index<0，则代表是插入新元素
index = ~index;
if (osize >= mHashes.length) { // 当 mSize 大于或等于 mHashes 数组长度时，需要扩容【小节2.3.1】
final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))
: (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
allocArrays(n); // 分配更大的内存【小节2.2.2】
// 由于 ArrayMap 并非线程安全的类，不允许并行，如果扩容过程其他线程调整 mSize 则抛出异常
if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
throw new ConcurrentModificationException();
}
if (mHashes.length > 0) {
// 将原来老的数组拷贝到新分配的数组
System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
System.arraycopy(oarray, 0, mArray, 0, oarray.length);
}
freeArrays(ohashes, oarray, osize); // 释放原来老的内存【小节2.2.2】
}
// 当需要插入的位置不在数组末尾时，需要将 index 位置后的数据通过拷贝往后移动一位
if (index < osize) {
System.arraycopy(mHashes, index, mHashes, index + 1, osize - index);
System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
}
if (CONCURRENT_MODIFICATION_EXCEPTIONS) {
if (osize != mSize || index >= mHashes.length) {
throw new ConcurrentModificationException();
}
}
// 将 hash、key、value 添加相应数组的位置，数据个数 mSize 加 1
mHashes[index] = hash;
mArray[index<<1] = key;
mArray[(index<<1)+1] = value;
mSize++;
return null;
}
put() 设计巧妙地将 修改已有数据对(key-value) 和 插入新的数据对 合二为一个方法，主要是依赖 indexOf() 过程中采用的 二分查找法，
当找到相应 key 时则返回正值，当找不到 key 则返回负值，
按位取反所对应的值代表的是需要插入的位置 index。
put() 在插入时，如果当前数组内容已填充满时，则会先进行扩容，再通过 System.arraycopy 来进行数据拷贝，最后在相应位置写入数据。
2.4.4 append()
public void append(K key, V value) {
int index = mSize;
final int hash = key == null ? 0
: (mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());
//使用append前必须保证mHashes的容量足够大，否则抛出异常
if (index >= mHashes.length) {
throw new IllegalStateException("Array is full");
}
//当数据需要插入到数组的中间，则调用put来完成
if (index > 0 && mHashes[index-1] > hash) {
put(key, value); // 【小节2.4.1】
return;
}
//否则，数据直接添加到队尾
mSize = index+1;
mHashes[index] = hash;
index <<= 1;
mArray[index] = key;
mArray[index+1] = value;
}
append() 与 put() 类似，append 的差异在于，该方法不会去做扩容的操作，是一个轻量级的插入方法。
Q：那么什么场景适合使用 append() 方法呢？
A：应就是对于明确知道肯定会插入队尾的情况下使用 append() 性能更好，因为 put() 上来先做 binarySearchHashes() 二分查找，时间复杂度为 O(logN)，而 append() 的时间复杂度为 O(1)。
2.4.5 remove()
public V remove(Object key) {
final int index = indexOfKey(key); // 通过二分查找 key 的 index
if (index >= 0) {
return removeAt(index); // 移除相应位置的数据
}
return null;
}
public V removeAt(int index) {
final Object old = mArray[(index << 1) + 1];
final int osize = mSize;
final int nsize;
if (osize <= 1) { // 当被移除的是 ArrayMap 的最后一个元素，则释放该内存
freeArrays(mHashes, mArray, osize);
mHashes = EmptyArray.INT;
mArray = EmptyArray.OBJECT;
nsize = 0;
} else {
nsize = osize - 1;
// 根据情况来收紧容量 【小节2.3.2】
if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
final int n = osize > (BASE_SIZE*2) ? (osize + (osize>>1)) : (BASE_SIZE*2);
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
allocArrays(n); // 分配一个更小内存的容量
// 禁止并发
if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
throw new ConcurrentModificationException();
}
if (index > 0) {
System.arraycopy(ohashes, 0, mHashes, 0, index);
System.arraycopy(oarray, 0, mArray, 0, index << 1);
}
if (index < nsize) {
System.arraycopy(ohashes, index + 1, mHashes, index, nsize - index);
System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1,
(nsize - index) << 1);
}
} else {
if (index < nsize) { // 当被移除的元素不是数组最末尾的元素时，则需要将后面的数组往前移动
System.arraycopy(mHashes, index + 1, mHashes, index, nsize - index);
System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1,
(nsize - index) << 1);
}
// 再将最后一个位置设置为 null
mArray[nsize << 1] = null;
mArray[(nsize << 1) + 1] = null;
}
}
if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
throw new ConcurrentModificationException();
}
mSize = nsize; // 大小减1
return (V)old;
}
remove() 过程：通过二分查找 key 的 index，再根据 index 来选择移除动作；
- 当被移除的是 ArrayMap 的最后一个元素，则释放该内存，
- 否则只做移除操作，这时会根据容量收紧原则来决定是否要收紧，当需要收紧时会创建一个更小内存的容量。
2.4.5 clear()
public void clear() {
if (mSize > 0) { // 当容量中元素不为空的情况 才会执行内存回收操作
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
final int osize = mSize;
mHashes = EmptyArray.INT;
mArray = EmptyArray.OBJECT;
mSize = 0;
freeArrays(ohashes, oarray, osize); //【小节2.2.1】
}
if (CONCURRENT_MODIFICATION_EXCEPTIONS && mSize > 0) {
throw new ConcurrentModificationException();
}
}
clear() 清理操作会执行 freeArrays() 方法来回收内存，而类似的方法 erase() 则只会清空数组内的数据，并不会回收内存。
三、缺陷分析
3.1 缺陷原因
由于 ArrayMap 是非线程安全的，除了静态变量 mBaseCache 和 mTwiceBaseCache 加类锁保护，其他成员变量并没有保护。可能修改 array[0] 的地方 put、append、removeAt、erase 等方法，此处省去分析过程，最终有两种情况：
- 场景一：这条缓存数据 array 在放入缓存池 (freeArrays) 后，被修改
- 场景二：刚从缓存池取出来 (allocArrays) 的同时，数据立刻被其他地方修改
从 [小节2.2.1] freeArrays() 可知，
- 每一次放入缓存池 mBaseCache 时，一定会把 array[0] 指向 Object[] 类型的缓冲头。
- 并且 mBaseCache 的所有操作，都通过 synchronized 加锁 ArrayMap.class 保护，不可能会有修改其他线程并发修改 mBaseCache。
- 虽然 mBaseCache 会加锁保护，但 mArray 并没有加锁保护。如果有机会把 mBaseCache 的引用传递出去，在其他地方修改的话是有可能出现问题的。
3.2 修复方案
Google 工程师 Suprabh Shukla 在 2018.5.14 提交修复方案，合入 Android 9.0 的代码。方案的思路是利用局部变量保存 mArray，再斩断对外的引用。修复代码如下：
public V removeAt(int index) {
final int osize = mSize;
if (osize <= 1) {
final int[] ohashes = mHashes;
final Object[] oarray = mArray; // 利用局部变量 oarray 先保存 mArray
mHashes = EmptyArray.INT;
mArray = EmptyArray.OBJECT; // 再将 mArray 引用置空
freeArrays(ohashes, oarray, osize);
nsize = 0;
} else {
**除了 removeAt()，其他调用 freeArrays() 的地方都会在调用之前先修改 mArray 内容引用，从而不会干扰缓存回收的操作。
四、类比分析
4.1 HashMap
4.1.1 HashMap 概论
详细的知识内容可以参考之前的文章进行学习hashMap原理解析,这里进行以下简要的概括：
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
{
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4； // 默认初始大小为 16
static final float DEFAULT_LOAD_FACTOR = 0.75； // 默认负载因子
static final int TREEIFY_THRESHOLD = 8; // 当链表个数超过 8，则转红黑树
// 用于存放数据的核心数组，老版本是 HashMapEntry，
transient Node<K,V>[] table；
transient int size; // 实际存储的键值对的个数
int threshold; // 阈值，等于 capacity*loadFactory
final float loadFactor = DEFAULT_LOAD_FACTOR; // 当前负载因子
transient int modCount; // 用于检测是否存在并发修改，transient 修饰则不会进入序列化
}
在不考虑哈希冲突的情况下，在哈希表中的增减、查找操作的时间复杂度为的 O(1)。
HashMap 是如何做到这么优秀的 O(1) 呢？
核心在于哈希函数能将 key 直接转换成哈希表中的存储位置，而哈希表本质是一个数组，在指定下标的情况下查找数组成员是一步到位的。
那么哈希函数设计的好坏，会影响哈希冲突的概率，进而影响哈希表查找的性能。为了解决哈希冲突，也就是两个不同 key，经过 hash 转换后指向同一个 bucket，这时该 bucket 把相同 hash 值的 key 组成一个链表，每次插入链表的表头。(头插法)
可见 HashMap 是由数组+链表组成的，链表是为了处理哈希碰撞而存在的，所以链表出现得越少，其性能越好。
想想一种极端情况，所有 key 都发生碰撞，那么 HashMap 就退化成链表，其时间复杂度一下就退化到 O(n)，这时比 ArrayMap 的性能还差，从 Android sdk26 开始，当链表长度超过 8 则转换为红黑树，让最坏情况的时间复杂度为 O(logn)。网上有大量介绍 HashMap 的资料，其中 table 是HashMapEntry<K,V>[]，那说明是老版本，新版为支持 RBTree 的功能，已切换到 Node 类。
用图表示为：
4.1.1 HashMap 扩容机制
- 扩容触发条件是当发生哈希冲突，并且当前实际键值对个数是否大于或等于阈值 threshold，默认为 0.75*capacity
- 扩容操作是针对哈希表 table 来分配内存空间，每次扩容是至少是当前大小的 2 倍，扩容的大小一定是 2^n。
- 另外，扩容后还需要将原来的数据都 transfer 到新的 table，同时计算新的ihash值，映射新的index下标，这是耗时操作。
4.2 SparseArray
public class SparseArray<E> implements Cloneable {
private static final Object DELETED = new Object();
private boolean mGarbage = false; // 标记是否存在待回收的键值对
private int[] mKeys;
private Object[] mValues;
private int mSize;
}
SparseArray 对应的 key 只能是 int 类型，它不会对 key 进行装箱操作。它使用了两个数组，一个保存 key，一个保存 value。 从内存使用上来说，SparseArray 不需要保存 key 所对应的哈希值，所以比 ArrayMap 还能再节省 1/3 的内存。
SparseArray 使用二分查找来找到 key 对应的插入位置，保证 mKeys 数组从小到大的排序。
4.2.1 SparseArray 的延迟回收机制
public void delete(int key) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
if (mValues[i] != DELETED) {
mValues[i] = DELETED; // 标记该数据为 DELETE
mGarbage = true; // 设置存在 GC
}
}
}
当执行 delete() 或者 removeAt() 删除数据的操作，只是将相应位置的数据标记为 DELETE，并设置 mGarbage=true，而不会直接执行数据拷贝移动的操作。
当执行 clear() 会清空所有的数据，并设置 mGarbage=false；另外有很多时机(比如实际数据大于等于数组容量)都有可能会主动调用 gc() 方法来清理 DELETE 数据，代码如下：
private void gc() {
int n = mSize;
int o = 0;
int[] keys = mKeys;
Object[] values = mValues;
for (int i = 0; i < n; i++) {
Object val = values[i];
if (val != DELETED) { // 将所有没有标记为 DELETE 的 value 移动到队列的头部
if (i != o) {
keys[o] = keys[i];
values[o] = val;
values[i] = null;
}
o++;
}
}
mGarbage = false; // 垃圾整理完成
mSize = o;
}
延迟回收机制的好处在于：首先删除方法效率更高，同时减少数组数据来回拷贝的次数，比如删除某个数据后被标记删除，接着又需要在相同位置插入数据，则不需要任何数组元素的来回移动操作。可见，对于 SparseArray 适合频繁删除和插入来回执行的场景，性能很好。
4.3 ArraySet
ArraySet 也是 Android 特有的数据结构，用于替代 HashSet 的，跟 ArrayMap 出自同一个作者，从源码来看 ArraySet 跟 ArrayMap 几乎完全一致，包含缓存机制，扩容机制。唯一的不同在于 ArrayMap 是一个 key-value 键值对的集合，而 ArraySet 是一个集合，mArray[] 保存所有的 value 值，而 mHashes[] 保存相应 value 所对应的hash 值。
当然 ArraySet 也有 ArrayMap 一样原理的缺陷，这一点 Google 修复如下：
private void allocArrays(final int size) {
if (size == (BASE_SIZE * 2)) {
...
} else if (size == BASE_SIZE) {
synchronized (ArraySet.class) {
if (sBaseCache != null) {
final Object[] array = sBaseCache;
try {
mArray = array;
sBaseCache = (Object[]) array[0];
mHashes = (int[]) array[1];
array[0] = array[1] = null;
sBaseCacheSize--;
return;
} catch (ClassCastException e) {
}
// 从下面这段日志，可以看出谷歌工程师也发现了存在这个问题
// Whoops! Someone trampled the array (probably due to not protecting
// their access with a lock). Our cache is corrupt; report and give up.
sBaseCache = null;
sBaseCacheSize = 0;
}
}
}
mHashes = new int[size];
mArray = new Object[size];
}
对于 ClassCastException 异常，这个有可能不是当前 ArraySet 使用不到导致的，也无法追溯，所以谷歌直接 catch 住这个异常，然后把缓冲池清空，再创建数组。这样可以解决问题，但这样有什么不足吗？ 这样的不足在于当发生异常时会让缓存机制失效。
五、总结分析
从以下几个角度进行总结分析：
数据结构
- ArrayMap 和 SparseArray 采用的都是两个数组，Android 专门针对内存优化而设计的
- HashMap 采用的是数据+链表+红黑树
内存优化
- ArrayMap 比 HashMap 更节省内存，综合性能方面在数据量不大的情况下，推荐使用 ArrayMap
- Hash 需要创建一个额外对象来保存每一个放入 map 的 entry（数组），且容量的利用率比 ArrayMap 低，整体更消耗内存
- SparseArray 比 ArrayMap 节省 1/3 的内存，但 SparseArray 只能用于 key 为 int 类型的 Map，所以 int 类型的 Map 数据推荐使用 SparseArray
性能方面
- ArrayMap 查找时间复杂度 O(logN)；ArrayMap 增加、删除操作需要移动成员，速度相比较慢，对于个数小于 1000 的情况下，性能基本没有明显差异
- HashMap 查找、修改的时间复杂度为 O(1)；
- SparseArray 适合频繁删除和插入来回执行的场景，性能比较好
缓存机制
- ArrayMap 针对容量为 4 和 8 的对象进行缓存，可避免频繁创建对象而分配内存与 GC 操作，这两个缓存池大小的上限为 10 个，防止缓存池无限增大
- HashMap 没有缓存机制
- SparseArray 有延迟回收机制，提供删除效率，同时减少数组成员来回拷贝的次数
扩容机制
- ArrayMap 是在容量满的时机触发容量扩大至原来的 1.5 倍，在容量不足 1/3 时触发内存收缩至原来的 0.5 倍，更节省的内存扩容机制
- HashMap 是在容量的 0.75 倍时触发容量扩大至原来的 2 倍，且没有内存收缩机制。HashMap 扩容过程有 - hash 重建，相对耗时。所以能大致知道数据量，可指定创建指定容量的对象，能减少性能浪费
并发问题
- ArrayMap 是非线程安全的类，大量方法中通过对 mSize 判断是否发生并发，来决定抛出异常。但没有覆盖到所有并发场景，比如大小没有改变而成员内容改变的情况就没有覆盖
- HashMap 是在每次增加、删除、清空操作的过程将 modCount 加 1，在关键方法内进入时记录当前 mCount，执行完核心逻辑后，再检测 mCount 是否被其他线程修改，来决定抛出异常。这一点的处理比 ArrayMap 更有全面
回到一开始的那几个问题，我们来简单回答一下：
- ArrayMapa和HashMap的区别？
- ArrayMap的存在是为了解决HashMap占用内存大的问题，它内部使用了一个int数组用来存储元素的hashcode，使用了一个Object数组用来存储元素，两者根据索引对应形成key-value结构，这样就不用像HashMap那样需要额外的创建Entry对象来存储，减少了内存占用。
- 但是在数据量比较大时，ArrayMap的性能就会远低于HashMap,因为ArrayMap基于二分查找算法来查找元素的，并目数组的插入操作如果不是末尾的话需要挪动数组元素，效率较低。
- 而HashMap内部基于数组+单向链表+红黑树实现，也是key-value结构，正如刚才提到的，HashMap每put一个元素都需要创建一个Enty来存放元素，导致它的内存占用会比较大，但是在大数据量的时候，因为HashMap中当出现冲突时，冲突的数据量大于8，就会从单向链表转换成红黑树，而红黑树的插入、删除、查找的时间复杂度为O(logn),相对于ArrayMapl的数组而言在插入和删除操作上要快不少，所以数据量上百的情况下，使用HashMap:会有更高的效率。
在ArrayMap中，假设存在冲突的话，并不会像HashMap那样使用单向链表或红黑树来保留这些冲突的元素，而是全部key、value都存储到一个数组当中，然后查找的话通过二分查找进行，这也就是当数据量大时不宜用ArrayMap的原因了。
