Java&Android集合框架须知须会（3）

一、SparseArray

使用 Android Studio 的同学可能遇到过一个现象，就是如果在代码中声明了类型变量的话，Android Studio 会提示：，即用 SparseArray< Object > 性能更优，可以用来替代 HashMapMap<Integer,Object>Use new SparseArray<Object>(...) instead for better performance ...

这里就来介绍下 SparseArray 的内部原理，看看它相比 HashMap 有什么性能优势

1、基本概念

SparseArray 的使用方式：

        SparseArray<String> sparseArray = new SparseArray<>();
sparseArray.put(100, "https://juejin.cn/user/923245496518439");
sparseArray.remove(100);
sparseArray.get(100);
sparseArray.removeAt(29);

SparseArray< E > 相当于 Map< Integer ， E > ，key 值固定为 int 类型，在初始化时只需要声明 value 的数据类型即可，其内部用两个数组分别来存储 key 和 value：int[] mKeys ; Object[] mValues

mKeys 和 mValues 按照如下规则对应起来：

假设要向 SparseArray 存入 key 为 10，value 为 200 的键值对，则先将 10 存到 mKeys 中，假设 10 在 mKeys 中对应的索引值是 2，则将 value 存入 mValues[2] 中
mKeys 中的元素值按照递增的方法进行存储，每次存放新的键值对时都通过二分查找的方式将 key 插入到 mKeys 中
当要从 SparseArray 取值时，则先判断 key 在 mKeys 中对应的索引，然后根据该索引从 mValues 中取值

从以上可以看出来的一点就是：SparseArray 避免了 HashMap 每次存取值时的装箱拆箱操作，key 值保持为基本数据类型 int，减少了性能开销

2、类声明

SparseArray 本身并没有直接继承于任何类，内部也没有使用到 Java 原生的集合框架，所以 SparseArray 是 Android 系统自己实现的一个集合框架

	public class SparseArray<E> implements Cloneable

3、全局变量

mGarbage 是 SparseArray 的一个优化点之一，用于标记当前是否有需要垃圾回收（GC）的元素，当该值被置为 true 时，意味着当前状态需要进行垃圾回收，但回收操作并不会马上进行，而是在后续操作中再统一进行

    //鍵值對被移除後對應的 value 會變成此值，用來當做 GC 標記位
private static final Object DELETED = new Object();
//用於標記當前是否有待垃圾回收(GC)的元素
private boolean mGarbage = false;
private int[] mKeys;
private Object[] mValues;
//當前集合元素的數量
//該值並不一定是時時處於正確狀態，因為有可能出現只刪除 key 和 value 兩者之一的情況
//所以 size() 方法內都會先進行 GC
private int mSize;

4、构造函数

key 数组和 value 数组的默认大小都是 10，如果在初始化时已知最终数据量的大小，则可以直接指定初始容量，这样可以避免后续的扩容操作

    //設置數組的默認初始容量為10
public SparseArray() {
this(10);
}
public SparseArray(int initialCapacity) {
if (initialCapacity == 0) {
mKeys = EmptyArray.INT;
mValues = EmptyArray.OBJECT;
} else {
mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
mKeys = new int[mValues.length];
}
mSize = 0;
}

5、添加元素

添加元素的方法有几个，主要看方法就可以，该方法用于存入 key 和 value 组成的键值对。按照前面所说的 SparseArray 存储键值对的规则，put 方法会先判断当前 mKeys 中是否已经有相同的 key 值，有的话就用 value 覆盖 mValues 中的旧值。如果不存在相同key值，在将key插入到mKeys后需要在mValues的相同索引位置插入value，由于mKeys是会按照大小对元素值进行排序存储的，所以将key插入到mKeys可能会导致元素重新排序，从而连锁导致mValues也需要重新排序put(int key, E value)

put 方法从 mKeys 查找 key 用的是 ContainerHelpers 类提供的二分查找方法：，用于获取 key 在 mKeys 中的当前索引（存在该 key 的话）或者是应该存放的位置的索引（不存在该 key），方法的返回值可以分为三种情况：binarySearch

如果 mKeys 中存在对应的 key，则直接返回对应的索引值
如果 mKeys 中不存在对应的 key
1. 假设 mKeys 中存在“值比 key 大且大小与 key 最接近的值的索引”为 presentIndex，则此方法的返回值为 ~presentIndex
2. 如果 mKeys 中不存在比 key 还要大的值的话，则返回值为 ~mKeys.length

    // This is Arrays.binarySearch(), but doesn't do any argument validation.
static int binarySearch(int[] array, int size, int value) {
int lo = 0;
int hi = size - 1;
while (lo <= hi) {
final int mid = (lo + hi) >>> 1;
final int midVal = array[mid];
if (midVal < value) {
lo = mid + 1;
} else if (midVal > value) {
hi = mid - 1;
} else {
return mid;  // value found
}
}
return ~lo;  // value not present
}

可以看到，如果 mKeys 存在目标 key，那么返回值即对应的索引位置。如果不存在目标 key，其返回值也指向了应该让 key 存入的位置，因为当不存在目标 key 时，将计算出的索引值进行 ~ 运算后返回值一定是负数，从而与“找得到目标 key 的情况（返回值大于等于0）”的情况区分开。从这里可以看出该方法的巧妙之处，单纯的一个返回值就可以区分出多种情况，且通过这种方式来存放数据可以使得 mKeys 的内部值一直是按照值递增的方式来排序的

再来具体看看 put 方法的逻辑

	public void put(int key, E value) {
//用二分查找法查找指定 key 在 mKeys 中的索引值
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) { //對應已經存在相同 key 的情況
mValues[i] = value;
} else {
//取反，拿到真實的索引位置
i = ~i;
//如果目標位置還未賦值，則直接存入數據即可
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
//如果存在冗餘數據，那麼就先進行 GC
if (mGarbage && mSize >= mKeys.length) {
gc();
//GC 後再次進行查找，因為值可能已經發生變化了
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
//索引 i 位置已經用於存儲其它數據了，此時就需要對數組元素進行遷移
//所以從索引 i 開始的所有數據都需要向後移動一位，並將 key 存到 mKeys[i]
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}
//將索引 index 處的元素賦值為 value
//知道目標位置的話可以直接向 mValues 賦值
public void setValueAt(int index, E value) {
if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) {
// The array might be slightly bigger than mSize, in which case, indexing won't fail.
// Check if exception should be thrown outside of the critical path.
throw new ArrayIndexOutOfBoundsException(index);
}
//如果需要則先進行垃圾回收
if (mGarbage) {
gc();
}
mValues[index] = value;
}
//和 put 方法類似
//但在存入數據前先對數據大小進行了判斷，有利於減少對 mKeys 進行二分查找的次數
//所以在“存入的 key 比現有的 mKeys 值都大”的情況下會比 put 方法性能高
public void append(int key, E value) {
if (mSize != 0 && key <= mKeys[mSize - 1]) {
put(key, value);
return;
}
if (mGarbage && mSize >= mKeys.length) {
gc();
}
mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
mValues = GrowingArrayUtils.append(mValues, mSize, value);
mSize++;
}

6、移除元素

上文说了，布尔变量用于标记当前是否有待垃圾回收（GC）的元素，当该值被置为 true 时，即意味着当前状态需要进行垃圾回收，但回收操作并不马上进行，而是在后续操作中再完成mGarbage

以下几个方法在移除元素时，都只是切断了 mValues 对 value 的引用，而 mKeys 并没有进行回收，这个操作会留到进行处理gc()

	public void delete(int key) {
//用二分查找法查找指定 key 在 mKeys 中的索引值
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
if (mValues[i] != DELETED) {
mValues[i] = DELETED;
//標記當前需要進行垃圾回收
mGarbage = true;
}
}
}
public void remove(int key) {
delete(key);
}
//和 delete 方法基本相同，差別在於會返回 key 對應的元素值
public E removeReturnOld(int key) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
if (mValues[i] != DELETED) {
final E old = (E) mValues[i];
mValues[i] = DELETED;
mGarbage = true;
return old;
}
}
return null;
}
//刪除指定索引對應的元素值
public void removeAt(int index) {
if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) {
// The array might be slightly bigger than mSize, in which case, indexing won't fail.
// Check if exception should be thrown outside of the critical path.
throw new ArrayIndexOutOfBoundsException(index);
}
if (mValues[index] != DELETED) {
mValues[index] = DELETED;
//標記當前需要進行垃圾回收
mGarbage = true;
}
}
//刪除從起始索引值 index 開始之後的 size 個元素值
public void removeAtRange(int index, int size) {
//避免發生數組越界的情況
final int end = Math.min(mSize, index + size);
for (int i = index; i < end; i++) {
removeAt(i);
}
}
//移除所有元素值
public void clear() {
int n = mSize;
Object[] values = mValues;
for (int i = 0; i < n; i++) {
values[i] = null;
}
mSize = 0;
mGarbage = false;
}

7、查找元素

查找元素的方法较多，逻辑都挺简单的

    //根據 key 查找相應的元素值，查找不到則返回默認值
@SuppressWarnings("unchecked")
public E get(int key, E valueIfKeyNotFound) {
//用二分查找法查找指定 key 在 mKeys 中的索引值
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
//如果找不到該 key 或者該 key 尚未賦值，則返回默認值
if (i < 0 || mValues[i] == DELETED) {
return valueIfKeyNotFound;
} else {
return (E) mValues[i];
}
}
//根據 key 查找相應的元素值，查找不到則返回 null
public E get(int key) {
return get(key, null);
}
//因為 mValues 中的元素值並非一定是連貫的，有可能摻雜著 DELETED 
//所以在遍歷前需要先進行 GC，這樣通過數組取出的值才是正確的
@SuppressWarnings("unchecked")
public E valueAt(int index) {
if (mGarbage) {
gc();
}
return (E) mValues[index];
}
//根據索引值 index 查找對應的 key 
public int keyAt(int index) {
if (mGarbage) {
gc();
}
return mKeys[index];
}
//根據 key 對應的索引值
public int indexOfKey(int key) {
if (mGarbage) {
gc();
}
return ContainerHelpers.binarySearch(mKeys, mSize, key);
}
//根據 value 查找對應的索引值
public int indexOfValue(E value) {
if (mGarbage) {
gc();
}
for (int i = 0; i < mSize; i++) {
if (mValues[i] == value) {
return i;
}
}
return -1;
}
//與 indexOfValue 方法類似，但 indexOfValue 方法是通過比較 == 來判斷是否同個對象
//而此方法是通過 equals 方法來判斷是否同個對象
public int indexOfValueByValue(E value) {
if (mGarbage) {
gc();
}
for (int i = 0; i < mSize; i++) {
if (value == null) {
if (mValues[i] == null) {
return i;
}
} else {
if (value.equals(mValues[i])) {
return i;
}
}
}
return -1;
}

8、垃圾回收

因为 SparseArray 中会出现只移除 key 和 value 两者之一的情况，导致当前数组中的有效数据并不是全都紧挨着排列在一起的，即存在无效值，因此方法会根据 mValues 中到底存在多少有效数据，将 mKeys 和 mValues 中的数据进行重新排列，将有意义的元素值紧挨着排序在一起gc()

		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];
//val 非 DELETED ，說明該位置可能需要移動數據
if (val != DELETED) {
//將索引 i 處的值賦值到索引 o 處
//所以如果 i == o ，則不需要執行代碼了
if (i != o) {
keys[o] = keys[i];
values[o] = val;
values[i] = null;
}
o++;
}
}
mGarbage = false;
mSize = o;
}

9、优劣势总结

从上文的介绍来看，SparseArray 的主要优势有以下几点：

避免了基本数据类型 int 的装箱拆箱操作
和 HashMap 中每个存储结点都是一个类对象不同，SparseArray 不需要用于包装 key 的结构体，单个元素的存储成本更加低廉
在数据量不大的情况下，查找效率较高（二分查找法）
延迟了垃圾回收的时机，只在需要的时候才一次性进行

劣势有以下几点：

具有特定的适用范围，key 只能是 int 类型
插入键值对时可能需要移动大量的数组元素
数据量较大时，查找效率（二分查找法）会明显降低，需要经过多次折半查找才能定位到目标数据。而 HashMap 在没有哈希冲突的情况下只需要进行一次哈希计算即可定位到目标元素，有哈希冲突时也只需要对比链表或者红黑树上的元素即可

10、关联类

SparseArray 属于泛型类，所以即使 value 是基本数据类型也会被装箱和拆箱，如果想再省去这一部分开销的话，可以使用 SparseBooleanArray、SparseIntArray 和 SparseLongArray 等三个容器，这三个容器的实现原理和 SparseArray 相同，但是 value 还是属于基本数据类型

此外，系统还提供了 LongSparseArray 这个容器类，其实现原理和 SparseArray 类似，但是 key 固定为 long 类型，value 通过泛型来声明，对于日常开发中比较有用的一点是可以用来根据 viewId 存储 view

二、ArrayMap

ArrayMap 属于泛型类，继承了 Map 接口，其使用情况和 HashMap 基本一样，但在内部逻辑上有着很大差异，所以需要了解其实现原理后才能明白 ArrayMap 到底适用于哪些场景

	public final class ArrayMap<K, V> implements Map<K, V> {
}

1、存储机制

ArrayMap 中包含以下两个数组。 mHashes 只用于存储键值对中 key 的哈希值，mArray 则用于存储 key 和 value，即每个存入的键值对会被一起存入 mArray 中

    // Hashes are an implementation detail. Use public key/value API.
int[] mHashes;
// Storage is an implementation detail. Use public key/value API.
Object[] mArray;

当向 ArrayMap 插入键值对时，会先计算出 key 的哈希值，将 keyHash 按照大小顺序存入 mHashes 中，拿到其位置索引 index。然后将key存入mArray的index<<1位置，将value存入mArray的（index<<1+1）位置，即key和value会存储在相邻的位置。从这个位置对应关系来看，mArray 的所需容量至少也需要是mHashes的两倍，且每个key-value的排列关系也是和keyHash的排列保持一致

当要通过key对象向ArrayMap取值时，就先计算出keyHash，然后通过二分查找法找到keyHash在mHashes中的位置索引index，然后在（index<<1+1）位置从mArray拿到value

2、添加元素

有几个用于添加元素的方法，当中重点看 put 方法即可，其它添加元素的方法都需要依靠该方法来实现，该方法参数就用于传入键值对。前文有讲到，key-value 最终是会相邻着存入 mArray 中的，而 key-value 在 mArray 中的位置是由 keyHash 和 mHashes 来共同决定的，所以 put 方法的整体逻辑如下所诉：

根據二分查找法獲取到 keyHash 在 mHashes 中的索引位置 index，
如果 index 大于等于 0，说明在 mArray 中 key 已存在，那么直接覆盖旧值即可，结束流程
如果 index 小于 0，说明在 mArray 中 key 不存在，~index 此时代表的是 keyHash 按照递增顺序应该插入 mHashes 的位置
判断是否需要扩容，需要的话则进行扩容。如果符合缓存标准的话，则会缓存扩容前的数组
对最终的数组进行数据迁移，插入 key-value 和 keyHash

	@Override
public V put(K key, V value) {
final int osize = mSize;
final int hash;
int index;
//第一步
if (key == null) {
hash = 0; 
index = indexOfNull();
} else {
hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
index = indexOf(key, hash);
}
//第二步
if (index >= 0) {
index = (index<<1) + 1;
final V old = (V)mArray[index];
mArray[index] = value;
return old;
}
//第三步
index = ~index;
//第四步
if (osize >= mHashes.length) {
//ArrayMap 的擴容機制相比 HashMap 會比較剋制
//當數組長度已超出 BASE_SIZE*2 後，數組容量按照 1.5 倍來擴容
final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))
: (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n);
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
allocArrays(n);
if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
throw new ConcurrentModificationException();
}
if (mHashes.length > 0) {
if (DEBUG) Log.d(TAG, "put: copy 0-" + osize + " to 0");
System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
System.arraycopy(oarray, 0, mArray, 0, oarray.length);
}
freeArrays(ohashes, oarray, osize);
}
//第五步
if (index < osize) {
if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (osize-index)
+ " to " + (index+1));
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();
}
}
mHashes[index] = hash;
mArray[index<<1] = key;
mArray[(index<<1)+1] = value;
mSize++;
return null;
}

append 方法也是用于添加元素的，带有一点“追加”的意思，即本意是外部可以确定本次插入的 key 的 hash 值比当前所有已有值都大，那么就可以直接向 mHashes 的尾部插入数据，从而节省了二分查找的过程。所以 append 方法会先和 mHashes 的最后一个元素值进行对比，如果 keyHash 比该值大的话就说明可以直接保存到尾部，校验不通过的话还是会调用 put 方法

    public void append(K key, V value) {
int index = mSize;
final int hash = key == null ? 0
: (mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());
if (index >= mHashes.length) {
throw new IllegalStateException("Array is full");
}
//如果 mHashes 當前的最後一個值比 hash 大，hash 沒法直接插到尾部，那麼就還是需要調用 put 方法
if (index > 0 && mHashes[index-1] > hash) {
RuntimeException e = new RuntimeException("here");
e.fillInStackTrace();
Log.w(TAG, "New hash " + hash
+ " is before end of array hash " + mHashes[index-1]
+ " at index " + index + " key " + key, e);
put(key, value);
return;
}
//將 key-value 直接插入到數組尾部
mSize = index+1;
mHashes[index] = hash;
index <<= 1;
mArray[index] = key;
mArray[index+1] = value;
}

3、获取元素

获取元素的方法主要看方法即可，只要理解了该方法是如何获取 keyIndex 的，那么就能够对 ArrayMap 的存储结构有更明确的认知indexOf(Object key, int hash)

indexOf 方法用于获取和 key，hash 均能对应上的元素的哈希值在 mHashes 中的索引位置。我们知道，keyHash是存储在 mHashes 中的，而 key-value 又是存储在 mArray 中的，但我们无法只根据 keyHash 就准确对应上 key-value，因为不同的 key 有可能有相同的 hash 值，即需要考虑哈希冲突的情况，所以 indexOf 方法除了需要对比 hash 值大小是否相等外还需要对比 key 的相等性。所以 indexOf 方法的具体逻辑如下所诉：

通过二分查找法获取到 mHashes 中和 hash 相等的值的索引 index
如果 index 小于 0，说明不存在该 key，那么就返回 index，~index 就是 hash 插入 mHashes 后的位置索引。结束流程
index 大于等于 0，说明 key 有可能存在，之所以说可能，因为存在 key 不同但 hash 值相等的情况
判断 mArray 中 index<<1 位置的元素是否和 key 相等，如果相等说明已经找到了目标位置，返回 index。结束流程
此时可以确定发生了哈希冲突，那么就还是需要对mArray进行相等性对比了，而之所以要分为两个 for 循环也是为了减少遍历次数，因为相同 hash 值是会靠拢在一起的，所以分别向两侧进行遍历查找。如果key和keyHash的相等性均校验通过，那么就返回对应的索引。结束流程
会执行到这里，说明还是没有找到和key相等的元素值，那么就拿到hash应该存入mHashes后的索引，~ 运算后返回

	int indexOf(Object key, int hash) {
final int N = mSize;
// Important fast case: if nothing is in here, nothing to look for.
if (N == 0) {
return ~0;
}
//第一步
int index = binarySearchHashes(mHashes, N, hash);
// If the hash code wasn't found, then we have no entry for this key.
//第二步
if (index < 0) {
return index;
}
// If the key at the returned index matches, that's what we want.
//第四步
if (key.equals(mArray[index<<1])) {
return index;
}
//第五步
// Search for a matching key after the index.
int end;
for (end = index + 1; end < N && mHashes[end] == hash; end++) {
if (key.equals(mArray[end << 1])) return end;
}
// Search for a matching key before the index.
for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
if (key.equals(mArray[i << 1])) return i;
}
// Key not found -- return negative value indicating where a
// new entry for this key should go.  We use the end of the
// hash chain to reduce the number of array entries that will
// need to be copied when inserting.
//第六步
return ~end;
}

4、缓存机制

ArrayMap 内部包含了对 mHashes 和 mArray 这两个数组进行缓存的机制，避免由于频繁创建数组而造成内存抖动，这一点还是比较有意义的。在 Android 系统中 Bundle 是使用得很频繁的一个类，其内部就通过 ArrayMap 来存储键值对，这可以从 Bundle 的父类 BaseBundle 看到。所以 ArrayMap 的数组缓存机制在我看来更多的是面对系统运行时的优化措施

public class BaseBundle {
@UnsupportedAppUsage
ArrayMap<String, Object> mMap = null;
public void putBoolean(@Nullable String key, boolean value) {
unparcel();
mMap.put(key, value);
}
void putByte(@Nullable String key, byte value) {
unparcel();
mMap.put(key, value);
}
void putChar(@Nullable String key, char value) {
unparcel();
mMap.put(key, value);
}
···
}

put 方法内部就使用到了数组的缓存和复用机制

	@Override
public V put(K key, V value) {
···
if (osize >= mHashes.length) {
final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))
: (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n);
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
//嘗試通過數組複用機制來初始化 mHashes 和 mArray
allocArrays(n);
if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
throw new ConcurrentModificationException();
}
if (mHashes.length > 0) {
if (DEBUG) Log.d(TAG, "put: copy 0-" + osize + " to 0");
System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
System.arraycopy(oarray, 0, mArray, 0, oarray.length);
}
//嘗試回收 ohashes 和 oarray
freeArrays(ohashes, oarray, osize);
}
···
return null;
}

1、缓存数组

实现数组缓存逻辑对应的是freeArrays方法，该方法就用于缓存mHashes和mArray。每当 ArrayMap 完成数组扩容后就会调用此方法对扩容前的数组进行缓存，但也不是所有数组都会进行缓存，而是有着数组长度和缓存总数这两方面的限制

首先，ArrayMap 包含了多个全局的静态变量和静态常量用于控制及实现数组缓存。从freeArrays方法可以看出来，if和else语句块的逻辑是基本完全一样的，其区别只在于触发缓存的条件和使用的缓存池不一样

例如，如果 hashes 的数组长度是 BASE_SIZE * 2，且当前缓存总数没有超出 CACHE_SIZE，那么缓存的数组就是保存在 mTwiceBaseCache 所构造的的单向链表中。 mTwiceBaseCache 采用单向链表的结构来串联多个数组，要缓存的 mArray 的第一个数组元素值会先指向 mTwiceBaseCache，第二个数组元素值会指向 mHashes，之后 mArray 会成为单向链表的新的头结点，即 mArray 成为了新的 mTwiceBaseCache。在这种缓存机制下，最终 mTwiceBaseCache 指向的其实是本次缓存的 mArray，mArray 的第一个元素值指向的又是上一次缓存的 mArray，第二个元素值指向的是本次缓存的 mHashes，从而形成了一个单向链表结构

	//用於緩存長度為 BASE_SIZE 的數組
static Object[] mBaseCache;
//mBaseCache 已緩存的數組個數
static int mBaseCacheSize;
//用於緩存長度為 BASE_SIZE * 2 的數組
static Object[] mTwiceBaseCache;
//mTwiceBaseCache 已緩存的數組個數
static int mTwiceBaseCacheSize;
private static final int BASE_SIZE = 4;
//mBaseCacheSize 和 mTwiceBaseCacheSize 的最大緩存個數
private static final int CACHE_SIZE = 10;
//用來當做同步鎖
private static final Object sBaseCacheLock = new Object();
private static final Object sTwiceBaseCacheLock = new Object();
//緩存 hashes 和 array
private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
if (hashes.length == (BASE_SIZE*2)) {
synchronized (sTwiceBaseCacheLock) {
if (mTwiceBaseCacheSize < CACHE_SIZE) {
//第一個元素指向 mTwiceBaseCache
array[0] = mTwiceBaseCache;
//第二個元素指向 hashes
array[1] = hashes;
for (int i=(size<<1)-1; i>=2; i--) {
//切除多餘引用，避免內存洩漏，有利於 GC
array[i] = null;
}
//array 成為單鏈表的頭結點
mTwiceBaseCache = array;
mTwiceBaseCacheSize++;
if (DEBUG) Log.d(TAG, "Storing 2x cache " + array
+ " now have " + mTwiceBaseCacheSize + " entries");
}
}
} else if (hashes.length == BASE_SIZE) {
synchronized (sBaseCacheLock) {
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++;
if (DEBUG) Log.d(TAG, "Storing 1x cache " + array
+ " now have " + mBaseCacheSize + " entries");
}
}
}
}

2、复用数组

缓存数组的目的自然就是为了后续复用，数组的复用逻辑对应的是allocArrays方法，该方法用于为mHashes和mArray申请一个更大容量的数组空间，通过复用数组或者全新初始化来获得

在进行数组缓存的时候会判断数组长度，只有当长度是BASE_SIZE*2或BASE_SIZE时才会进行缓存，那么自然只有当数组的目标长度size是这两个值之一才会符合复用条件了。 allocArrays 的取缓存逻辑也很简单，只需要取出单向链表的头结点赋值给 mHashes 和 mArray，同时使链表的第二个结点成为新的头结点即可。如果不符合复用条件，那么就还是会进行全新初始化

	//用於緩存長度為 BASE_SIZE 的數組
static Object[] mBaseCache;
//mBaseCache 已緩存的數組個數
static int mBaseCacheSize;
//用於緩存長度為 BASE_SIZE * 2 的數組
static Object[] mTwiceBaseCache;
//mTwiceBaseCache 已緩存的數組個數
static int mTwiceBaseCacheSize;
private static final int BASE_SIZE = 4;
//mBaseCacheSize 和 mTwiceBaseCacheSize 的最大緩存個數
private static final int CACHE_SIZE = 10;
//用來當做同步鎖
private static final Object sBaseCacheLock = new Object();
private static final Object sTwiceBaseCacheLock = new Object();
private void allocArrays(final int size) {
if (mHashes == EMPTY_IMMUTABLE_INTS) {
throw new UnsupportedOperationException("ArrayMap is immutable");
}
if (size == (BASE_SIZE*2)) {
synchronized (sTwiceBaseCacheLock) {
if (mTwiceBaseCache != null) {
final Object[] array = mTwiceBaseCache;
mArray = array;
try {
//指向頭結點的下一個結點，即原先的第二個結點將成為鏈表新的頭結點
mTwiceBaseCache = (Object[]) array[0];
mHashes = (int[]) array[1];
if (mHashes != null) {
//符合複用條件，切除多餘引用
array[0] = array[1] = null;
mTwiceBaseCacheSize--;
if (DEBUG) {
Log.d(TAG, "Retrieving 2x cache " + mHashes
+ " now have " + mTwiceBaseCacheSize + " entries");
}
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.
Slog.wtf(TAG, "Found corrupt ArrayMap cache: [0]=" + array[0]
+ " [1]=" + array[1]);
//會執行到這裡，說明緩存機制發現問題，則棄用之前的所有緩存
mTwiceBaseCache = null;
mTwiceBaseCacheSize = 0;
}
}
} else if (size == BASE_SIZE) {
synchronized (sBaseCacheLock) {
if (mBaseCache != null) {
final Object[] array = mBaseCache;
mArray = array;
try {
mBaseCache = (Object[]) array[0];
mHashes = (int[]) array[1];
if (mHashes != null) {
array[0] = array[1] = null;
mBaseCacheSize--;
if (DEBUG) {
Log.d(TAG, "Retrieving 1x cache " + mHashes
+ " now have " + mBaseCacheSize + " entries");
}
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.
Slog.wtf(TAG, "Found corrupt ArrayMap cache: [0]=" + array[0]
+ " [1]=" + array[1]);
mBaseCache = null;
mBaseCacheSize = 0;
}
}
}
mHashes = new int[size];
mArray = new Object[size<<1];
}

3、总结

上文说了，只有长度为BASE_SIZE或者BASE_SIZE*2 的数组才会被缓存复用，而 mHashes 和 mArray 的扩容操作也会尽量使得扩容后的数组长度就是这两个值之一，这可以从 put 方法计算扩容后容量的算法看出来

	@Override
public V put(K key, V value) {
final int osize = mSize;
final int hash;
···
if (osize >= mHashes.length) {
//計算數組擴容後的大小
final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))
: (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n);
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
allocArrays(n);
···
freeArrays(ohashes, oarray, osize);
}
···
return null;
}

所以说，虽然ArrayMap的构造函数中并没有直接将BASE_SIZE作为数组的默认长度，但是在扩容过程中会尽量往BASE_SIZE和BASE_SIZE * 2 这两个值靠拢，这就有利于尽量实现数组复用

此外，ArrayMap的扩容操作，即申请内存操作也显得比较克制，在数组长度超出BASE_SIZE*2后，只是扩容到当前的1.5倍，且也只在mHashes容量不足时才会触发扩容机制。而HashMap在达到负载因子设定的比例后（此时数组未满）就会触发扩容机制，而且也是按照扩充到两倍容量的方式进行扩容。所以说，ArrayMap 对于内存空间的利用效率会更高一些

5、优劣势总结

ArrayMap 的适用场景可以从它的缓存机制就看出来一些，它会缓存容量为 4 或者 8 的数组并进行后续复用，而这两个值可以说都是比较小的。对于 Android 开发来说，系统对于内存比较敏感，需要存储键值对时面对的往往是使用频率高但数据量小的场景。例如我们在跳转到 Activity 时往往是通过 Bundle 来存储跳转参数，但数据量一般都很少，所以 Bundle 内部就使用到了 ArrayMap 来存储键值对。 ArrayMap 在内存申请时相比 HashMap 会比较克制，键值对会以更加紧密的数据结构存储在一起，对内存利用率会更高一些

而相对的，ArrayMap的这种存储结构也导致了其查找效率相比 HashMap 要低很多。在数据量大时，ArrayMap 可能需要通过多次二分查找才能定位到元素，而 HashMap 在没有哈希冲突的情况下只需要经过一次哈希计算即可定位到元素，即使有哈希冲突也只需要遍历发生冲突的部分元素即可

所以说，ArrayMap适用于数据量较小的场景，此时查找效率也不会受多大影响，而内存利用率能够显著提高。如果数据量较大，那就可以考虑使用HashMap来替代了

6、关联类

系统还包含了一个用于存储不重复元素值的集合框架类：ArraySet，从名字就可以猜到 ArraySet 实现了 Set 接口。 ArraySet 内部一样使用两个数组来存储 hash 和 value，即 mHashes 和 mArray，在实现逻辑上基本和 ArrayMap 一样，只是会在存值的时候判断 value 是否重复而已，这里就不再赘述了