容器类源码解析系列（四）—SparseArray分析
引言
容器类源码解析系列已经更新到了第四篇，前三篇已经分别对ArrayList、LinkedList、HashMap进行源码分析。
SparseArray 是用来存储Key-Value这种映射关系的容器，它要求Key的类型必须是int型。
要点
-
Key的类型必须是int型；
-
SparseArray底层通过双数组的结构实现数据存储，一个数组用来存储key值，一个数组用来存储value；
-
相较于HashMap，在存储key（int型）-value数据时，SparseArray会更省内存，但是在数据量大的情况下，查找效率没有HashMap好。
-
Sparse可以存储NULL值，没有fail-fast机制；
关于fail-fast机制，容器类源码解析系列（一）—— ArrayList 源码分析(最新版) 这篇文章有详细介绍。
构造方法
在看构造方法之前先看一下几个重要成员变量。
private static final Object DELETED = new Object();
private boolean mGarbage = false;
private int[] mKeys;
private Object[] mValues;
private int mSize;
mKeys和mValues是我上面提到的那两个数组，分别用来存储key和value的。mSize表示容器中key-value键值对的数量。
DELETED是什么呢？还有mGarbage？
上面的要点中，我们提到，SparseArray在存储数据时比HashMap更省内存，但是效率没有HashMap高，SparseArray使用了二分查找，这个我们在后面的源码分析中能够看到。
所以SparseArray想了一个方法来提高效率，就用到了DELETED和mGarbage这两个变量。这个方法是，在删除数据时，没有立马把数据置空回收，重组数组结构，而是先把要删除的value先置为DELETED状态，在后面合适的时机，mGarbage会被置为true，然后调用gc方法，统一清除DELETED状态的数据，重新调整容器结构。而在这个过程中，如果有新添加的数据，是可以复用DELETED状态对应的index的，这样DELETED数据又会变成正常数据，不会被回收了。 这样就避免了频繁的回收调整次数。
/**
* 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 {
mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
mKeys = new int[mValues.length];
}
mSize = 0;
}
构造方法很简单，就两个构造方法，默认的不传capacity参数的情况下创建的数组长度是10。
常规操作
添加数据
/**
* 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) {
//通过二分查找来找到mKeys数组中对应key的index索引。
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) { //如果找到了，表示之前存过这个key，则覆盖旧的value。
mValues[i] = value;
} else {
i = ~i;//取反，把负数变成正数。（注释一）
if (i < mSize && mValues[i] == DELETED) {//如果这个key对应的value之前被删除了，但是还没有被执行gc操作，目前还是DELETED状态，那么就复用此index。(注释二)
mKeys[i] = key;
mValues[i] = value;
return;
}
if (mGarbage && mSize >= mKeys.length) {
gc();
// Search again because indices may have changed.
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);//插入新key，如果需要扩容，就像ArrayList那样，通过copy操作来完成。
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);//插入新value
mSize++;//表示新添加了一对key-value键值对。
}
}
上面在查找key对应的索引时，使用了二分查找二分搜索算法 。我们看下代码：
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
}
~ 操作是什么意思呢？表示按位取反。
假设lo值为3；int是四个字节，其二进制表示为：00000000 00000000 00000000 00000011，那么~3 就等于：
11111111 11111111 11111111 11111100 等于-4。
所以注释一处的操作就好理解了。注释二 的行为表现就是我们上面说到的DELETED状态的妙用，用来提高效率的。
set 操作
public void setValueAt(int index, E value) {
if (mGarbage) {
gc();
}
mValues[index] = value;
}
这里要注意index的范围要在0~size()-1之间。
删除操作
public void delete(int key) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
if (mValues[i] != DELETED) {
mValues[i] = DELETED;
mGarbage = true;
}
}
}
可以看到，它在执行删除操作时并没有立马把对应的value置为null。而是先设置为DELETED状态，然后后面找到合适时机一致回收，这个期间该key是可以被复用的，如果被复用那么DELETED状态可以重新变成NORMAL状态。 我们同时也注意到mGarbage这个标志位在此刻被置为了true。
/**
* Removes the mapping at the specified index.
*
* <p>For indices outside of the range <code>0...size()-1</code>,
* the behavior is undefined.</p>
* 主要index的范围问题
*/
public void removeAt(int index) {
if (mValues[index] != DELETED) {
mValues[index] = DELETED;
mGarbage = true;
}
}
get操作
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];
}
}
gc
private void gc() {
// Log.e("SparseArray", "gc start with " + mSize);
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) {
if (i != o) {
keys[o] = keys[i];
values[o] = val;
values[i] = null;
}
o++;
}
}
mGarbage = false;
mSize = o;
// Log.e("SparseArray", "gc end with " + mSize);
}
在调用gc操作后，会对那些个DELETED状态的value统一置为null ，方便回收。同时会对index进行一次重新排序。
我们看看有哪些操作可能会触发SparseArray的gc方法 注意哦，我这篇文章里说的gc操作，指的都是SparseArray内部的gc方法。
| put(int key, E value) | size() | keyAt(int index) |
|---|---|---|
| valueAt(int index) | setValueAt(int index, E value) | indexOfKey(int key) |
| indexOfValue(E value) | indexOfValueByValue(E value) | append(int key, E value) |
总结
android开发用如果存储key-value下的key是int型的话，建议使用SparseArray容器来操作，可以减少内存消耗。