SparseArray分析
SparseArray是一個(gè)稀疏數(shù)組醋虏，所謂稀疏數(shù)組就是指數(shù)組中的大部分內(nèi)容值未被使用（或者為零），只有很少部分的空間被使用。因此造成了內(nèi)存空間的浪費(fèi)，為了節(jié)省內(nèi)存空間扩淀，并且不影響數(shù)組中的原始內(nèi)容值，我們可以采用一種壓縮的方式來表示數(shù)組的內(nèi)容啤挎。故稀疏數(shù)組我們可以看做是普通數(shù)組的壓縮驻谆。
例如：
我們有一個(gè)5*9的數(shù)組，普通數(shù)組的表示如下
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的數(shù)組中胜臊，我們內(nèi)容只有1,4,6，其他的都沒有使用到伙判，浪費(fèi)了大部分的內(nèi)存空間象对，我們?nèi)绻褂孟∈钄?shù)組表示
5 9 3 //5表示數(shù)組有5行，9表示數(shù)組有9列宴抚，3表示數(shù)組中有三個(gè)非0數(shù)據(jù)
1 1 1 //1表示第一行 1 表示第一列 1表示元素1
3 1 4 //3表示第三行 1 表示第一列 4表示元素4
5 2 6
SparseArray的特點(diǎn)：
- SparseArray是一個(gè)稀疏的數(shù)組
- SparseArray的key只能是int類型,避免了key的裝箱拆箱的操作勒魔，提升了性能
- SparseArray的key的查找使用了二分的查找方式甫煞，故key是一個(gè)有序的數(shù)組
- SparseArray的刪除是一個(gè)延遲的刪除，通過將key的value置為DELECTED冠绢，方便后面對(duì)該下標(biāo)的存儲(chǔ)的復(fù)用
- SparseArray遇到頻繁刪除抚吠，不會(huì)觸發(fā)gc，導(dǎo)致mSize遠(yuǎn)大于有效數(shù)組的長度弟胀，造成性能損耗
- SparseArray插入的時(shí)候楷力，在不能復(fù)用的情況下，需要將該位置及以后的數(shù)據(jù)先進(jìn)行copy移位孵户，然后再插入
使用場(chǎng)景：
- key為整型
- 不需要進(jìn)行頻繁的刪除
- 元素個(gè)數(shù)相對(duì)較少
源碼分析：
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;
}
構(gòu)造函數(shù)萧朝，默認(rèn)的數(shù)組的長度為10，mSize數(shù)組中的元素為0夏哭。
mKeys：0 0 0 0 0 0 0 0 0 0
mValues：null null null null null null null null null null
現(xiàn)向當(dāng)前數(shù)組中插入一個(gè)Person
public void put(int key,E value){
//第一步通過key獲取當(dāng)前key所在的位置剪勿，使用的是二分查找
int pos = ContainerHelper.binarySearch(mKeys,mSize,key);
if(pos >=0){//找到了對(duì)應(yīng)的位置,直接覆蓋
mValues[pos] = value;
}else{//不存在
pos = ~pos; //即將要插入的位置
if(pos < mSize && mValues[pos] == DELETED){//可以復(fù)用該位置
mKeys[pos] = pos;
mValues[pos] = value;
mSize++;
return;
}
if（mGarbage && mSize>=mKeys.length()）{//需要回收，且mSize超出了mkeys的長度
//回收
gc();
//重新獲取回收后方庭，key的位置
pos = ContainerHelper.binarySearch(mKeys,mSize,key);
}
//進(jìn)行插入操作
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; //無符號(hào)右移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所在的位置下標(biāo)械念，如果不存在則返回即將要插入的位置的坐標(biāo)的反碼。
回收
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;
}
回收數(shù)組中的DELETED的數(shù)值
原始數(shù)組mKeys：[5,6,7,8,9]
原始數(shù)組mValues:[6,DELETED,DELETED,9,10]
mSize = 5
gc()過后的數(shù)組
數(shù)組mKeys:[5,8,9,8,9]
數(shù)組mValues:[6,9,10,null,null]
mSize = 3
插入數(shù)據(jù)（1.判斷是否需要擴(kuò)容运悲，如果先進(jìn)行擴(kuò)容 2.數(shù)據(jù)的拷貝后移 3龄减，插入數(shù)據(jù)）
public Object[] insert(Object[] array,int mCurrentSize,int pos,Object value){
if(mCurrentSize+1<=array.length()){//容量夠了，不需要進(jìn)行擴(kuò)容
//先進(jìn)行數(shù)據(jù)的copy后移
System.arrayCopy(array,pos,array,pos+1,mCurrentSize-pos);
//插入數(shù)據(jù)
array[pos] = value
return array;
}else{//數(shù)組容量不夠
Object[] newArray = ArrayUtils.newUnpaddedArray(getSize(mCurrentSize))
//先拷貝前面的數(shù)據(jù)
System.arrayCopy(array,0,newArray,0,pos);
//插入數(shù)據(jù)
newArray[pos] = value;
//拷貝后面的數(shù)據(jù)
System.arrayCopy(array,pos,newArray,pos+1,mSize-pos);
return newArray;
}
}
public int getSize(int mCurrentSize){
return mCurrentSize<=4?8:mCurrentSize*2;
}
插入數(shù)據(jù)的數(shù)組變化：
原始數(shù)組
mKeys：0 0 0 0 0 0 0 0 0 0
mValues：null null null null null null null null null null
mSize = 0
現(xiàn)在調(diào)用方法:put(3,perosn1)
通過二分查找返回的pos = -1
故直接插入到0位置
插入后數(shù)組：
mKeys：3 0 0 0 0 0 0 0 0 0
mValues：person1 null null null null null null null null null
mSize = 1
現(xiàn)在調(diào)用方法:put(7,perosn2)
通過二分查找返回的pos = -2
故直接插入到1位置
插入后數(shù)組：
mKeys：3 7 0 0 0 0 0 0 0 0
mValues：person1 perosn2 null null null null null null null null
mSize = 2
現(xiàn)在調(diào)用方法:put(5,perosn3)
通過二分查找返回的pos = -2
故先將1位置及以后的后移班眯，再在1位置插入person3
插入后數(shù)組：
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;
}
}
