背景
SparseArray 是用于存储 K-V 的数据结构，但是并没有像 ArrayMap 和 HashMap
一样实现 Map 接口，仅仅实现了 Cloneable 接口，其内部 维护了 2 个数组，一个 int 数组用于存储 key，一个 Object 数组用于存储 value。mKeys 数组存储的元素是 key 值本省，没有进行 hash 值运算，避免了装箱操作，同时并没有像 HashMap 那样引入额外的数据结构 Entry（1.7）或者 Node（1.8），这大大提升了内存利用效率。
类结构
public class SparseArray<E> implements Cloneable {
private static final Object DELETED = new Object();
private boolean mGarbage = false;
@UnsupportedAppUsage(maxTargetSdk = 28) // Use keyAt(int)
private int[] mKeys;
@UnsupportedAppUsage(maxTargetSdk = 28) // Use valueAt(int), setValueAt(int, E)
private Object[] mValues;
@UnsupportedAppUsage(maxTargetSdk = 28) // Use size()
private int mSize;
......
}
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++;
}
}
如上，put() 方法主要做了以下操作：
- 通过二分查找在 mKeys 数组中查找对应的 key（即 mKeys 数组里面的元素是有序，这是实现二分查找法的前提）。
- 查找成功则直接更新 key 对应的 value，而且不返回旧值，而 ArrayMap 和 HashMap 都会返回旧值。
- 如果当前要插入的 key 索引上的值为 DELETE，直接覆盖。
- 如果需要执行 gc 方法 & 需要扩大数组容量，则会执行 gc 方法，由于 gc 方法会改变元素的位置，因此会重新计算插入的位置并插入，GrowingArrayUtils.insert() 源码如下：
public static int[] insert(int[] array, int currentSize, int index, int element) {
assert currentSize <= array.length;
if (currentSize + 1 <= array.length) {
System.arraycopy(array, index, array, index + 1, currentSize - index);
array[index] = element;
return array;
}
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;
}
在 array 不需要扩容的情况下可以添加一个元素，则先将待插入位置 index 开始的元素整体后移一位，然后再插入元素。否则执行 growSize() 方法进行扩容，每次扩容时如果当前容量小于等于 4 则扩容 为 8，否则扩容容量为原容量的 2 倍，代码如下：
public static int growSize(int currentSize) {
return currentSize <= 4 ? 8 : currentSize * 2;
}
删除方法
SparseArray 提供了 2 种删除方式。
- 根据 key 删除对象
/**
* 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;
}
}
}
- 根据位置删除对象
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;
}
}
这里的逻辑还是比较简单的，找到要删除的元素，标记为 DELETED，然后把 mGarbage 标记为 true。
gc
gc 方法将 mValue 数组中还未标记为 DELETED 的元素以及对应下标的 mKeys 数组中的元素移动到数组的前面，保证数组前面的数据都是有效数据，而不是存储着 DELETED。
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() 方法
get() 方法主要是通过二分查找获取到 key 的索引，通过该索引俩获取到对应的 value。源码如下：
/**
* 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];
}
}
拓展
除了 SparseArray，Android 还提供了一系列的 Sparse*() 方法，如下：
- SparseIntArray — key(int) : value(int)
- SparseBooleanArray — key(int) : value(boolean)
- SparseLongArray — ikey(int) : value(long)
总结
至此，我们大概了解 SparseArray 原理，与 HashMap 相比：
- 避免了基本数据类型的自动装箱，不会创建多余的对象，内存利用率更高。
- 没有额外的存储结点的数据结构，同上，内存利用率更高。
- 插入操作、gc 操作需要复制数组，效率低。
- 查询时间复杂度为 O(logN)，数据量巨大时查询明显下降。
网友评论