一、介绍
Android 平台，SparesArray 类可以替代 HashMap 作为数据存储，与 HashMap 数组+链表的数据结构不同，采用两个数组的方案。下面是源码中定义的两个数组，分别存储 key 和 value。其中，key 必须为 int 类型。
private int[] mKeys;
private Object[] mValues;
public SparseArray() {
this(10);
}
无参构造方法，默认容量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;
}
根据容量值，初始化两个数组，它们长度是一样。
二、数据存取
public void put(int key, E value) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
//key已存在mKey中，直接更新mValue数组。
if (i >= 0) {
mValues[i] = value;
} else {//key不存在mKey中
i = ~i;//将最后查找的索引位置恢复，此位置对应新key的值正好符合数组排序。
//key应放置的位置在size数量内，正好对应value处是DELETED。
//一般情况下根据新key是根据排序插入的，此位置key已经有值了，value也会被占坑。
//如果value被delete，就可以将key替换这个旧key，同时value也设置新的。
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
//下面的情况说明
//key最大，应放在size处，0到size-1的值都比它小。
//或者key值可以放到位置i，位置i处有其他value有用，非DELETED。
if (mGarbage && mSize >= mKeys.length) {
gc();
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
//key插入到合适位置i。mKeys后面的元素需要后移。自增mSize。
//当遇到数组元素不够时，自动扩容
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}
根据 key 值，在数组 mKeys 查找索引，二分查找算法，如果查值 >=0，同步更新数组 mValues 相同索引的 value 值即可。
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值在array的索引，
}
}
return ~lo; //未找到value，不可能返回一个正确的索引，因此返回负值
}
如果 key 不在数组中，情况比较复杂，源码的逻辑如下。
1，取反返回值，从上面 binarySearch 源码可知，当未找到时，返回最后查找的索引位置取反 (<0)。key 数组升序存储，该 key 值在数组排序应该插入的位置。
2，如果索引在 mSize 范围且这个位置的 value 已被删除( DELETED 状态)。那么，可以直接将 value 值放到数组 mValues 的此索引位置，并替换掉 key。如果不满足以上条件，说明这个位置存在有用的 key 和 value 值，无法替换。或者插入位置在末尾，即当 key >= mSize，应该插入 mSize 索引处，该索引目前 value 无值，也不能直接插入，防止已经达到 length，要走后面的逻辑，垃圾状态时清理数组重排，以及最后的强行插入，自动扩容。
mSize 是当前数组的元素个数，mKeys.length 返回的是数组大小。
3，GrowingArrayUtils() 方法，key 和 value 插入索引位置，此索引后面元素将后移，容量不足时，还会自动扩容，自增 mSize，表示数组又增加了一个元素。
垃圾清理，当有垃圾标志时，且 mSize>= 数组 length，说明数组已经无位置啦，有一个 gc 的过程，遍历一次，将带垃圾 Object 的 value 清理掉，重新放置数组元素，这个过程试图减小 mSize 使其小于 length，并重新查找该 key 的位置。
垃圾标志，在 removeAt() 方法，从 value 的数组删除某项 key 的 value 时，将该 value 位置值指向 DELETED，它是一个内部 Object 对象。
private static final Object DELETED = new Object();
public void removeAt(int index) {
if (mValues[index] != DELETED) {
mValues[index] = DELETED;
mGarbage = true;
}
}
数组查找数据
public E get(int key, E valueIfKeyNotFound) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i < 0 || mValues[i] == DELETED) {
return valueIfKeyNotFound;
} else {
return (E) mValues[i];
}
}
根据 key，二分查找算法，计算索引，返回数组 mValues 该索引 value 值。若查找的索引小于0，说明数组不存在 key 键或 value 数组索引值 DELETED，返回默认 valueIfKeyNotFound。
三、总结
SparesArray 用两个数组存储 key 和 value，保持相同索引，int 数组和 Object 数组。key 键是 int 基本数据类型，不需要 hash 计算，直接返回索引。
HashMap 的 key 键必须是引用类型，SparesArray 可以避免 key 的自动装箱，数据量不大时可以代替 HashMap，更省内存。
采用二分查找算法获取数据 value。
任重而道远
