SparseArray是Android框架獨(dú)有的類胯甩。是Google官方推薦當(dāng)key為整形的時(shí)候，（key堪嫂，value）的形式偎箫，替代HashMap的一種存儲(chǔ)結(jié)構(gòu)，使用SparseArray可以避免java的自動(dòng)裝箱皆串，拆箱的過程淹办，而且相比較HashMap，Sparse更節(jié)省內(nèi)存恶复。
我們?cè)谑褂靡环N數(shù)據(jù)結(jié)構(gòu)的時(shí)候會(huì)關(guān)注怜森，這種結(jié)構(gòu)的效率速挑，包括時(shí)間和空間兩點(diǎn)。實(shí)際測(cè)試了一下副硅。
正向插入時(shí)
long btimeSp=System.currentTimeMillis();
SparseArray sparse=new SparseArray();
for(int i=0;i<100000;i++){
sparse.put(i,i);
}
long ftimeSp=System.currentTimeMillis()-btimeSp;
long btimeHash=System.currentTimeMillis();
HashMap hash=new HashMap();
for(int i=0;i<100000;i++){
hash.put(i,i);
}
long ftimeHa=System.currentTimeMillis()-btimeHash;
正向插入100 000條 Sparse: 17ms Hash: 44ms
正向插入的時(shí)候姥宝，SparseArray相比較HashMap要快一倍以上。
反向插入時(shí)
long btimeSp=System.currentTimeMillis();
SparseArray sparse=new SparseArray();
for(int i=100000;i>0;i--){
sparse.put(i,i);
}
long ftimeSp=System.currentTimeMillis()-btimeSp;
long btimeHa=System.currentTimeMillis();
HashMap hash=new HashMap();
for(int i=100000;i>0;i--){
hash.put(i,i);
}
long ftimeHa=System.currentTimeMillis()-btimeHa;
反向插入100 000條 Sparse: 6561ms Hash: 42ms
可見反向插入的時(shí)候在數(shù)據(jù)量到達(dá)10 0000級(jí)別的時(shí)候恐疲，SparseArray比正向插入要慢百倍以上（SparseArray在android性能優(yōu)化典范中說到適合數(shù)量級(jí)在千以內(nèi)）
但如果反向插入1 0000的時(shí)候占用內(nèi)存 SparseArray和HashMap 10 0000條的時(shí)候Sparse: 82ms Hash: 6ms腊满，這時(shí)就到了相差了10倍左，1000的時(shí)候就比較相近了（注意這里我們看的是SparseArray在最差的情況下）
這樣可以看出SparseArray的插入效率并不是很穩(wěn)定,至于其中的原因可以在源碼中找到培己。
public void put(int key, E value) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
...
}
static int binarySearch(int[] array, int size, int value) {
int lo = 0;
int hi = size - 1;
while (lo <= hi) {
final int mid = (lo + hi) >>> 1;
final int midVal = array[mid];
if (midVal < value) {
lo = mid + 1;
} else if (midVal > value) {
hi = mid - 1;
} else {
return mid; // value found
}
}
return ~lo; // value not present
}
put添加數(shù)據(jù)的時(shí)候碳蛋，會(huì)使用二分查找法和之前的key比較當(dāng)前我們添加的元素的key的大小，然后按照從小到大的順序排列好漱凝，SparseArray通過Key值的大小維持了一個(gè)有序的數(shù)組疮蹦。
Sparse: 3.52M Hash: 8.14M
我們已經(jīng)看到了相比較HashMap SparseMap的優(yōu)勢(shì)是更節(jié)省內(nèi)存诸迟，時(shí)間效率上SparseMap沒有HashMap穩(wěn)定茸炒，但相對(duì)Android對(duì)于內(nèi)存更加敏感，使用SparseArray顯然更加合適阵苇，SparseArray是時(shí)間和空間的一個(gè)折中壁公，而且我們測(cè)試的是在10 0000這個(gè)數(shù)量級(jí)（而且是最差的情況），在數(shù)量級(jí)較大的時(shí)候绅项，不停地插入數(shù)據(jù)紊册，由于存儲(chǔ)數(shù)據(jù)的是數(shù)組，這樣會(huì)創(chuàng)建新的數(shù)組快耿，數(shù)據(jù)量較大的時(shí)候每次創(chuàng)建與復(fù)制的過程都很耗時(shí)囊陡，SparseArray會(huì)在index超出的時(shí)候重新創(chuàng)建一個(gè)長度是原來二倍的數(shù)組（SparseArray 的key和value是用兩個(gè)數(shù)組存儲(chǔ)）
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value)
GrowingArrayUtils的insert
public static int[] insert(int[] array, int currentSize, int index, int element) {
assert currentSize <= array.length;
if (currentSize + 1 <= array.length) {
System.arraycopy(array, index, array, index + 1, currentSize - index);
array[index] = element;
return array;
}
int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize));
System.arraycopy(array, 0, newArray, 0, index);
newArray[index] = element;
System.arraycopy(array, index, newArray, index + 1, array.length - index);
return newArray;
}
增長長度
public static int growSize(int currentSize) {
return currentSize <= 4 ? 8 : currentSize * 2;
}
這里我們看到了插入數(shù)據(jù)時(shí)的移位的過程，而且超出數(shù)組界限會(huì)創(chuàng)建一個(gè)長度為原來2倍的數(shù)組掀亥，數(shù)據(jù)量越大put時(shí)需要移位的數(shù)據(jù)就越多撞反，這也是我們不希望看到的，這也就是推薦使用數(shù)量級(jí)在千以內(nèi)的原因搪花。但如果在千數(shù)量級(jí)內(nèi)遏片，SparseArray的性能顯然要好很多，查找的過程是二分法查找撮竿，效率也相當(dāng)?shù)牟诲e(cuò)吮便，內(nèi)存比HashMap至少節(jié)省一半。SparseArray還避免了java的自動(dòng)裝箱的行為幢踏，key和value分別使用兩個(gè)數(shù)組存儲(chǔ)key直接存儲(chǔ)的是int髓需，對(duì)于HashMap，我們?cè)趐ut的時(shí)候就執(zhí)行了裝箱房蝉。
我們傳入的是int授账，但這里會(huì)裝箱為Integer枯跑，當(dāng)我們?nèi)≈档臅r(shí)候執(zhí)行的是 i.intValue()，對(duì)于HashMap又會(huì)將<Key白热，Value>封裝成為HashMapEntry敛助，int占用 4個(gè)字節(jié)，對(duì)于Integer占用的字節(jié)數(shù)屋确，至少包含實(shí)例數(shù)據(jù)和指向類數(shù)據(jù)的指針纳击，實(shí)例數(shù)據(jù)是int占用4字節(jié)，指向類數(shù)據(jù)的指針占用4字節(jié)攻臀，Integer至少包含8字節(jié)焕数。
總結(jié)：
1.SparseArray只能在key為int時(shí)替換HashMap。
2.SparseArray不適用于數(shù)量級(jí)過大的存儲(chǔ)刨啸，通常在千級(jí)以內(nèi)堡赔。
3.SparseArray效率比較HashMap不是很穩(wěn)定，數(shù)量級(jí)較小效率較高设联，但比較HashMap更節(jié)省內(nèi)存善已。
還有兩個(gè)類SparseBooleanArray和SparseIntArray分別對(duì)應(yīng)的是特定 int -> boolean ，int -> int
對(duì)于key值比較大的可以使用LongSparseArray
