深入分析Android系统中SparseArray的源码
前言
昨晚想在Android应用中增加一个int映射到String的字典表，使用HashMap实现的时候，Eclipse给出了一个警告，昨晚项目上线紧张，我直接给忽略了，今天看了一下具体的Eclipse提示如下：
UsenewSparseArray<String>(...)insteadforbetterperformance
这个警告的意思是使用SparseArray来替代，以获取更好的性能。
源码
因为SparseArray整体代码比较简单，先把源码展示出来，然后再分析为什么使用SparseArray会比使用HashMap有更好的性能。
publicclassSparseArray<E>implementsCloneable{
privatestaticfinalObjectDELETED=newObject();
privatebooleanmGarbage=false;
privateint[]mKeys;
privateObject[]mValues;
privateintmSize;
/**
*CreatesanewSparseArraycontainingnomappings.
*/
publicSparseArray(){
this(10);
}
/**
*CreatesanewSparseArraycontainingnomappingsthatwillnot
*requireanyadditionalmemoryallocationtostorethespecified
*numberofmappings.Ifyousupplyaninitialcapacityof0,the
*sparsearraywillbeinitializedwithalight-weightrepresentation
*notrequiringanyadditionalarrayallocations.
*/
publicSparseArray(intinitialCapacity){
if(initialCapacity==0){
mKeys=ContainerHelpers.EMPTY_INTS;
mValues=ContainerHelpers.EMPTY_OBJECTS;
}else{
initialCapacity=ArrayUtils.idealIntArraySize(initialCapacity);
mKeys=newint[initialCapacity];
mValues=newObject[initialCapacity];
}
mSize=0;
}
@Override
@SuppressWarnings("unchecked")
publicSparseArray<E>clone(){
SparseArray<E>clone=null;
try{
clone=(SparseArray<E>)super.clone();
clone.mKeys=mKeys.clone();
clone.mValues=mValues.clone();
}catch(CloneNotSupportedExceptioncnse){
/*ignore*/
}
returnclone;
}
/**
*GetstheObjectmappedfromthespecifiedkey,or<code>null</code>
*ifnosuchmappinghasbeenmade.
*/
publicEget(intkey){
returnget(key,null);
}
/**
*GetstheObjectmappedfromthespecifiedkey,orthespecifiedObject
*ifnosuchmappinghasbeenmade.
*/
@SuppressWarnings("unchecked")
publicEget(intkey,EvalueIfKeyNotFound){
inti=ContainerHelpers.binarySearch(mKeys,mSize,key);
if(i<0||mValues[i]==DELETED){
returnvalueIfKeyNotFound;
}else{
return(E)mValues[i];
}
}
/**
*Removesthemappingfromthespecifiedkey,iftherewasany.
*/
publicvoiddelete(intkey){
inti=ContainerHelpers.binarySearch(mKeys,mSize,key);
if(i>=0){
if(mValues[i]!=DELETED){
mValues[i]=DELETED;
mGarbage=true;
}
}
}
/**
*Aliasfor{@link#delete(int)}.
*/
publicvoidremove(intkey){
delete(key);
}
/**
*Removesthemappingatthespecifiedindex.
*/
publicvoidremoveAt(intindex){
if(mValues[index]!=DELETED){
mValues[index]=DELETED;
mGarbage=true;
}
}
/**
*Removearangeofmappingsasabatch.
*
*@paramindexIndextobeginat
*@paramsizeNumberofmappingstoremove
*/
publicvoidremoveAtRange(intindex,intsize){
finalintend=Math.min(mSize,index+size);
for(inti=index;i<end;i++){
removeAt(i);
}
}
privatevoidgc(){
//Log.e("SparseArray","gcstartwith"+mSize);
intn=mSize;
into=0;
int[]keys=mKeys;
Object[]values=mValues;
for(inti=0;i<n;i++){
Objectval=values[i];
if(val!=DELETED){
if(i!=o){
keys[o]=keys[i];
values[o]=val;
values[i]=null;
}
o++;
}
}
mGarbage=false;
mSize=o;
//Log.e("SparseArray","gcendwith"+mSize);
}
/**
*Addsamappingfromthespecifiedkeytothespecifiedvalue,
*replacingthepreviousmappingfromthespecifiedkeyifthere
*wasone.
*/
publicvoidput(intkey,Evalue){
inti=ContainerHelpers.binarySearch(mKeys,mSize,key);
if(i>=0){
mValues[i]=value;
}else{
i=~i;
if(i<mSize&&mValues[i]==DELETED){
mKeys[i]=key;
mValues[i]=value;
return;
}
if(mGarbage&&mSize>=mKeys.length){
gc();
//Searchagainbecauseindicesmayhavechanged.
i=~ContainerHelpers.binarySearch(mKeys,mSize,key);
}
if(mSize>=mKeys.length){
intn=ArrayUtils.idealIntArraySize(mSize+1);
int[]nkeys=newint[n];
Object[]nvalues=newObject[n];
//Log.e("SparseArray","grow"+mKeys.length+"to"+n);
System.arraycopy(mKeys,0,nkeys,0,mKeys.length);
System.arraycopy(mValues,0,nvalues,0,mValues.length);
mKeys=nkeys;
mValues=nvalues;
}
if(mSize-i!=0){
//Log.e("SparseArray","move"+(mSize-i));
System.arraycopy(mKeys,i,mKeys,i+1,mSize-i);
System.arraycopy(mValues,i,mValues,i+1,mSize-i);
}
mKeys[i]=key;
mValues[i]=value;
mSize++;
}
}
/**
*Returnsthenumberofkey-valuemappingsthatthisSparseArray
*currentlystores.
*/
publicintsize(){
if(mGarbage){
gc();
}
returnmSize;
}
/**
*Givenanindexintherange<code>0...size()-1</code>,returns
*thekeyfromthe<code>index</code>thkey-valuemappingthatthis
*SparseArraystores.
*
*<p>Thekeyscorrespondingtoindicesinascendingorderareguaranteedto
*beinascendingorder,e.g.,<code>keyAt(0)</code>willreturnthe
*smallestkeyand<code>keyAt(size()-1)</code>willreturnthelargest
*key.</p>
*/
publicintkeyAt(intindex){
if(mGarbage){
gc();
}
returnmKeys[index];
}
/**
*Givenanindexintherange<code>0...size()-1</code>,returns
*thevaluefromthe<code>index</code>thkey-valuemappingthatthis
*SparseArraystores.
*
*<p>Thevaluescorrespondingtoindicesinascendingorderareguaranteed
*tobeassociatedwithkeysinascendingorder,e.g.,
*<code>valueAt(0)</code>willreturnthevalueassociatedwiththe
*smallestkeyand<code>valueAt(size()-1)</code>willreturnthevalue
*associatedwiththelargestkey.</p>
*/
@SuppressWarnings("unchecked")
publicEvalueAt(intindex){
if(mGarbage){
gc();
}
return(E)mValues[index];
}
/**
*Givenanindexintherange<code>0...size()-1</code>,setsanew
*valueforthe<code>index</code>thkey-valuemappingthatthis
*SparseArraystores.
*/
publicvoidsetValueAt(intindex,Evalue){
if(mGarbage){
gc();
}
mValues[index]=value;
}
/**
*Returnstheindexforwhich{@link#keyAt}wouldreturnthe
*specifiedkey,oranegativenumberifthespecified
*keyisnotmapped.
*/
publicintindexOfKey(intkey){
if(mGarbage){
gc();
}
returnContainerHelpers.binarySearch(mKeys,mSize,key);
}
/**
*Returnsanindexforwhich{@link#valueAt}wouldreturnthe
*specifiedkey,oranegativenumberifnokeysmaptothe
*specifiedvalue.
*<p>Bewarethatthisisalinearsearch,unlikelookupsbykey,
*andthatmultiplekeyscanmaptothesamevalueandthiswill
*findonlyoneofthem.
*<p>Notealsothatunlikemostcollections'{@codeindexOf}methods,
*thismethodcomparesvaluesusing{@code==}ratherthan{@codeequals}.
*/
publicintindexOfValue(Evalue){
if(mGarbage){
gc();
}
for(inti=0;i<mSize;i++)
if(mValues[i]==value)
returni;
return-1;
}
/**
*Removesallkey-valuemappingsfromthisSparseArray.
*/
publicvoidclear(){
intn=mSize;
Object[]values=mValues;
for(inti=0;i<n;i++){
values[i]=null;
}
mSize=0;
mGarbage=false;
}
/**
*Putsakey/valuepairintothearray,optimizingforthecasewhere
*thekeyisgreaterthanallexistingkeysinthearray.
*/
publicvoidappend(intkey,Evalue){
if(mSize!=0&&key<=mKeys[mSize-1]){
put(key,value);
return;
}
if(mGarbage&&mSize>=mKeys.length){
gc();
}
intpos=mSize;
if(pos>=mKeys.length){
intn=ArrayUtils.idealIntArraySize(pos+1);
int[]nkeys=newint[n];
Object[]nvalues=newObject[n];
//Log.e("SparseArray","grow"+mKeys.length+"to"+n);
System.arraycopy(mKeys,0,nkeys,0,mKeys.length);
System.arraycopy(mValues,0,nvalues,0,mValues.length);
mKeys=nkeys;
mValues=nvalues;
}
mKeys[pos]=key;
mValues[pos]=value;
mSize=pos+1;
}
/**
*{@inheritDoc}
*
*<p>Thisimplementationcomposesastringbyiteratingoveritsmappings.If
*thismapcontainsitselfasavalue,thestring"(thisMap)"
*willappearinitsplace.
*/
@Override
publicStringtoString(){
if(size()<=0){
return"{}";
}
StringBuilderbuffer=newStringBuilder(mSize*28);
buffer.append('{');
for(inti=0;i<mSize;i++){
if(i>0){
buffer.append(",");
}
intkey=keyAt(i);
buffer.append(key);
buffer.append('=');
Objectvalue=valueAt(i);
if(value!=this){
buffer.append(value);
}else{
buffer.append("(thisMap)");
}
}
buffer.append('}');
returnbuffer.toString();
}
}
首先，看一下SparseArray的构造函数：
/**
*CreatesanewSparseArraycontainingnomappings.
*/
publicSparseArray(){
this(10);
}
/**
*CreatesanewSparseArraycontainingnomappingsthatwillnot
*requireanyadditionalmemoryallocationtostorethespecified
*numberofmappings.Ifyousupplyaninitialcapacityof0,the
*sparsearraywillbeinitializedwithalight-weightrepresentation
*notrequiringanyadditionalarrayallocations.
*/
publicSparseArray(intinitialCapacity){
if(initialCapacity==0){
mKeys=ContainerHelpers.EMPTY_INTS;
mValues=ContainerHelpers.EMPTY_OBJECTS;
}else{
initialCapacity=ArrayUtils.idealIntArraySize(initialCapacity);
mKeys=newint[initialCapacity];
mValues=newObject[initialCapacity];
}
mSize=0;
}
从构造方法可以看出，这里也是预先设置了容器的大小，默认大小为10。
再来看一下添加数据操作：
/**
*Addsamappingfromthespecifiedkeytothespecifiedvalue,
*replacingthepreviousmappingfromthespecifiedkeyifthere
*wasone.
*/
publicvoidput(intkey,Evalue){
inti=ContainerHelpers.binarySearch(mKeys,mSize,key);
if(i>=0){
mValues[i]=value;
}else{
i=~i;
if(i<mSize&&mValues[i]==DELETED){
mKeys[i]=key;
mValues[i]=value;
return;
}
if(mGarbage&&mSize>=mKeys.length){
gc();
//Searchagainbecauseindicesmayhavechanged.
i=~ContainerHelpers.binarySearch(mKeys,mSize,key);
}
if(mSize>=mKeys.length){
intn=ArrayUtils.idealIntArraySize(mSize+1);
int[]nkeys=newint[n];
Object[]nvalues=newObject[n];
//Log.e("SparseArray","grow"+mKeys.length+"to"+n);
System.arraycopy(mKeys,0,nkeys,0,mKeys.length);
System.arraycopy(mValues,0,nvalues,0,mValues.length);
mKeys=nkeys;
mValues=nvalues;
}
if(mSize-i!=0){
//Log.e("SparseArray","move"+(mSize-i));
System.arraycopy(mKeys,i,mKeys,i+1,mSize-i);
System.arraycopy(mValues,i,mValues,i+1,mSize-i);
}
mKeys[i]=key;
mValues[i]=value;
mSize++;
}
}
再看查数据的方法：
/**
*GetstheObjectmappedfromthespecifiedkey,or<code>null</code>
*ifnosuchmappinghasbeenmade.
*/
publicEget(intkey){
returnget(key,null);
}
/**
*GetstheObjectmappedfromthespecifiedkey,orthespecifiedObject
*ifnosuchmappinghasbeenmade.
*/
@SuppressWarnings("unchecked")
publicEget(intkey,EvalueIfKeyNotFound){
inti=ContainerHelpers.binarySearch(mKeys,mSize,key);
if(i<0||mValues[i]==DELETED){
returnvalueIfKeyNotFound;
}else{
return(E)mValues[i];
}
}
可以看到，在put数据和get数据的过程中，都统一调用了一个二分查找算法，其实这也就是SparseArray能够提升效率的核心。
staticintbinarySearch(int[]array,intsize,intvalue){
intlo=0;
inthi=size-1;
while(lo<=hi){
finalintmid=(lo+hi)>>>1;
finalintmidVal=array[mid];
if(midVal<value){
lo=mid+1;
}elseif(midVal>value){
hi=mid-1;
}else{
returnmid;//valuefound
}
}
return~lo;//valuenotpresent
}
个人认为（lo+hi）>>>1的方法有些怪异，直接用lo+(hi-lo)/2更好一些。