android SparseArray替代HashMap的分析

SparseArray是Android框架獨有的類，在標准的JDK中不存在這個類。它要比 HashMap 節省內存，某些情況下比HashMap性能更好，按照官方問答的解釋，主要是因為SparseArray不需要對key和value進行auto-boxing（將原始類型封裝為對象類型，比如把int類型封裝成Integer類型），結構比HashMap簡單（SparseArray內部主要使用兩個一維數組來保存數據，一個用來存key，一個用來存value）不需要額外的額外的數據結構（主要是針對HashMap中的HashMapEntry而言的）。是騾子是馬得拉出來遛遛，下面我們就通過幾段程序來證明SparseArray在各方面表現如何，下面的試驗結果時在我的Hike X1（Android 4.2.2）手機上運行得出的。

代碼1：

int MAX = 100000;
long start = System.currentTimeMillis();
HashMap hash = new HashMap();
for (int i = 0; i < MAX; i++) {
    hash.put(i, String.valueOf(i));
}
long ts = System.currentTimeMillis() - start;

代碼2：

int MAX = 100000;
long start = System.currentTimeMillis();
SparseArray sparse = new SparseArray();
for (int i = 0; i < MAX; i++) {
    sparse.put(i, String.valueOf(i));
}
long ts = System.currentTimeMillis() - start;

我們分別在long start處和long ts處設置斷點，然後通過DDMS工具查看內存使用情況。

代碼1中，我們使用HashMap來創建100000條數據，開始創建前的系統內存情況為：

創建HashMap之後，應用內存情況為： 可見創建HashMap用去約 13.2M內存。

再看 代碼2，同樣是創建100000條數據，我們用SparseArray來試試，開始創建前的內存使用情況為：

創建SparseArray之後的情況： 創建SparseArray共用去 8.626M內存。<喎?/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+Cr/JvPvKudPDIFNwYXJzZUFycmF5ILXEyLexyCBIYXNoTWFwIL3ayqHE2rTmo6y087jFvdrKoSAzNSXX89PStcTE2rTmoaM8L3A+Cjxocj4KPHA+Cs7Sw8fU2bHIvc/Su8/CsuXI68r9vt21xNCnwsrI57rOo6zO0sPH1Nq808G9ts60+sLro6jW99Kqvs3Kx7DRsuXI68uz0PKx5Lu70rvPwqOstNO087W90KGy5cjro6mjujwvcD4KPHA+CrT6wuszo7o8L3A+Cgo8cHJlIGNsYXNzPQ=="brush:java;">int MAX = 100000; long start = System.currentTimeMillis(); HashMap hash = new HashMap(); for (int i = 0; i < MAX; i++) { hash.put(MAX - i -1, String.valueOf(i)); } long ts = System.currentTimeMillis() - start;

代碼4：

int MAX = 100000;
long start = System.currentTimeMillis();
SparseArray sparse = new SparseArray();
for (int i = 0; i < MAX; i++) {
    sparse.put(MAX - i -1, String.valueOf(i));
}
long ts = System.currentTimeMillis() - start;

我們分別把這4代碼分別運行5次，對比一下ts的時間（單位毫秒）：

# 代碼1 代碼2 代碼3 代碼4 1 10750ms 7429ms 10862ms 90527ms 2 10718ms 7386ms 10711ms 87990ms 3 10816ms 7462ms 11033ms 88259ms 4 10943ms 7386ms 10854ms 88474ms 5 10671ms 7317ms 10786ms 90630ms

通過結果我們看出，在正序插入數據時候，SparseArray比HashMap要快一些；HashMap不管是倒序還是正序開銷幾乎是一樣的；但是SparseArray的倒序插入要比正序插入要慢10倍以上，這時為什麼呢？我們再看下面一段代碼：

代碼5：

SparseArray sparse = new SparseArray(3);

sparse.put(1, "s1");
sparse.put(3, "s3");
sparse.put(2, "s2");

我們在Eclipse的debug模式中，看Variables窗口,如圖：

及時我們是按照1,3,2的順序排列的，但是在SparseArray內部還是按照正序排列的，這時因為SparseArray在檢索數據的時候使用的是二分查找，所以每次插入新數據的時候SparseArray都需要重新排序，所以代碼4中，逆序是最差情況。

---

下面我們在簡單看下檢索情況：

代碼5：

long start4search = System.currentTimeMillis();
for (int i = 0; i < MAX; i++) {
    hash.get(33333); //針對固定值檢索
}
long end4search = System.currentTimeMillis() - start4search;

代碼6:

long start4search = System.currentTimeMillis();
for (int i = 0; i < MAX; i++) {
    hash.get(i); //順序檢索
}
long end4search = System.currentTimeMillis() - start4search;

代碼7:

long start4search = System.currentTimeMillis();
for (int i = 0; i < MAX; i++) {
    sparse.get(33333); //針對固定值檢索
}
long end4search = System.currentTimeMillis() - start4search;

代碼8:

long start4search = System.currentTimeMillis();
for (int i = 0; i < MAX; i++) {
    sparse.get(i); //順序檢索
}
long end4search = System.currentTimeMillis() - start4search;

表1：

# 代碼5 代碼6 代碼7 代碼8 1 4072ms 4318ms 3442ms 3390ms 2 4349ms 4536ms 3402ms 3420ms 3 4599ms 4203ms 3472ms 3376ms 4 4149ms 4086ms 3429ms 3786ms 5 4207ms 4219ms 3439ms 3376ms

代碼9，我們試一些離散的數據。

//使用Foo為了避免由原始類型被自動封裝（auto-boxing，比如把int類型自動轉存Integer對象類型）造成的干擾。
class FOO{
    Integer objKey;
    int intKey;
}
...
int MAX = 100000;

HashMap hash = new HashMap();
SparseArray sparse = new SparseArray();

for (int i = 0; i < MAX; i++) {
    hash.put(i, String.valueOf(i));
    sparse.put(i, String.valueOf(i));
}

List keylist4search = new ArrayList();
for (int i = 0; i < MAX; i++) {
    FOO f = new FOO();
    f.intKey = i;
    f.objKey = Integer.valueOf(i);
    keylist4search.add(f);
}

long start4search = System.currentTimeMillis();
for (int i = 0; i < MAX; i++) {
    hash.get(keylist4search.get(i).objKey);
}
long end4searchHash = System.currentTimeMillis() - start4search;

long start4search2 = System.currentTimeMillis();
for (int i = 0; i < MAX; i++) {
    sparse.get(keylist4search.get(i).intKey);
}
long end4searchSparse = System.currentTimeMillis() - start4search2;

代碼9,運行5次之後的結果如下：

表2:

# end4searchHash end4searchSparse 1 2402ms 4577ms 2 2249ms 4188ms 3 2649ms 4821ms 4 2404ms 4598ms 5 2413ms 4547ms

從上面兩個表中我們可以看出，當SparseArray中存在需要檢索的下標時，SparseArray的性能略勝一籌（表1）。但是當檢索的下標比較離散時，SparseArray需要使用多次二分檢索，性能顯然比hash檢索方式要慢一些了（表2），但是按照官方文檔的說法性能差異不是很大，不超過50%（ For containers holding up to hundreds of items, the performance difference is not significant, less than 50%.）

總體而言，在Android這種內存比CPU更金貴的系統中，能經濟地使用內存還是上策，何況SparseArray在其他方面的表現也不算差（另外，SparseArray刪除數據的時候也做了優化——使用了延遲整理數組的方法，可參考官方文檔SparseArray，讀者可以自行把代碼9中的hash.get和sparse.get改成hash.remove和sparse.delete試試，你會發現二者的性能相差無幾）。而且，使用SparseArray代替HashMap也是官方推薦的做法，在Eclipse中也會提示你優先使用SparseArray，如圖：

另外，我們還可以用 LongSparseArray來替代HashMap。SparseBooleanArray來替代HashMap。