Android應用性能優化之使用SparseArray替代HashMap

一、概述

最近在項目中看到瞭SparseArray，好奇研究瞭下。 SparseArray是Android框架獨有的類，在標準的JDK中不存在這個類。它要比 HashMap 節省內存，某些情況下比HashMap性能更好，按照官方問答的解釋，主要是因為SparseArray不需要對key和value進行auto-boxing（將原始類型封裝為對象類型，比如把int類型封裝成Integer類型），結構比HashMap簡單（SparseArray內部主要使用兩個一維數組來保存數據，一個用來存key，一個用來存value）不需要額外的額外的數據結構（主要是針對HashMap中的HashMapEntry而言的）。

二、詳解

單純從字面上來理解，SparseArray指的是稀疏數組(Sparse array)，所謂稀疏數組就是數組中大部分的內容值都未被使用（或都為零），在數組中僅有少部分的空間使用。因此造成內存空間的浪費，為瞭節省內存空間，並且不影響數組中原有的內容值，我們可以采用一種壓縮的方式來表示稀疏數組的內容。

假設有一個9*7的數組，其內容如下：

在此數組中，共有63個空間，但卻隻使用瞭5個元素，造成58個元素空間的浪費。以下我們就使用稀疏數組重新來定義這個數組：
其中在稀疏數組中第一部分所記錄的是原數組的列數和行數以及元素使用的個數、第二部分所記錄的是原數組中元素的位置和內容。經過壓縮之後，原來需要聲明大小為63的數組，而使用壓縮後，隻需要聲明大小為6*3的數組，僅需18個存儲空間。
光說不行啊，不能你說性能好就性能好，是騾子是馬拉出來溜溜，我們寫兩段測試程序： 代碼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;

上面兩段代碼中，我們分別用HashMap和SpaseArray正序插入100000條數據，數據如下：

#	代碼1	代碼2
時間	10750ms	7429ms
空間	13.2M	8.26M

可見使用 SparseArray 的確比 HashMap 節省內存，大概節省 35%左右的內存。
並且在正序條件下，時間上比HashMap快33%左右。
我們把正序變為反序試試 代碼3：

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;

運行結果如下：

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

通過結果我們看出，在正序插入數據時候，SparseArray比HashMap要快一些；HashMap不管是倒序還是正序開銷幾乎是一樣的；但是SparseArray的倒序插入要比正序插入要慢10倍以上，這時為什麼呢？ 跟進源碼，找到put方法：

public void put(int key, E value) {
        int i = binarySearch(mKeys, 0, 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();

                // Search again because indices may have changed.
                i = ~binarySearch(mKeys, 0, mSize, key);
            }
            …………

在put數據之前，會先查找要put的數據是否已經存在，如果存在就是修改，不存在就添加。其中有個查找的過程，就是binarySearch，這是個什麼鬼啊，跟進去看看：

private static int binarySearch(int[] a, int start, int len, int key) {
        int high = start + len, low = start - 1, guess;

        while (high - low > 1) {
            guess = (high + low) / 2;

            if (a[guess] < key)
                low = guess;
            else
                high = guess;
        }

        if (high == start + len)
            return ~(start + len);
        else if (a[high] == key)
            return high;
        else
            return ~high;
    }

soga，原來是二分查找。那麼原因也就找到瞭，正是因為SparseArray在檢索數據的時候使用的是二分查找，所以每次插入新數據的時候SparseArray都需要重新排序，所以代碼4中，逆序是最差情況。
另外，當SparseArray中存在需要檢索的下標時，SparseArray的性能略勝一籌。但是當檢索的下標比較離散時，SparseArray需要使用多次二分檢索，性能比hash檢索方式要慢一些瞭，但是按照官方文檔的說法性能差異不是很大，不超過50%（ For containers holding up to hundreds of items, the performance difference is not significant, less than 50%.）

三、總結

總體而言，在Android這種內存比CPU更金貴的系統中，能經濟地使用內存還是上策，何況SparseArray在其他方面的表現也不算差（另外，SparseArray刪除數據的時候也做瞭優化——使用瞭延遲整理數組的方法，可參考官方文檔

總結：SparseArray是android裡為這樣的Hashmap而專門寫的類,目的是提高效率，其核心是折半查找函數（binarySearch）。在Android中，當我們需要定義

HashMap hashMap = new HashMap();

時，我們可以使用如下的方式來取得更好的性能.

SparseArray sparseArray = new SparseArray();

參考：

SparseArray
二分查找
稀疏矩陣