Android中的SparseArray源码解析
一、概述
在Android平台中,更推荐使用
SparseArray<E>
来替代HashMap
的数据结构,更具体的说,是用于替代key
为int
类型,value
为Object
类型的HashMap
; 用于替代HashMap<Integer, Object>
二、SparseArray的特点
和
ArrayMap
类似,它的实现相比HashMap
更加节省内存空间,而且因为指定了key
为int
类型,可以避免int->Integer
的装箱拆箱带来的性能消耗。仅仅实现了
Cloneable
接口,所以使用时不能使用Map
类型,它不是一个Map
,它也是线程不安全的,允许value为null它内部实现基于两个数组: 一个是
int[]
类型的数组mKeys
,用于保存每个Item的key
,key
本身就是int
类型,所以可以理解为hashCode
的值就是key
的值; 另一个是Object[]
类型的数组mValues
,用于保存value
,数组容量大小与mKeys
数组一致类似于
ArrayMap
,但是SparseArray
相比它的扩容更为简单,扩容时只需要数组拷贝工作,不需要重建哈希表,同样它不适合大容量的数据存储。存储大容量数据性能会下降50%。相比传统
HashMap
时间效率更低,一般HashMap基于哈希表,时间复杂度近似于O(1), 而SparseArray
则会对它的key
进行从小到大排序,然后使用二分查找查询key
对应在数组中的下标,在添加、删除、查找数据的时候都是先使用二分查找法得到相应的index,然后通过index来进行添加、查找、删除等操作。所以SparseArray
时间复杂度是O(logn),相对于O(1)的HashMap
效率比较低。那么它的key
就是按照从小到大升序存储的。
SparseArray
为了提升性能,在删除操作时做了一些优化:
当删除一个元素时,并不是立即从value
数组中删除它,并压缩数组,
而是将其在value
数组中标记为已删除。这样当存储相同的key
的value
时,可以重用这个空间。
如果该空间没有被重用,随后将在合适的时机里执行gc(垃圾收集)操作,将数组压缩,以免浪费空间。
三、SparseArray的适用场景
数据量不大
内存空间比时间效率更重要
需要使用
Map
且key
的类型是int
类型
四、SparseArray的基本使用
private void test() {
SparseArray<String> stringSparseArray = new SparseArray<>();
stringSparseArray.put(1, "a");
stringSparseArray.put(5, "c");
stringSparseArray.put(4, "e");
stringSparseArray.put(6, null);
Log.d(TAG, "onCreate() called with: stringSparseArray = [" + stringSparseArray + "]");
}
输出结果:
//可以看出是按照key的升序排序的
onCreate() called with: stringSparseArray = [{1=a, 4=e, 5=c, 6=null}]
五、SparseArray的源码解析
1、构造器
//用于标记value数组,作为已经删除的标记
private static final Object DELETED = new Object();
//用于表示是否需要GC,这里的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) {
//初始容量为0的话,就赋值两个轻量级的引用
if (initialCapacity == 0) {
mKeys = EmptyArray.INT;
mValues = EmptyArray.OBJECT;
} else {
//否则初始化对应容量大小的int[]数组mKeys和Object[]数组mValues
mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
mKeys = new int[mValues.length];
}
//mSize用于统计集合大小,默认初始为0
mSize = 0;
}
2、集合的增加、修改
1、单个元素的增加和修改put(key, value)
public void put(int key, E value) {
//利用ContainerHelpers的binarySearch进行二分查找,找到待插入key的下标index
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
//如果i下标大于0,说明之前这个key已经存在
if (i >= 0) {
mValues[i] = value;//直接覆盖key对应的value即可
} else {
//如果i下标小于0,说明mKeys中不存在key,所以这个key是第一次插入
i = ~i;//先对返回的i取反,得到应该插入的位置i
//如果i没有越界,且对应位置是已删除的标记,则复用这个空间
if (i < mSize && mValues[i] == DELETED) {
//赋值key和value后,返回
mKeys[i] = key;
mValues[i] = value;
return;
}
//如果需要GC,且集合mSize大于mKeys的长度(需要扩容)
if (mGarbage && mSize >= mKeys.length) {
gc();//先触发GC
//gc后,下标i可能发生变化,所以再次用二分查找找到应该插入的位置i
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
//插入key(可能需要扩容)
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
//插入value(可能需要扩容)
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
//集合大小递增
mSize++;
}
}
//ContainerHelpers.binarySearch,标准二分查找的算法
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;//防止int溢出,采用位运算
final int midVal = array[mid];
if (midVal < value) {
lo = mid + 1;
} else if (midVal > value) {
hi = mid - 1;
} else {
return mid; //找到对应key
}
}
return ~lo; // 若没有找到,则low是value应该插入的位置,是一个正数。对这个正数去反,返回负数回去
}
//gc,垃圾回收函数,压缩数组
private void gc() {
int n = mSize;//保存GC前的集合大小
int o = 0;//既是下标index,又是GC后的集合大小
int[] keys = mKeys;
Object[] values = mValues;
//遍历values集合,以下算法意义为 从values数组中,删除所有值为DELETED的元素
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,那么它就是gc后的集合大小
o++;
}
}
mGarbage = false;//GC过后,修改标识,不需要GC
mSize = o;//更新gc后的集合大小
// Log.e("SparseArray", "gc end with " + mSize);
}
GrowingArrayUtils.insert:插入
public static int[] insert(int[] array, int currentSize, int index, int element) {
//断言 确认 当前集合长度 小于等于 array数组长度
assert currentSize <= array.length;
//如果不需要扩容,当前集合大小+1不超过数组容量就不需要扩容
if (currentSize + 1 <= array.length) {
//将array数组内元素,从index开始 后移一位
System.arraycopy(array, index, array, index + 1, currentSize - index);
//在index处赋值
array[index] = element;
//返回
return array;
}
//需要扩容
//构建新的数组
int[] newArray = new int[growSize(currentSize)];
//将原数组中index之前的数据复制到新数组中
System.arraycopy(array, 0, newArray, 0, index);
//在index处赋值
newArray[index] = element;
//将原数组中index及其之后的数据赋值到新数组中
System.arraycopy(array, index, newArray, index + 1, array.length - index);
//返回
return newArray;
}
//根据现在的size 返回合适的扩容后的容量
public static int growSize(int currentSize) {
//如果当前size 小于等于4,则返回8, 否则返回当前size的两倍
return currentSize <= 4 ? 8 : currentSize * 2;
}
二分查找,若未找到返回下标时,与JDK里的实现不同,JDK是返回
return -(low + 1); // key not found.
,而这里是对 低位去反 返回。这样在函数调用处,根据返回值的正负,可以判断是否找到index。对负index取反,即可得到应该插入的位置。扩容时,当前容量小于等于4,则扩容后容量为8.否则为当前集合长度的两倍。和
ArrayList,ArrayMap
不同(扩容一半),和Vector
相同(扩容一倍)。扩容操作依然是用数组的复制、覆盖完成。类似
ArrayList
.
3、集合的删除
1、按key删除
public void remove(int key) {
delete(key);//内部调用delete方法来删除
}
public void delete(int key) {
//二分查找得到要删除的key所在的index
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
//若i >= 0 表示对应key的index存在
if (i >= 0) {
//将对应index位置的value置为标志DELETED
if (mValues[i] != DELETED) {
mValues[i] = DELETED;//value置为标志DELETED
//并修改需要GC的标识为true,表示稍后需要GC
mGarbage = true;
}
}
}
2、按index删除(其实就省去二分查找的过程)
public void removeAt(int index) {
//直接索引到对应的value,将它置为标志DELETED
if (mValues[index] != DELETED) {
mValues[index] = DELETED;
//并修改需要GC的标识为true,表示稍后需要GC
mGarbage = true;
}
}
3、批量删除
public void removeAtRange(int index, int size) {
final int end = Math.min(mSize, index + size);
for (int i = index; i < end; i++) {//循环对单个元素按照index删除
removeAt(i);
}
}
4、集合的查找
1、按key进行查询
//按照key查询,如果key不存在,返回null
public E get(int key) {
return get(key, null);
}
//按照key查询,如果key不存在,返回valueIfKeyNotFound
public E get(int key, E valueIfKeyNotFound) {
//二分查找到 key 所在的index
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
//不存在
if (i < 0 || mValues[i] == DELETED) {//如果i下标小于0或者找到i对应的value是一个DELETED已删除状态,就返回value为空的默认值
return valueIfKeyNotFound;
} else {//存在就直接返回mValue数组对应i下标的值
return (E) mValues[i];
}
}
2、按index进行查询
public int keyAt(int index) {
//按照下标查询时,需要考虑是否先GC
if (mGarbage) {
gc();
}
return mKeys[index];
}
public E valueAt(int index) {
//按照下标查询时,需要考虑是否先GC
if (mGarbage) {
gc();
}
return (E) mValues[index];
}
3、查询对应的index
public int indexOfKey(int key) {
//查询下标时,也需要考虑是否先GC
if (mGarbage) {
gc();
}
//二分查找返回 对应的下标 ,可能是负数
return ContainerHelpers.binarySearch(mKeys, mSize, key);
}
public int indexOfValue(E value) {
//查询下标时,也需要考虑是否先GC
if (mGarbage) {
gc();
}
//不像key一样使用的二分查找。是直接线性遍历去比较,而且不像其他集合类使用equals比较,这里直接使用的 ==
//如果有多个key 对应同一个value,则这里只会返回一个更靠前的index
for (int i = 0; i < mSize; i++)
if (mValues[i] == value)
return i;
return -1;
}
- 按照value查询下标时,不像key一样使用的二分查找。是直接线性遍历去比较,而且不像其他集合类使用
equals
比较,这里直接使用的 ==- 如果有多个key 对应同一个value,则这里只会返回一个第一个相等value的index
六、总结
Android sdk中,还提供了三个类似思想的集合:
- SparseBooleanArray,value为boolean
- SparseIntArray,value为int
- SparseLongArray,value为long
他们和SparseArray唯一的区别在于value的类型,SparseArray的value可以是任意类型。而它们是三个常使用的拆箱后的基本类型。