上一次介绍了HashMap的原理，HashMap采用一维数组+单链表+二叉树的数据结构。今天看下android对map类型的优化，SparseArray的原理。在没有hash冲突的情况下HashMap那种桶排序的算法查找速度应该是最快的，缺点是在数据量较少时，内存的利用率不高，而SparseArray在数据冲突的时候可能会进行垃圾回收，提高了内存利用率。
SparseArray原理.jpg
成员变量和构造函数
首先看下成员变量，可以看到有两个一维数组，mKeys和mValues。SparseArray限定了key的类型是int基本类型。
@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;
接下来看构造函数，默认情况下初始容量是0，初始没有数据的情况下是不需要额外分配内存的。
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;
}
数据插入过程
看看put方法插入一个数据的过程，这里重要的是二分查找，获取key的索引位置。
public void put(int key, E value) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);//1
if (i >= 0) {
mValues[i] = value;//2
} else {
i = ~i;//3
if (i < mSize && mValues[i] == DELETED) {//4
mKeys[i] = key;
mValues[i] = value;
return;
}
if (mGarbage && mSize >= mKeys.length) {
gc();//5
// Search again because indices may have changed.
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);//6
}
//7
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}
1.通过二分查找方法找到该key值所在的索引位置；
2.如果该key值已经存在，直接替换该位置的value；
3.如果该key不存在，对二分查找返回的位置i取反，这里取反的原因待会看看binarySearch方法；
4.如果应该插入的索引位置value=DELETED状态，直接插入该位置，覆盖原来的key和value；
5.如果该索引位置已经有元素，且当前数组已满，执行gc方法回收DELETED的位置；
6.重新通过二分查找方法找到key应该存放的位置，并取反；
7.通过GrowingArrayUtils.insert方法插入元素。
二分查找
接下来看看二分查找方法：
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;//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//2
}
1.每次对索引做除2运算，所以每次查找的位置是n/2，n/4，n/8，最后是n/(2^k)，k是n的对数，查找时间复杂度是O(log n)。
2.如果找不到该元素，返回当前查找位置的反码。
注意计算机保存的是二进制的补码，所以这里取反并不是直接对原码取反，而是补码。比如lo=4，原码和补码都是0100，取反后变成1011，如果要输出，就需要将补码转换成原码，先减1，变成1010，然后对非符号位取反，变成1101，得到的结果是-5。
垃圾回收
接下来看看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) {//1
if (i != o) {
keys[o] = keys[i];
values[o] = val;
values[i] = null;
}
o++;
}
}
//2
mGarbage = false;
mSize = o;
// Log.e("SparseArray", "gc end with " + mSize);
}
1.遍历数组，如果元素不是DELETED状态，就将元素移动到values[o]位置，将原来values[i]位置设置为null。
2.最后将垃圾回收标志设置为false，数组容量更新为有效元素个数。
数据插入
看完了查找和垃圾回收，最后看一下数据插入的过程：
public static <T> T[] insert(T[] array, int currentSize, int index, T element) {
assert currentSize <= array.length;
if (currentSize + 1 <= array.length) {//1
System.arraycopy(array, index, array, index + 1, currentSize - index);
array[index] = element;
return array;
}
@SuppressWarnings("unchecked")
T[] newArray = ArrayUtils.newUnpaddedArray((Class<T>)array.getClass().getComponentType(),
growSize(currentSize));//2
System.arraycopy(array, 0, newArray, 0, index);//3
newArray[index] = element;//4
System.arraycopy(array, index, newArray, index + 1, array.length - index);//5
return newArray;//6
}
1.如果当前数组有空位，即容量大于实际元素个数，将index及以后的数据后移一位，在原来的index位置插入新数据；
2.如果当前数组没有空余容量，先对数组进行扩容；
3.将原来数组index之前的元素复制到新数组中；
4.将新数据插入index位置；
5.将原来数组index以及之后的数据复制到新数组中；
6.返回新数组。
数据获取过程
数据获取就是一个简单的二分查找过程，上面已经分析过，这里就不介绍了。
public E get(int key) {
return get(key, null);
}
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];
}
}
参考：
https://juejin.im/entry/57c3e8c48ac24700634bd3cf
https://blog.csdn.net/weixin_34008933/article/details/91397619
网友评论