注意：SparseArray<Object>對(duì)應(yīng)的是HashMap<Integer,Object>官还，如果是HashMap<String,Object>等則無(wú)法代替穴张；SparseArray只能優(yōu)化內(nèi)存（意譯即為稀疏數(shù)組）鲁猩，并不能優(yōu)化存取速度腾供；采用二分查找來(lái)查找key，會(huì)頻繁的插入遮怜、刪除實(shí)體（entry）到數(shù)組里淋袖，所以比起Hashmap速度并沒(méi)有明顯提升；
HashMap是java里比較常用的一個(gè)集合類(lèi)锯梁，我比較習(xí)慣用來(lái)緩存一些處理后的結(jié)果适贸。最近在做一個(gè)Android項(xiàng)目，在代碼中定義這樣一個(gè)變量涝桅，實(shí)例化時(shí)拜姿，Eclipse卻給出了一個(gè) performance 警告。
意思就是說(shuō)用SparseArray 來(lái)替代冯遂，以獲取更好性能蕊肥。老實(shí)說(shuō)，對(duì)SparseArray并不熟悉蛤肌，第一感覺(jué)應(yīng)該是Android提供的一個(gè)類(lèi)壁却。按住Ctrl點(diǎn)擊進(jìn)入SparseArray的源碼，果不其然裸准，確定是Android提供的一個(gè)工具類(lèi)展东。
單純從字面上來(lái)理解，SparseArray指的是稀疏數(shù)組(Sparse array)炒俱，所謂稀疏數(shù)組就是數(shù)組中大部分的內(nèi)容值都未被使用（或都為零）盐肃，在數(shù)組中僅有少部分的空間使用。因此造成內(nèi)存空間的浪費(fèi)权悟，為了節(jié)省內(nèi)存空間砸王，并且不影響數(shù)組中原有的內(nèi)容值，我們可以采用一種壓縮的方式來(lái)表示稀疏數(shù)組的內(nèi)容峦阁。
假設(shè)有一個(gè)9*7的數(shù)組谦铃，其內(nèi)容如下：
在此數(shù)組中，共有63個(gè)空間榔昔，但卻只使用了5個(gè)元素驹闰，造成58個(gè)元素空間的浪費(fèi)瘪菌。以下我們就使用稀疏數(shù)組重新來(lái)定義這個(gè)數(shù)組：
其中在稀疏數(shù)組中第一部分所記錄的是原數(shù)組的列數(shù)和行數(shù)以及元素使用的個(gè)數(shù)、第二部分所記錄的是原數(shù)組中元素的位置和內(nèi)容嘹朗。經(jīng)過(guò)壓縮之后师妙，原來(lái)需要聲明大小為63的數(shù)組，而使用壓縮后骡显，只需要聲明大小為6*3的數(shù)組，僅需18個(gè)存儲(chǔ)空間曾掂。
繼續(xù)閱讀SparseArray的源碼惫谤，從構(gòu)造方法我們可以看出，它和一般的List一樣珠洗，可以預(yù)先設(shè)置容器大小溜歪，默認(rèn)的大小是10：
publicSparseArray(){
this(10);
}
publicSparseArray(intinitialCapacity){
initialCapacity=ArrayUtils.idealIntArraySize(initialCapacity);
mKeys=newint[initialCapacity];
mValues=newObject[initialCapacity];
mSize=0;
}
再來(lái)看看它對(duì)數(shù)據(jù)的”增刪改查”。
它有兩個(gè)方法可以添加鍵值對(duì)：
publicvoidput(intkey,E value){}
publicvoidappend(intkey,E value){}
有四個(gè)方法可以執(zhí)行刪除操作:
publicvoiddelete(intkey){}
publicvoidremove(intkey){}//直接調(diào)用的delete(int key)
publicvoidremoveAt(intindex){}
publicvoidclear(){}
修改數(shù)據(jù)起初以為只有setValueAt(int index, E value)可以修改數(shù)據(jù)许蓖，但后來(lái)發(fā)現(xiàn)put(int key, E value)也可以修改數(shù)據(jù)蝴猪，我們查看put(int key, E value)的源碼可知，在put數(shù)據(jù)之前膊爪，會(huì)先查找要put的數(shù)據(jù)是否已經(jīng)存在自阱，如果存在就是修改，不存在就添加米酬。
publicvoidput(intkey,E value){
inti=binarySearch(mKeys,0,mSize,key);
if(i>=0){
mValues[i]=value;
}else{
i=~i;
if(i
mKeys[i]=key;
mValues[i]=value;
return;
}
if(mGarbage&&mSize>=mKeys.length){
gc();
// Search again because indices may have changed.
i=~binarySearch(mKeys,0,mSize,key);
}
…………
所以沛豌，修改數(shù)據(jù)實(shí)際也有兩種方法：
publicvoidput(intkey,E value)
publicvoidsetValueAt(intindex,E value)
最后再來(lái)看看如何查找數(shù)據(jù)。有兩個(gè)方法可以查詢(xún)?nèi)≈担?/p>
publicEget(intkey)
publicEget(intkey,E valueIfKeyNotFound)
其中g(shù)et(int key)也只是調(diào)用了 get(int key,E valueIfKeyNotFound),最后一個(gè)從傳參的變量名就能看出赃额，傳入的是找不到的時(shí)候返回的值.get(int key)當(dāng)找不到的時(shí)候加派，默認(rèn)返回null。
查看第幾個(gè)位置的鍵：public int keyAt(int index)
有一點(diǎn)需要注意的是跳芳，查看鍵所在位置芍锦，由于是采用二分法查找鍵的位置，所以找不到時(shí)返回小于0的數(shù)值飞盆，而不是返回-1娄琉。返回的負(fù)值是表示它在找不到時(shí)所在的位置。
查看第幾個(gè)位置的值：
public E valueAt(int index)
查看值所在位置吓歇，沒(méi)有的話(huà)返回-1：
public int indexOfValue(E value)
最后车胡，發(fā)現(xiàn)其核心就是折半查找函數(shù)（binarySearch），算法設(shè)計(jì)的很不錯(cuò)照瘾。
privatestaticintbinarySearch(int[]a,intstart,intlen,intkey){
inthigh=start+len,low=start-1,guess;
while(high-low>1){
guess=(high+low)/2;
if(a[guess]
low=guess;
else
high=guess;
}
if(high==start+len)
return~(start+len);
elseif(a[high]==key)
returnhigh;
else
return~high;
}
相應(yīng)的也有SparseBooleanArray匈棘，用來(lái)取代HashMap ，SparseIntArray用來(lái)取代HashMap 析命，大家有興趣的可以研究主卫。
總結(jié)：
SparseArray是android里為這樣的Hashmap而專(zhuān)門(mén)寫(xiě)的類(lèi),目的是提高效率逃默，其核心是折半查找函數(shù)（binarySearch）。在Android中簇搅，當(dāng)我們需要定義
HashMap hashMap = new HashMap ();
時(shí)完域，我們可以使用如下的方式來(lái)取得更好的性能.
SparseArray sparseArray = new SparseArray ();
https://liuzhichao.com/p/832.html
