SpareseArray源码分析
站长
· 阅读数 1
SpareseArray 是Android内置的一种数据结构，用来替换key是int类型的HashMap。由于Key是int类型，所以他省去了解包的过程以及data数据不依赖于额外的对象（pair），能够减少内存占有。不过缺点也是有的，因为是使用二分搜索，所以他的查找效率是低于HashMap的，根据官方注释，小于100的items的时候搜索效率相比HashMap小于50%。与此同时，SpareseArray在扩容上使用了延后删除，当第一次删除时使用DELETE对象替换被删除的数据，使得该key-value可以复用。
类定义
//比较简单的定义，仅实现了一个标记作用的接口Cloneable
public class SparseArray<E> implements Cloneable
属性定义
//删除标志符，mValues[i]=DELETED表示该数据被删除了
private static final Object DELETED = new Object();
//是否存在垃圾的标志，用于gc判断
private boolean mGarbage = false;
//key值数组
private int[] mKeys;
//value数组
private Object[] mValues;
//当前容量
private int mSize;
构造方法
//默认容量是10
public SparseArray() {
this(10);
}
public SparseArray(int initialCapacity) {
if (initialCapacity == 0) {
//当默认容量是0的时候创建空数组
mKeys = EmptyArray.INT;
mValues = EmptyArray.OBJECT;
} else {
//这里调用的是一个未公开的API
//最终会通过调用虚拟机调用native的新建数组，开辟一块内存空间
//返回的数组也许会大于指定的容量
mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
mKeys = new int[mValues.length];
}
mSize = 0;
}
查
//是否存在
public boolean contains(int key) {
return indexOfKey(key) >= 0;
}
//找到key对应的索引
public int indexOfKey(int key) {
//如果当前存在垃圾，则进行一次垃圾回收
if (mGarbage) {
gc();
}
//通过二分搜索找到key在数组中的索引
return ContainerHelpers.binarySearch(mKeys, mSize, key);
}
public E get(int key) {
return get(key, null);
}
public E get(int key, E valueIfKeyNotFound) {
//找到key在数组中的索引
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i < 0 || mValues[i] == DELETED) {
//如果当前索引位置的数据是DELETE标志，说明数据不存在
return valueIfKeyNotFound;
} else {
//否则返回找到的数据
return (E) mValues[i];
}
}
二分搜索：
// 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
}
}
//注意这里返回值取反
//lo是没有搜索到该值时该值应该存在的位置
//取反返回负数方便后面判断，同时后面可以再次取反得到本应插入的问题，在插入数据时候会很方便
//这也就是为什么没有排序相关的代码
return ~lo; // value not present
}
增/改
public void put(int key, E value) {
//找到当前key的索引
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
//当前key存在
if (i >= 0) {
mValues[i] = value;
} else {
//当前数据不存在，～i是当前key应该存放的位置
i = ~i;
//如果当前key的值是DELETE标志则直接赋值
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
//如果当前存在辣鸡同时使用的（逻辑）数据大于等于实际数据，进行gc辣鸡回收
if (mGarbage && mSize >= mKeys.length) {
gc();
//再次搜索i，因为垃圾搜索以后坐标会变
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
//隐藏api，主要是数组插入数据使用的
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}
GrowingArrayUtils.insert:
public static <T> T[] insert(T[] array, int currentSize, int index, T element) {
assert currentSize <= array.length;
//小于数组长度，直接移动数组内数据即可
if (currentSize + 1 <= array.length) {
System.arraycopy(array, index, array, index + 1, currentSize - index);
array[index] = element;
return array;
}
//大于现有数组长度，需要新建数组，将原数组数据拷贝至新数组
T[] newArray = (T[]) Array.newInstance(array.getClass().getComponentType(),
growSize(currentSize));
System.arraycopy(array, 0, newArray, 0, index);
newArray[index] = element;
System.arraycopy(array, index, newArray, index + 1, array.length - index);
return newArray;
}
删
SparesArry的删除有2种：delete和gc，前者是在原有的数组位置使用DELETE标志占位，减少数组扩容的次数，后者是真正的移除数据。
remove:
//使用这个方法需要注意index是否会数组越界，否则会抛出错误
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;
}
}
delete：
//将key对应位置数据修改为DELETE，同时标记存在垃圾
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:
//gc主要是将DELETE数据给清除掉，将DELETE后一位的数据赋值给DELETE，并且后面所有数据往前移动一位
//真正的数组压缩并没有在这里做，而是在insert时候，会进行数组内存空间的压缩
private void gc() {
int n = mSize;
int o = 0;
int[] keys = mKeys;
Object[] values = mValues;
for (int i = 0; i < n; i++) {
Object val = values[i];
//当val==DELETE时，o不会递增，也就是o会留在DELETE位置
if (val != DELETED) {
if (i != o) {
//如果i！=o说明已经遇到了DELETE
//如果当前o就是DELETE，则正好把o覆盖
//如果当前o不是DELETE，则说明之前已经覆盖过了，这个时候相当于把后一位的数据覆盖掉前一位的
keys[o] = keys[i];
values[o] = val;
values[i] = null;
}
o++;
}
}
mGarbage = false;
//新的实际容量
mSize = o;
}
总结
双数组存储
采用SparseArray采用两个数组存储了key和valuse，其中key必须是int类型（其他类型的Sparse是可以支持。比如：SparseLongArray, LongSparseArray注意两个区别，类型在前面的，标识key是long类型，类型在中间的，标识valuse是long类型）
逻辑删除
SparseArray在删除数据的时候，只是标记，不做物理删除。好处：重复利用位置和多次删除后，在获取数据或者put数据时，一次就可以全部删除，这也是SparseArray的好处，避免数组创建，减少内存，这是主要目的，所以牺牲了性能，haspmap是通过牺牲内存，来提高性能。
二分查找，并记录插入位置
SparseArray 二分查找，返回插入位置取反，一举3得（确定是否找到、确定插入位置，保证mKey有序），值得我们在工作中借鉴。
大量数据时性能不好
SparseArray每次插入或者获取数据时，需要做一次二分查找，性能较hashmap直接hash慢，所以大量数据时不建议使用，google官方减少，容纳100个数据时，性能小于50%。
remove需判断数组越界
通过remove(index)的时候，一定要注意数组越界判断。否则崩溃。
没有扩展，每次只新增一个位置
SparseArray，没有扩容说法，每次都是新增一个索引位且只在put的时候。
实用范围
如果相同位置对象删除、插入操作频繁，则非常适合。如果大量删除、查询连续操作，则效果不好。适合数据量较少的情况下。