SparseArray解析
SparseArray
Sparse[spɑːrs]
文档介绍
/**
* <code>SparseArray</code> maps integers to Objects and, unlike a normal array of Objects,
* its indices can contain gaps. <code>SparseArray</code> is intended to be more memory-efficient
* than a
* <a href="/reference/java/util/HashMap"><code>HashMap</code></a>, because it avoids
* auto-boxing keys and its data structure doesn't rely on an extra entry object
* for each mapping.
*
* <p>Note that this container keeps its mappings in an array data structure,
* using a binary search to find keys. The implementation is not intended to be appropriate for
* data structures
* that may contain large numbers of items. It is generally slower than a
* <code>HashMap</code> because lookups require a binary search,
* and adds and removes require inserting
* and deleting entries in the array. For containers holding up to hundreds of items,
* the performance difference is less than 50%.
*
* <p>To help with performance, the container includes an optimization when removing
* keys: instead of compacting its array immediately, it leaves the removed entry marked
* as deleted. The entry can then be re-used for the same key or compacted later in
* a single garbage collection of all removed entries. This garbage collection
* must be performed whenever the array needs to be grown, or when the map size or
* entry values are retrieved.
*
* <p>It is possible to iterate over the items in this container using
* {@link #keyAt(int)} and {@link #valueAt(int)}. Iterating over the keys using
* <code>keyAt(int)</code> with ascending values of the index returns the
* keys in ascending order. In the case of <code>valueAt(int)</code>, the
* values corresponding to the keys are returned in ascending order.
*/
复制代码SparseArray是谷歌提供的k-v键值对存储类，key固定为int，value为泛型(内部为Object)。虽然
内部主要方法
ContainerHelpers
工具类，二分查找法查找int或者long值，找到返回index，没有找到返回取反后的值(为负数)。
PS:
>>: 带符号右移
>>>: 无符号右移
最高位为1表示负数，负数则数值位取反
01111111111111111111111111111111 int maxVal 补:01111111111111111111111111111111
10000000000000000000000000000000 int minVal 补:11111111111111111111111111111111
因为在计算机系统中，数值一律用补码来表示和存储。0的补码属于正数范围,所以int值的范围高区间(正数区间)减1:
-2^31~2^31-1
复制代码// 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 取反为负
}
复制代码put
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;
}
//可能碰到需要重新排列，如果重排则重新计算索引位置。
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++;
}
}
复制代码先用二分查找法查找查找值的index，index大于0则集合中存在，小于0则不存在(见ContainerHelpers)。找到则更新；没找到，则获取需要插入的index位置(返回的负数为插入位置取反)，key数组和value数组分别在对应index插入元素。也就是说这里面的元素是通过key的大小进行排序的。其中插入元素的方法是在GrowingArrayUtils.insert内部中调用System.arraycopy，内部真实数组的size在这里进行改变。
delete
删除某个键值对，这里的删除并不是真实删除，而是把它的value标记为DELETED，mGarbage标记为true。然后在put、size、keyAt、valueAt、setValueAt、indexForKey、indexOfValue、indexOfValue、indexOfValueByValue、append等方法中触发成员gc方法。
/**
* 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;
}
}
}
复制代码gc
遍历数组，把未被标记为DELETE的元素放到数组前面，并刷新size大小。(这里的size并不是内存两个数组的size大小，而是有效位数的大小)
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);
}
复制代码get
通过key获取元素。根据调用方法获取不到返回默认或者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);
}
/**
* 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];
}
}
复制代码append
对比put，在append的元素大于最大的一个的时候，直接追加在最后，而不是先二分查找再插入。不大于最后一个的时候就调用put。
/**
* Puts a key/value pair into the array, optimizing for the case where
* the key is greater than all existing keys in the array.
*/
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++;
}
复制代码和HashMap、ArrayMap对比，SparseArray的优缺点：
SparseArray的限制在于键必须是int类型，值必须是Object类型。这样可以避免key自动装箱产生过多的Object。但是这样的话，如果key值相同，那么数据就会被直接覆盖。
SparseArray不能保证保留它们的插入顺序，在迭代的时候应该注意。SparseArray中没有Iterator，SparseArray只实现了Cloneable接口，而没有继承Collection、List或者Map接口。
查找数据的时候使用的是二分法，明显比通过hashcode慢，所以数据越大，查找速度慢的劣势越明显，所以SparseArray适于数据一千以内的场景中。
优点：
- 避免了基本数据类型的装箱操作
- 不需要额外的结构体，单个元素的存储成本更低
- 数据量小的情况下，随机访问的效率更高
缺点：
- 插入操作需要复制数组，增删效率降低
- 数据量巨大时，复制数组成本巨大，gc()成本也巨大
- 数据量巨大时，查询效率也会明显下降
————————————————
参考资料:
">
">
