SparseArray源码分析
引子
SparseArray是google官方提供的一种int到Object的map，文档见：SparseArray。
大家都知道Java里已经有了非常通用且功能强大的HashMap，那么Google为什么要再发明个轮子呢？这个新轮子相比有什么优势呢？下面我们先从整体上看下区别。
区别何在
从官方文档描述我们知道此类的引入主要是基于节省内存考虑，因为毕竟运行时是在终端设备上。说它更省内存，主要是因为相比HashMap，它在实现上避免了int到Integer的autobox操作，还有每次put操作需要的额外Entry对象；它的key和value分别存储在2个数组中，get时使用二分查找来定位某个key，不适合大数据量的场景比如上千，几百的量比较合适，删除操作也比较特殊，仅仅是个标记操作，内部也有自己的gc()方法用来清理压缩内存。接下来让我们进入正题。
源码分析
和以往一样，首先我们来看看其关键字段和ctor，如下：
private static final Object DELETED = new Object();
private boolean mGarbage = false;
private int[] mKeys; // 存放int key的数组，元素升序排列
private Object[] mValues;
private int mSize;
/**
* Creates a new SparseArray containing no mappings.
*/
public SparseArray() {
this(10);
}
/**
* Creates a new SparseArray containing no mappings that will not
* require any additional memory allocation to store the specified
* number of mappings. If you supply an initial capacity of 0, the
* sparse array will be initialized with a light-weight representation
* not requiring any additional array allocations.
*/
public SparseArray(int initialCapacity) {
if (initialCapacity == 0) {
mKeys = EmptyArray.INT;
mValues = EmptyArray.OBJECT;
} else {
// 分配至少initialCapacity这么大的数组
mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
mKeys = new int[mValues.length];
}
mSize = 0;
}
常量DELETED对象用来标记删除，如果某个位置的值是DELETED则表示这个位置没对应的元素（被删除了）；
mGarbage在删除操作中会被设置（置为true），表示接下来需要清理压缩了（compacting）；
mkeys，mValues分别表示SparseArray的内部存储，即分别是key、value的存储数组，mkeys在put操作中会被保证以升序的方式排列（以便二分查找能够work）；
mSize表示有效的key-value对的数目；
两个构造函数比较简单明了，无参版本会调用带参数的版本并且将初始容量设为10，我们可以看到如果initialCapacity=0的话，mkeys、mValues会分别被初始化为EmptyArray里的常量数组，实际是长度为0的数组，不会产生内存分配；在Android 9.0的设备上跑无参的版本，实际mValues为有11个元素的数组（这点细节可能跟大多数人想的不一样，因为其实newUnpaddedObjectArray实际上会分配至少initialCapacity个元素，并一定刚好等于它）。
最后都设置了mSize为0，表明当前还只是个刚被构建的空的SparseArray。
接下来看2个依据key来得到value的方法，即get方法：
/**
* Gets the Object mapped from the specified key, or <code>null</code>
* if no such mapping has been made.
*/
public E get(int key) {
return get(key, null);
}
/**
* Gets the Object mapped from the specified key, or the specified Object
* if no such mapping has been made.
*/
@SuppressWarnings("unchecked")
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];
}
}
2个版本的实现都很简单明了，唯一有趣的点是内部的ContainerHelpers.binarySearch(mKeys, mSize, key);这行代码调用；
SparseArray内部就是通过此二分查找算法来search key的，一并看下其实现：
// 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
}
如源码所说，这个版本和java.util.Arrays.java里的实现一样，只是省略了参数检查。二分查找大家都接触过，看下实现是不是很眼熟，没什么特别的，这里着重说下最后没找到时的返回值~lo。如方法的doc所说，没找到的情况下会返回一个负值，那到底返回哪个负值呢，-1行不行？其实这里的~lo就相当于-(lo+1)（参看Arrays.binarySearch的实现）。为什么要这样做，因为我们不仅想表示没找到，还想返回更多信息，即这个key如果要插进来应该在的位置（外面的代码只需要再次~即取反就可以得到这个信息）。
接下来回到刚才的get方法，明白了这里使用的二分查找这个方法就非常简单明了了。get内部通过binarySearch的返回值来做判断，如果是负的或i>=0但是位置i已经被标记为删除了则返回valueIfKeyNotFound，否则直接返回(E) mValues[i]。
紧接着来看一组delete/remove方法：
/**
* Removes the mapping from the specified key, if there was any.
*/
public void delete(int key) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) { // 元素存在的前提下
// 标记删除法！！！
if (mValues[i] != DELETED) {
mValues[i] = DELETED;
mGarbage = true;
}
}
}
/**
* Alias for {@link #delete(int)}.
*/
public void remove(int key) {
delete(key);
}
/**
* Removes the mapping at the specified index.
*/
public void removeAt(int index) {
if (mValues[index] != DELETED) {
mValues[index] = DELETED;
mGarbage = true;
}
}
/**
* Remove a range of mappings as a batch.
*
* @param index Index to begin at
* @param size Number of mappings to remove
*/
public void removeAtRange(int index, int size) {
final int end = Math.min(mSize, index + size);
for (int i = index; i < end; i++) {
removeAt(i);
}
}
delete(key)和remove(key)一样，都是先通过二分查找来找这个key，如果不存在则do nothing，否则如果这个位置还没被标记为删除则标记之，顺便设置mGarbage（之前提到过删除之类的操作都会设置这个值，表示接下来需要执行清理压缩操作了）。注意这里数组的不同处理，没有直接移动数组元素（压缩处理）来删除这个key，而仅仅是标记操作（另外留意下这些操作在执行的时候，mKeys数组并没有经过任何修改）。这2个方法都是通过key来进行操作，有时你可能想基于index来执行某些操作，上面的removeAt(index)和removeAtRange(index, size)就是这样的方法，处理也都是如果位置i没标记删除则标记之，并设置mGarbage的值。只是在removeAtRange中对上限做了保险处理即end = Math.min(mSize, index+size)，以防数组越界。
接下来该打起来精神睁大眼睛了，让我们一起来看看SparseArray的关键，姑且称之为清理压缩，上代码：
private void gc() {
// Log.e("SparseArray", "gc start with " + mSize);
int n = mSize;
// 数组的2个下标，一前一后，接下来移动数组元素需要用到
int reusedIndex = 0;
int[] keys = mKeys;
Object[] values = mValues;
for (int i = 0; i < n; i++) {
Object val = values[i];
if (val != DELETED) {
if (i != reusedIndex) {
keys[reusedIndex] = keys[i];
values[reusedIndex] = val;
values[i] = null; // 往前提后，释放此位置上的元素
}
// 如果遇到了DELETED值，那么此下标不动，i还是正常增加
// 所以下次循环执行的时候，就会发生后面的有效值覆盖掉前面DELETED的位置
// 如果遇到的是有效值，那么这2个下标是同步移动的
reusedIndex++;
}
}
mGarbage = false;
mSize = reusedIndex;
// Log.e("SparseArray", "gc end with " + mSize);
}
gc方法只有在mGarbage设置的时候才有可能调用，其总体思想是把靠后的有效元素（即没被删除的）往前（reusedIndex的位置）提，从而达到清理压缩的目的。我们仔细分析下，首先初始化一些接下来要用到的值，这里特别留意下reusedIndex（源码中叫o，实在不好理解，我按自己的理解重新命名了），初始化为0，指向第一个元素。接下来是遍历mValues数组的for循环，其内部是如果当前元素val是DELETED则啥也不做，接着看下一个元素（注意此时reusedIndex还是保持不动）；否则当前是个有效的元素，执行步骤1、2：
-
reusedIndex不是当前的index则应该把当前元素拷贝到reusedIndex的位置（key和value都复制，即往前提），当前位置的value清空（置null）；
-
reusedIndex往前+1（每遇到一个有效元素），准备下次循环。
结束遍历之后reset mGarbage（因为刚刚做过了，暂时不需要了），更新mSize为reusedIndex（因为每遇到一个有效元素，reusedIndex就+1，所以它的值就是新的mSize）。
整个gc结束后，mValues数组里的所有DELETED元素就不存在了，故mSize也会相应减小。
看完了上面的方法，我们来看下put相关的方法，代码如下：
/**
* Adds a mapping from the specified key to the specified value,
* replacing the previous mapping from the specified key if there
* was one.
*/
public void put(int key, E value) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
// 已存在，则直接用新值替换
mValues[i] = value;
} else {
i = ~i; // 再次取反，得到要插入的位置
if (i < mSize && mValues[i] == DELETED) {
// 标记为删除的位置的再次复用
mKeys[i] = key;
mValues[i] = value;
return;
}
// 到了临界点且需要触发gc，则执行一次gc方法
if (mGarbage && mSize >= mKeys.length) {
gc();
// Search again because indices may have changed.
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
// 将key、value在i的位置插入，并返回新的数组
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++; // key-value对+1
}
}
// 上面用到的GrowingArrayUtils.insert实现，代码如下：
public static int[] insert(int[] array, int currentSize, int index, int element) {
assert currentSize <= array.length;
if (currentSize + 1 <= array.length) {
// 大小够用，index处的元素往后顺延1个位置，给新的index腾出位置
System.arraycopy(array, index, array, index + 1, currentSize - index);
array[index] = element;
return array;
}
// 大小不够用，申请新的数组，拷贝，index处赋值
int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize));
System.arraycopy(array, 0, newArray, 0, index);
newArray[index] = element;
System.arraycopy(array, index, newArray, index + 1, array.length - index);
return newArray;
}
put实现关键的几个点，也已经写在上面的代码注释里了，可以重点关注下。
看完了上面put的实现后，最后来看看几个非常简单的方法，
/**
* Returns the number of key-value mappings that this SparseArray
* currently stores.
*/
public int size() {
if (mGarbage) {
gc();
}
return mSize;
}
/**
* Given an index in the range <code>0...size()-1</code>, returns
* the key from the <code>index</code>th key-value mapping that this
* SparseArray stores.
*
* <p>The keys corresponding to indices in ascending order are guaranteed to
* be in ascending order, e.g., <code>keyAt(0)</code> will return the
* smallest key and <code>keyAt(size()-1)</code> will return the largest
* key.</p>
*/
public int keyAt(int index) {
if (mGarbage) {
gc();
}
return mKeys[index];
}
/**
* Given an index in the range <code>0...size()-1</code>, returns
* the value from the <code>index</code>th key-value mapping that this
* SparseArray stores.
*
* <p>The values corresponding to indices in ascending order are guaranteed
* to be associated with keys in ascending order, e.g.,
* <code>valueAt(0)</code> will return the value associated with the
* smallest key and <code>valueAt(size()-1)</code> will return the value
* associated with the largest key.</p>
*/
@SuppressWarnings("unchecked")
public E valueAt(int index) {
if (mGarbage) {
gc();
}
return (E) mValues[index];
}
/**
* Given an index in the range <code>0...size()-1</code>, sets a new
* value for the <code>index</code>th key-value mapping that this
* SparseArray stores.
*/
public void setValueAt(int index, E value) {
if (mGarbage) {
gc();
}
mValues[index] = value;
}
/**
* Returns the index for which {@link #keyAt} would return the
* specified key, or a negative number if the specified
* key is not mapped.
*/
public int indexOfKey(int key) {
if (mGarbage) {
gc();
}
return ContainerHelpers.binarySearch(mKeys, mSize, key);
}
/**
* Returns an index for which {@link #valueAt} would return the
* specified key, or a negative number if no keys map to the
* specified value.
* <p>Beware that this is a linear search, unlike lookups by key,
* and that multiple keys can map to the same value and this will
* find only one of them.
* <p>Note also that unlike most collections' {@code indexOf} methods,
* this method compares values using {@code ==} rather than {@code equals}.
*/
public int indexOfValue(E value) {
if (mGarbage) {
gc();
}
for (int i = 0; i < mSize; i++)
if (mValues[i] == value) // 唯一需要留意的是这里比较用的==，而非equals
return i;
return -1;
}
/**
* Removes all key-value mappings from this SparseArray.
*/
public void clear() {
int n = mSize;
Object[] values = mValues;
for (int i = 0; i < n; i++) {
values[i] = null;
}
mSize = 0;
mGarbage = false;
}
size()方法返回当前有效的key-value对的数目，值得注意的是在其内部都会有条件的执行gc方法，因为之前的操作可能导致mGarbage被设置了，所以必须执行下清理压缩才能返回最新的值；
keyAt(index)和valueAt(index)提供了遍历SparseArray的方式，如下：
for (int i = 0; i < sparseArray.size(); i++) {
System.out.println("key = " + sparseArray.keyAt(i) + ", value = " + sparseArray.valueAt(i));
}
同样和size()方法一样其内部也都会有条件的执行gc方法，注意你传递的index必须在[0, size()-1]之间，否则会数组越界。
setValueAt让你像使用数组一样设置某个位置处的值，同样会有条件的执行gc方法。
indexOfKey通过二分查找来search key的位置；indexOfValue在整个mValues数组中遍历查找value，有则返回对应的index否则返回-1。
clear()方法清空了mValues数组，重置了mSize，mGarbage，但请注意并没有动mKeys数组；
目前为止，SparseArray类的所有关键代码都已经分析完毕，希望对各位平时的开发有所帮助，祝好。
