Android特有的数据结构：SparseArray
SparseArray ，稀疏数组，是Android中特有的数据结构，从Android 1.0就有，主要目的是为了节省内存。SparseArray 的实现简洁，源码仅500余行，值得学习。
1、SparseArray数据存储方式
java中的HashMap是采用数组+链表存储(java1.8以后，链表超过8个采用红黑树存储)。而SparseArray是用两个数组去存储数据：int类型的key和任意类型的value。
一共用到了以下几个成员：
//此对象用来标记位置被删除
private static final Object DELETED = new Object();
//表记是否需要gc，置空
private boolean mGarbage = false;
//数组存储key
private int[] mKeys;
//对应位置存储value值
private Object[] mValues;
//当前SparseArray的size
private int mSize;
看一下它的构造函数，默认构造函数，构造一个容量为10的稀疏数组。
/**
* Creates a new SparseArray containing no mappings.
*/
public SparseArray() {
this(10);
} 另外一个有参构造函数，需要传入一个initialCapacity指定初始化稀疏数组的容量。并且初始化mValues和mKeys两个数组：
/**
* 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;
}
2、SparseArray添加数据
使用put(int key, E value)向稀疏数组中添加数据：
/**
* 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存储
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
//已经存储过key值，直接替换对应位置的mValues值
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);
}
//容量不够的话，以两倍扩容
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
} 其中用到了二分查找，从mKeys数组中查找是否已经存储过对应的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
} 如果容量满了，会通过GrowingArrayUtils的insert(mKeys, mSize, i, key)方法去扩容：
/**
* Given the current size of an array, returns an ideal size to which the array should grow.
* This is typically double the given size, but should not be relied upon to do so in the
* future.
*/
public static int growSize(int currentSize) {
return currentSize <= 4 ? 8 : currentSize * 2;
} 后来SparseArray新增了一个方法：set(int key, E value)，为了支持Kotlin的[index]= operator操作：
/**
* Alias for {@link #put(int, Object)} to support Kotlin [index]= operator.
* @see #put(int, Object)
*/
public void set(int key, E value) {
put(key, value);
} 还有append(int key, E value)方法也可以插入数据。
3、SparseArray获取数据
通过get(int key)方法从SparseArray获取数据，对应key没有value的话默认返回null。
/**
* 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);
} 也可以使用get(int key, E valueIfKeyNotFound)指定默认返回值。
/**
* 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];
}
} 同样的，通过二分查找从mKeys里面找到对应key的索引，返回对应mValues里面的值。如果没有的话返回默认值。
4、SparseArray删除数据
通过delete(int key)删除稀疏数组中指定key和对应的值，通过二分查找找到对应的key索引位置，将对应mValues位置标记为DELETED。
/**
* 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;
}
}
} delete(int key)方法有别名方法：remove(int key)
/**
* Alias for {@link #delete(int)}.
*/
public void remove(int key) {
delete(key);
} 除了通过key删除数据，removeAt(int index)方法还能直接删除指定索引位置的数据，不过需要注意索引的范围不能超过数据大小。
/**
* Removes the mapping at the specified index.
*
* <p>For indices outside of the range <code>0...size()-1</code>,
* the behavior is undefined for apps targeting {@link android.os.Build.VERSION_CODES#P} and
* earlier, and an {@link ArrayIndexOutOfBoundsException} is thrown for apps targeting
* {@link android.os.Build.VERSION_CODES#Q} and later.</p>
*/
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;
}
} 或者removeAtRange(int index, int size)删除指定范围的数据：
/**
* Remove a range of mappings as a batch.
*
* @param index Index to begin at
* @param size Number of mappings to remove
*
* <p>For indices outside of the range <code>0...size()-1</code>,
* the behavior is undefined.</p>
*/
public void removeAtRange(int index, int size) {
final int end = Math.min(mSize, index + size);
for (int i = index; i < end; i++) {
removeAt(i);
}
} 值得注意的是SparseArray中的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);
}
与之类似的SparseBooleanArray、SparseIntArray、SparseLongArray也是同样的实现方式。
