788
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<Integer, String> hash = new HashMap<Integer, String>();
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<String> sparse = new SparseArray<String>();
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內存。
可見使用 SparseArray 的確比 HashMap 節省內存，大概節省 35%左右的內存。
我們再比較一下插入數據的效率如何，我們在加兩段代碼（主要就是把插入順序變換一下，從大到小插入）：
代碼3：
int MAX = 100000;
long start = System.currentTimeMillis();
HashMap<Integer, String> hash = new HashMap<Integer, String>();
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<String> sparse = new SparseArray<String>();
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<String> sparse = new SparseArray<String>(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<Integer, String> hash = new HashMap<Integer, String>();
SparseArray<String> sparse = new SparseArray<String>();
for (int i = 0; i < MAX; i++) {
hash.put(i, String.valueOf(i));
sparse.put(i, String.valueOf(i));
}
List<FOO> keylist4search = new ArrayList<FOO>();
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。
最後更新：2017-04-03 12:55:52
上一篇：
Java運算符
下一篇： 深搜回溯-素數環-1459-jobdu
- Swagger入門教程
- 【文檔】四、Mysql Binlog事件含義詳解
- Maven發布項目
- Android 自定義UI-垂直方向的SeekBar
- ELRepo - Enterprise Linux ???RHEL???CentOS ??? SL??????????????????-??????-????????????-?????????
- Jackson 高性能的JSON處理 android/移動開發必備jackson
- 關於DateTime的轉換
- 架構雲如何改變傳統IT部署需求？
- 並發工具類（三）控製並發線程數的Semaphore
- iPhone與iPad開發實戰——精通iOS開發--視頻