SparseArray家族
SparseArray基于键值对存储数据,key为int,value为object,简单使用如下:
//声明
SparseArray<String> sparseArray= new SparseArray<>();
//增加元素,append方式
sparseArray.append(0, "myValue");
//增加元素,put方式
sparseArray.put(1, "myValue");
//删除元素,二者等同
sparseArray.remove(1);
sparseArray.delete(1);
//修改元素,put或者append相同的key值即可
sparseArray.put(1,"newValue");
sparseArray.append(1,"newValue");
//查找,遍历方式1
for(int i=0;i<sparseArray.size();i++){
Log.d(TAG,sparseArray.valueAt(i));
}
//查找,遍历方式2
for(int i=0;i<sparseArray.size();i++){
int key = sparseArray.keyAt(i);
Log.d(TAG,sparseArray.get(key));
}
LongSparseArray 和SparseArray 相比,唯一的不同就是key值为long,所以LongSparseArray可以存储的数据元素就比SparseArray多,int的范围是-2^31 到 231-1,而long是-263 到 2^63-1。
SparseBooleanArray,SparseIntArray,SparseLongArray,这三个数据结构的key值的类型也是int,value值的类型也固定,SparseBooleanArray的value固定为boolean类型,SparseIntArray的value固定为int类型,SparseLongArray的value固定为long类型。
总结一下这四种数据结构的key,value类型:
SparseArray <int, Object>
LongSparseArray <long, Object>
SparseBooleanArray <int, boolean>
SparseIntArray <int, int>
SparseLongArray <int, long>
上述四种数据结构的key类型都是int,而不是Integer,相较于使用HashMap的话,省去了装箱拆箱过程,查询、存储等操作效率更高,而且int的存储开销也远小于Integer。
SparseArray实现原理
SparseArray内部的重要属性:
public class SparseArray<E> implements Cloneable {
private static final Object DELETED = new Object();
private boolean mGarbage = false;
private int[] mKeys;
private Object[] mValues;
private int mSize;
}
DELETED
static final 的一个静态Object实例,当一个键值对被remove后,会在对应key的value下放置该对象,标记该元素已经被删除,只是标记删除,没有真正的删除。
mGarbage
当值为true,标志数据结构中有元素被删除,可以触发gc对无效数据进行回收,真正删除。
mKeys
用于存放Key的数组,通过int[] 进行存储,与HashMap相比减少了装箱拆箱的操作,同时一个int只占4字节;一个重要特点,mKeys的元素是升序排列的,也是基于此,我们才能使用二分查找。
mValues
用于存放与Key对应的Value,通过数组的position 进行映射;如果存放的是int型等,可以用SparseIntArray ,存放的Values也是int数组,性能更高。
mSize
mSize的大小等于数组中mValues的值等于非DELETED的元素个数。
remove方法源码:
public void delete(int key) {
//查找对应key在数组中的下标,如果存在,返回下标,不存在,返回下标的取反;
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
//key存在于mKeys数组中,将元素删除,用DELETED替换原value,起标记作用;
if (i >= 0) {
if (mValues[i] != DELETED) {
mValues[i] = DELETED;
mGarbage = true;
}
}
}
/**
* @hide
* Removes the mapping from the specified key, if there was any, returning the old value.
*/
public E removeReturnOld(int key) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
if (mValues[i] != DELETED) {
final E old = (E) mValues[i];
mValues[i] = DELETED;
mGarbage = true;
return old;
}
}
return null;
}
/**
* Alias for {@link #delete(int)}.
*/
public void remove(int key) {
delete(key);
}
二分查找:
class ContainerHelpers {
// This is Arrays.binarySearch(), but doesn't do any argument validation.
//第一个参数array为keys的数组,第二个为数组中元素个数(与keys的length不一定相等),第三个value为目标的key
static int binarySearch(int[] array, int size, int value) {
//lo为二分查找的左边界
int lo = 0;
//hi为二分查找的右边界
int hi = size - 1;
//还没找到,继续查找
while (lo <= hi) {
//左边界+右边界处以2,获取到mid 的index
final int mid = (lo + hi) >>> 1;
//获取中间元素
final int midVal = array[mid];
// 目标key在右部分 。。。。感觉这部分太简单了
if (midVal < value) {
lo = mid + 1;
} else if (midVal > value) {
hi = mid - 1;
} else {
//相等,找到了,返回key对应在array的下标;
return mid; //