SparseArray分析
SparseArray是一个稀疏数组，所谓稀疏数组就是指数组中的大部分内容值未被使用（或者为零），只有很少部分的空间被使用。因此造成了内存空间的浪费，为了节省内存空间，并且不影响数组中的原始内容值，我们可以采用一种压缩的方式来表示数组的内容。故稀疏数组我们可以看做是普通数组的压缩。
例如：
我们有一个5*9的数组，普通数组的表示如下
0 0 0 0 0 0
0 1 0 0 0 0
0 0 0 0 0 0
0 4 0 0 0 0
0 0 0 0 0 0
0 0 6 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
从上面我们，5*9的数组中，我们内容只有1,4,6，其他的都没有使用到，浪费了大部分的内存空间，我们如果使用稀疏数组表示
5 9 3 //5表示数组有5行，9表示数组有9列，3表示数组中有三个非0数据
1 1 1 //1表示第一行 1 表示第一列 1表示元素1
3 1 4 //3表示第三行 1 表示第一列 4表示元素4
5 2 6
SparseArray的特点：
- SparseArray是一个稀疏的数组
- SparseArray的key只能是int类型,避免了key的装箱拆箱的操作，提升了性能
- SparseArray的key的查找使用了二分的查找方式，故key是一个有序的数组
- SparseArray的删除是一个延迟的删除，通过将key的value置为DELECTED，方便后面对该下标的存储的复用
- SparseArray遇到频繁删除，不会触发gc，导致mSize远大于有效数组的长度，造成性能损耗
- SparseArray插入的时候，在不能复用的情况下，需要将该位置及以后的数据先进行copy移位，然后再插入
使用场景：
- key为整型
- 不需要进行频繁的删除
- 元素个数相对较少
源码分析：
private int[] mKeys;
private Object[] mValues;
private int mSize;
private boolean mGarbage = false;
public SparseArray(){
this(10);
}
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;
}
构造函数，默认的数组的长度为10，mSize数组中的元素为0。
mKeys：0 0 0 0 0 0 0 0 0 0
mValues：null null null null null null null null null null
现向当前数组中插入一个Person
public void put(int key,E value){
//第一步通过key获取当前key所在的位置，使用的是二分查找
int pos = ContainerHelper.binarySearch(mKeys,mSize,key);
if(pos >=0){//找到了对应的位置,直接覆盖
mValues[pos] = value;
}else{//不存在
pos = ~pos; //即将要插入的位置
if(pos < mSize && mValues[pos] == DELETED){//可以复用该位置
mKeys[pos] = pos;
mValues[pos] = value;
mSize++;
return;
}
if（mGarbage && mSize>=mKeys.length()）{//需要回收，且mSize超出了mkeys的长度
//回收
gc();
//重新获取回收后，key的位置
pos = ContainerHelper.binarySearch(mKeys,mSize,key);
}
//进行插入操作
mKeys = GrowingArrayUtils.insert(mKeys,mSize,pos,key)
mValues = GrowingArrayUtils.insert(mValues,mSize,pos,value)
mSize++;
}
}
二分查找
public static int binarySearch(int[] mKeys,int mSize,int key){
int low = 0;
int high = mSize-1;
while(low<=high){
int mid = (low+high)>>>2; //无符号右移1位及(除2)
int midValue = mKeys[mid];
if(midValue < key){
low = mid+1;
}else if(midValue > key){
high = mid-1;
}else{
return mid;
}
}
return ~low;
}
该二分查找方法，如果mkeys中存在key，则返回该key所在的位置下标，如果不存在则返回即将要插入的位置的坐标的反码。
回收
public void gc(){
int[] tempKeys = mKeys;
Object[] tempValues = mValues;
int n = mSize;
int avaliableSize = 0;
for(int i =0;i<n;i++){
Object value = tempValues[i];
if(value != DELETED){
if(i != avaliable){
tempValues[avaliableSize] = value
tempKeys[avaliableSize] = tempKeys[i]
tempValues[i] = null
}
avaliableSize++;
}
}
mGarbage = false;
mSize = avaliableSize;
}
回收数组中的DELETED的数值
原始数组mKeys：[5,6,7,8,9]
原始数组mValues:[6,DELETED,DELETED,9,10]
mSize = 5
gc()过后的数组
数组mKeys:[5,8,9,8,9]
数组mValues:[6,9,10,null,null]
mSize = 3
插入数据（1.判断是否需要扩容，如果先进行扩容 2.数据的拷贝后移 3，插入数据）
public Object[] insert(Object[] array,int mCurrentSize,int pos,Object value){
if(mCurrentSize+1<=array.length()){//容量够了，不需要进行扩容
//先进行数据的copy后移
System.arrayCopy(array,pos,array,pos+1,mCurrentSize-pos);
//插入数据
array[pos] = value
return array;
}else{//数组容量不够
Object[] newArray = ArrayUtils.newUnpaddedArray(getSize(mCurrentSize))
//先拷贝前面的数据
System.arrayCopy(array,0,newArray,0,pos);
//插入数据
newArray[pos] = value;
//拷贝后面的数据
System.arrayCopy(array,pos,newArray,pos+1,mSize-pos);
return newArray;
}
}
public int getSize(int mCurrentSize){
return mCurrentSize<=4?8:mCurrentSize*2;
}
插入数据的数组变化：
原始数组
mKeys：0 0 0 0 0 0 0 0 0 0
mValues：null null null null null null null null null null
mSize = 0
现在调用方法:put(3,perosn1)
通过二分查找返回的pos = -1
故直接插入到0位置
插入后数组：
mKeys：3 0 0 0 0 0 0 0 0 0
mValues：person1 null null null null null null null null null
mSize = 1
现在调用方法:put(7,perosn2)
通过二分查找返回的pos = -2
故直接插入到1位置
插入后数组：
mKeys：3 7 0 0 0 0 0 0 0 0
mValues：person1 perosn2 null null null null null null null null
mSize = 2
现在调用方法:put(5,perosn3)
通过二分查找返回的pos = -2
故先将1位置及以后的后移，再在1位置插入person3
插入后数组：
mKeys：3 5 7 0 0 0 0 0 0 0
mValues：person1 perosn3 perosn3 null null null null null null null
mSize = 3
删除操作
public void delete(int key){
int pos = ContainerHelper.binarySearch(mkeys,mSize,key);
if(pos >=0){
mValues[pos] = DELETED;
mGarbage = true;
}
}
