SparseArray是Android框架獨(dú)有的類。是Google官方推薦當(dāng)key為整形的時候，（key，value）的形式，替代HashMap的一種存儲結(jié)構(gòu)，使用SparseArray可以避免java的自動裝箱，拆箱的過程，而且相比較HashMap，Sparse更節(jié)省內(nèi)存。
我們在使用一種數(shù)據(jù)結(jié)構(gòu)的時候會關(guān)注，這種結(jié)構(gòu)的效率，包括時間和空間兩點(diǎn)。實(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
正向插入的時候，SparseArray相比較HashMap要快一倍以上。
反向插入時
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ù)據(jù)量到達(dá)10 0000級別的時候，SparseArray比正向插入要慢百倍以上（SparseArray在android性能優(yōu)化典范中說到適合數(shù)量級在千以內(nèi)）
但如果反向插入1 0000的時候占用內(nèi)存 SparseArray和HashMap 10 0000條的時候Sparse: 82ms Hash: 6ms，這時就到了相差了10倍左，1000的時候就比較相近了（注意這里我們看的是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ù)的時候，會使用二分查找法和之前的key比較當(dāng)前我們添加的元素的key的大小，然后按照從小到大的順序排列好，SparseArray通過Key值的大小維持了一個有序的數(shù)組。
Sparse: 3.52M Hash: 8.14M
我們已經(jīng)看到了相比較HashMap SparseMap的優(yōu)勢是更節(jié)省內(nèi)存，時間效率上SparseMap沒有HashMap穩(wěn)定，但相對Android對于內(nèi)存更加敏感，使用SparseArray顯然更加合適，SparseArray是時間和空間的一個折中，而且我們測試的是在10 0000這個數(shù)量級（而且是最差的情況），在數(shù)量級較大的時候，不停地插入數(shù)據(jù)，由于存儲數(shù)據(jù)的是數(shù)組，這樣會創(chuàng)建新的數(shù)組，數(shù)據(jù)量較大的時候每次創(chuàng)建與復(fù)制的過程都很耗時，SparseArray會在index超出的時候重新創(chuàng)建一個長度是原來二倍的數(shù)組（SparseArray 的key和value是用兩個數(shù)組存儲）
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ù)組界限會創(chuàng)建一個長度為原來2倍的數(shù)組，數(shù)據(jù)量越大put時需要移位的數(shù)據(jù)就越多，這也是我們不希望看到的，這也就是推薦使用數(shù)量級在千以內(nèi)的原因。但如果在千數(shù)量級內(nèi)，SparseArray的性能顯然要好很多，查找的過程是二分法查找，效率也相當(dāng)?shù)牟诲e，內(nèi)存比HashMap至少節(jié)省一半。SparseArray還避免了java的自動裝箱的行為，key和value分別使用兩個數(shù)組存儲key直接存儲的是int，對于HashMap，我們在put的時候就執(zhí)行了裝箱。
我們傳入的是int，但這里會裝箱為Integer，當(dāng)我們?nèi)≈档臅r候執(zhí)行的是 i.intValue()，對于HashMap又會將<Key，Value>封裝成為HashMapEntry，int占用 4個字節(jié)，對于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時替換HashMap。
2.SparseArray不適用于數(shù)量級過大的存儲，通常在千級以內(nèi)。
3.SparseArray效率比較HashMap不是很穩(wěn)定，數(shù)量級較小效率較高，但比較HashMap更節(jié)省內(nèi)存。
還有兩個類SparseBooleanArray和SparseIntArray分別對應(yīng)的是特定 int -> boolean ，int -> int
對于key值比較大的可以使用LongSparseArray
