Android 开发也要懂得数据结构 - SparseArray源码
- 在之前分析 HashMap 就知道当容量达到 75% 时就需要扩容，那也就意味着 25% 的内存空间啥也不放，浪费掉了，为了解决这个问题，就有了 SparseArray。
- 本文章使用的是 JDK1.8 ，不同版本源码有差异。
- 可先食用 Android 开发也要懂得数据结构 - HashMap源码 。
1.SparseArray特点
- SparseArray的结构是 双数组 ，就是key和value都是数组，下标一一对应。
- SparseArray虽然是 key-valye 结构，但是key只能是 int 类型，用于代替 HashMap<Integer,Object>，这也是缺点，还有 LongSparseArray。
- HashMap 处理 int 类型的key，是需要 装箱成Integer类型 ，消耗一些资源，而 SparseArray 就不需要装箱操作，更快一些。
- HashMap 保存数据是以 Entry对象保存，还要计算hashCode，在内存方面是要大于 SparseArray。
- SparseArray 的查找速度比较快，利用的是二分法查找，二分查找的要求就是key是有序排列的。
- 二分查找虽然挺快的，数据量大的时候跟HashMap比就没有什么优势了，千级以下使用。
2.SparseArray常用的方法
2.1 基本参数
- DELETED 是删除的位置放的东西，SparseArray 删除相当于是打上标记，就不需要移动数组，减少数组移动的耗时。
- mGarbage 标志是如果有删除，就为true，用于后面的 gc() 方法的标记。
- 可以看到 SparseArray 的 key 和 value 都是数组。
- 还有一个长度mSize，与List,Map一样样，这个是实际数据的长度，不是容量的大小。
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;
复制代码2.2 构造方法
- 构造方法两种，可以选填容量大小或者不填，不填容量，容量默认就为10。
- 如果填写的容量为0，那就会创建一个非常轻量的数组。
/**
* 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。
mSize = 0;
}
复制代码2.3 二分查找 ContainerHelpers.binarySearch(mKeys, mSize, key)
- 显示利用二分法，找出要放入元素的 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) {
//检索的范围最小就为中间+1
lo = mid + 1;
} else if (midVal > value) {
//如果大于，范围的最大就为中间-1
hi = mid - 1;
} else {
//找到就返回下标位置
return mid; // value found
}
}
//找不到就返回lo取反
return ~lo; // value not present
}
复制代码2.4 放入元素 put(int key, E value)
- 如果 key 位置已存在，直接覆盖。
- 如果找不到 key 对应下标，且在范围内，有删除过闲置的位置，就把当前数据放在这个位置。
- 如果这都不满足条件，就调用 gc() 方法整理一遍数据，把标记过删除的位置，干掉，再插入数据。
- 插入元素如果容量不够，就扩容，如果原始容量小于4的，扩容成8，否则就以2倍的大小扩容。
- 数组的插入需要移动后面位置的元素。
/**
* 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;
//如果i小于长度，且i位置没东西，就放在i位置。
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
//如果有垃圾（删除过东西），且数据容量长度大于等于key数组时
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++;
}
}
//GrowingArrayUtils.insert
/**
* Primitive int version of {@link #insert(Object[], int, int, Object)}.
*/
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 = new int[growSize(currentSize)];
System.arraycopy(array, 0, newArray, 0, index);
newArray[index] = element;
System.arraycopy(array, index, newArray, index + 1, array.length - index);
return newArray;
}
//GrowingArrayUtils.growSize
//扩容，如果容量小于4的，扩容成8，否则就以2倍的大小扩容。
/**
* 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;
}
复制代码2.5 整理数据 gc()
- 把非 DELETED 位置的数据，一个个往前移动。
- mGarbage 设置为 false 。
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);
}
复制代码2.6 删除元素 remove(int key)或者delete(int key)
- 我们知道真正数组的删除，是要以移动后面的元素的，每次会造成大量的操作，所以改为标记清除，先打上标记，可以在放入元素时重新利用上空闲的位置，或者后面gc时再一次性清除掉。
/**
* Alias for {@link #delete(int)}.
*/
public void remove(int key) {
delete(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;
}
}
}
复制代码2.7 查找元素 get(int key)
- 利用二分查找找出 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];
}
}
复制代码2.8 查找key对应的下标 indexOfKey(int key)
- 如果有标记垃圾，先整理一遍再放回 key 对应的下标。
/**
* 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);
}
复制代码2.9 查找value对应的下标 indexOfValue(E value)
- 查找之前依然会整理一次数据，不同位置都可能保存着这个value,所以遍历后，返回第一个，如果找不到就返回-1。
/**
* Returns an index for which {@link #valueAt} would return the
* specified value, 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) {
return i;
}
}
return -1;
}
复制代码2.10 长度size()
- 返回数据的长度。
/**
* Returns the number of key-value mappings that this SparseArray
* currently stores.
*/
public int size() {
if (mGarbage) {
gc();
}
return mSize;
}作者：包籽
链接：https://juejin.cn/post/6922733430719381511
来源：掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
