學(xué)習(xí)內(nèi)容：
1.Android中SparseArray的使用..
昨天研究完橫向二級(jí)菜單，發(fā)現(xiàn)其中使用了SparseArray去替換HashMap的使用.于是乎自己查了一些相關(guān)資料,自己同時(shí)對(duì)性能進(jìn)行了一些測試。首先先說一下SparseArray的原理.
SparseArray(稀疏數(shù)組).他是Android內(nèi)部特有的api,標(biāo)準(zhǔn)的jdk是沒有這個(gè)類的.在Android內(nèi)部用來替代HashMap<Integer,E>這種形式,使用SparseArray更加節(jié)省內(nèi)存空間的使用,SparseArray也是以key和value對(duì)數(shù)據(jù)進(jìn)行保存的.使用的時(shí)候只需要指定value的類型即可.并且key不需要封裝成對(duì)象類型.
樓主根據(jù)親測,SparseArray存儲(chǔ)數(shù)據(jù)占用的內(nèi)存空間確實(shí)比HashMap要小一些.一會(huì)放出測試的數(shù)據(jù)在進(jìn)行分析矛渴。我們首先看一下二者的結(jié)構(gòu)特性.
HashMap是數(shù)組和鏈表的結(jié)合體,被稱為鏈表散列.
SparseArray是單純數(shù)組的結(jié)合.被稱為稀疏數(shù)組,對(duì)數(shù)據(jù)保存的時(shí)候,不會(huì)有額外的開銷.結(jié)構(gòu)如下：
這就是二者的結(jié)構(gòu),我們需要看一下二者到底有什么差異...
首先是插入：
HashMap的正序插入：
復(fù)制代碼
HashMap<Integer, String>map = new HashMap<Integer, String>();
long start_map = System.currentTimeMillis();
for(int i=0;i<MAX;i++){
map.put(i, String.valueOf(i));
}
long map_memory = Runtime.getRuntime().totalMemory();
long end_map = System.currentTimeMillis()-start_map;
System.out.println("<---Map的插入時(shí)間--->"+end_map+"<---Map占用的內(nèi)存--->"+map_memory);
執(zhí)行后的結(jié)果:
<---Map的插入時(shí)間--->914
<---Map占用的內(nèi)存--->28598272
復(fù)制代碼
SparseArray的正序插入：
復(fù)制代碼
SparseArray<String>sparse = new SparseArray<String>();
long start_sparse = System.currentTimeMillis();
for(int i=0;i<MAX;i++){
sparse.put(i, String.valueOf(i));
}
long sparse_memory = Runtime.getRuntime().totalMemory();
long end_sparse = System.currentTimeMillis()-start_sparse;
System.out.println("<---Sparse的插入時(shí)間--->"+end_sparse+"<---Sparse占用的內(nèi)存--->"+sparse_memory);
//執(zhí)行后的結(jié)果：
<---Sparse的插入時(shí)間--->611
<---Sparse占用的內(nèi)存--->23281664
復(fù)制代碼
我們可以看到100000條數(shù)據(jù)量正序插入時(shí)SparseArray的效率要比HashMap的效率要高.并且占用的內(nèi)存也比HashMap要小一些..這里的正序插入表示的是i的值是從小到大進(jìn)行的一個(gè)遞增..序列取決于i的值秆撮，而不是for循環(huán)內(nèi)部如何執(zhí)行...
通過運(yùn)行后的結(jié)果我們可以發(fā)現(xiàn)绢彤，SparseArray在正序插入的時(shí)候描馅，效率要比HashMap要快得多营勤，并且還節(jié)省了一部分內(nèi)存富弦。網(wǎng)上有很多的說法關(guān)于二者的效率問題沟娱，很多人都會(huì)誤認(rèn)為SparseArray要比HashMap的插入和查找的效率要快，還有人則是認(rèn)為Hash查找當(dāng)然要比SparseArray中的二分查找要快得多.
其實(shí)我認(rèn)為Android中在保存<Integer,Value>的時(shí)候推薦使用SparseArray的本質(zhì)目的不是由于效率的原因腕柜，而是內(nèi)存的原因.我們確實(shí)看到了插入的時(shí)候SparseArray要比HashMap要快.但是這僅僅是正序插入.我們來看看倒序插入的情況.
HashMap倒序插入：
復(fù)制代碼
System.out.println("<------------- 數(shù)據(jù)量100000 散列程度小 Map 倒序插入--------------->");
HashMap<Integer, String>map_2 = new HashMap<Integer, String>();
long start_map_2 = System.currentTimeMillis();
for(int i=MAX-1;i>=0;i--){
map_2.put(MAX-i-1, String.valueOf(MAX-i-1));
}
long map_memory_2 = Runtime.getRuntime().totalMemory();
long end_map_2 = System.currentTimeMillis()-start_map_2;
System.out.println("<---Map的插入時(shí)間--->"+end_map_2+"<---Map占用的內(nèi)存--->"+map_memory_2);
//執(zhí)行后的結(jié)果：
<------------- 數(shù)據(jù)量100000 Map 倒序插入--------------->
<---Map的插入時(shí)間--->836<---Map占用的內(nèi)存--->28598272
復(fù)制代碼
SparseArray倒序插入：
復(fù)制代碼
System.out.println("<------------- 數(shù)據(jù)量100000 散列程度小 SparseArray 倒序插入--------------->");
SparseArray<String>sparse_2 = new SparseArray<String>();
long start_sparse_2 = System.currentTimeMillis();
for(int i=MAX-1;i>=0;i--){
sparse_2.put(i, String.valueOf(MAX-i-1));
}
long sparse_memory_2 = Runtime.getRuntime().totalMemory();
long end_sparse_2 = System.currentTimeMillis()-start_sparse_2;
System.out.println("<---Sparse的插入時(shí)間--->"+end_sparse_2+"<---Sparse占用的內(nèi)存--->"+sparse_memory_2);
//執(zhí)行后的結(jié)果
<------------- 數(shù)據(jù)量100000 SparseArray 倒序插入--------------->
<---Sparse的插入時(shí)間--->20222<---Sparse占用的內(nèi)存--->23281664
復(fù)制代碼
通過上面的運(yùn)行結(jié)果,我們?nèi)匀豢梢钥吹?SparseArray與HashMap無論是怎樣進(jìn)行插入,數(shù)據(jù)量相同時(shí),前者都要比后者要省下一部分內(nèi)存,但是效率呢济似？我們可以看到,在倒序插入的時(shí)候,SparseArray的插入時(shí)間和HashMap的插入時(shí)間遠(yuǎn)遠(yuǎn)不是一個(gè)數(shù)量級(jí).由于SparseArray每次在插入的時(shí)候都要使用二分查找判斷是否有相同的值被插入.因此這種倒序的情況是SparseArray效率最差的時(shí)候.
SparseArray的插入源碼我們簡單的看一下..
復(fù)制代碼
public void put(int key, E value) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key); //二分查找.
if (i >= 0) { //如果當(dāng)前這個(gè)i在數(shù)組中存在,那么表示插入了相同的key值,只需要將value的值進(jìn)行覆蓋..
mValues[i] = value;
} else { //如果數(shù)組內(nèi)部不存在的話,那么返回的數(shù)值必然是負(fù)數(shù).
i = ~i; //因此需要取i的相反數(shù).
//i值小于mSize表示在這之前. mKey和mValue數(shù)組已經(jīng)被申請了空間.只是鍵值被刪除了.那么當(dāng)再次保存新的值的時(shí)候.不需要額外的開辟新的內(nèi)存空間.直接對(duì)數(shù)組進(jìn)行賦值即可.
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
//當(dāng)需要的空間要超出,但是mKey中存在無用的數(shù)值,那么需要調(diào)用gc()函數(shù).
if (mGarbage && mSize >= mKeys.length) {
gc();
// Search again because indices may have changed.
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
//如果需要的空間大于了原來申請的控件,那么需要為key和value數(shù)組開辟新的空間.
if (mSize >= mKeys.length) {
int n = ArrayUtils.idealIntArraySize(mSize + 1);
//定義了一個(gè)新的key和value數(shù)組.需要大于mSize
int[] nkeys = new int[n];
Object[] nvalues = new Object[n];
// Log.e("SparseArray", "grow " + mKeys.length + " to " + n);
//對(duì)數(shù)組進(jìn)行賦值也就是copy操作.將原來的mKey數(shù)組和mValue數(shù)組的值賦給新開辟的空間的數(shù)組.目的是為了添加新的鍵值對(duì).
System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
//將數(shù)組賦值..這里只是將數(shù)組的大小進(jìn)行擴(kuò)大..放入鍵值對(duì)的操作不在這里完成.
mKeys = nkeys;
mValues = nvalues;
}
//如果i的值沒有超過mSize的值.只需要擴(kuò)大mKey的長度即可.
if (mSize - i != 0) {
// Log.e("SparseArray", "move " + (mSize - i));
System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
}
//這里是用來完成放入操作的過程.
mKeys[i] = key;
mValues[i] = value;
mSize++;
}
}
復(fù)制代碼
這就是SparseArray插入函數(shù)的源碼.每次的插入方式都需要調(diào)用二分查找.因此這樣在倒序插入的時(shí)候會(huì)導(dǎo)致情況非常的糟糕,效率上絕對(duì)輸給了HashMap學(xué)過數(shù)據(jù)結(jié)構(gòu)的大家都知道.Map在插入的時(shí)候會(huì)對(duì)沖突因子做出相應(yīng)的決策.有非常好的處理沖突的方式.不需要遍歷每一個(gè)值.因此無論是倒序還是正序插入的效率取決于處理沖突的方式,因此插入時(shí)犧牲的時(shí)間基本是相同的.
通過插入.我們還是可以看出二者的差異的.
我們再來看一下查找首先是HashMap的查找.
復(fù)制代碼
System.out.println("<------------- 數(shù)據(jù)量100000 Map查找--------------->");
HashMap<Integer, String>map = new HashMap<Integer, String>();
for(int i=0;i<MAX;i++){
map.put(i, String.valueOf(i));
}
long start_time =System.currentTimeMillis();
for(int i=0;i<MAX;i+=100){
map.get(i);
}
long end_time =System.currentTimeMillis()-start_time;
System.out.println(end_time);
//執(zhí)行后的結(jié)果
復(fù)制代碼
SparseArray的查找:
復(fù)制代碼
System.out.println("<------------- 數(shù)據(jù)量100000 SparseArray 查找--------------->");
SparseArray<String>sparse = new SparseArray<String>();
for(int i=0;i<10000;i++){
sparse.put(i, String.valueOf(i));
}
long start_time =System.currentTimeMillis();
for(int i=0;i<MAX;i+=10){
sparse.get(i);
}
long end_time =System.currentTimeMillis()-start_time;
System.out.println(end_time);
//執(zhí)行后的結(jié)果
復(fù)制代碼
我這里也簡單的對(duì)查找的效率進(jìn)行了測試.對(duì)一個(gè)數(shù)據(jù)或者是幾個(gè)數(shù)據(jù)的查詢.二者的差異還是非常小的.當(dāng)數(shù)據(jù)量是100000條.查100000條的效率還是Map要快一點(diǎn).數(shù)據(jù)量為10000的時(shí)候.這就差異性就更小.但是Map的查找的效率確實(shí)還是贏了一籌.
其實(shí)在我看來.在保存<Integer,E>時(shí)使用SparseArray去替換HashMap的主要原因還是因?yàn)閮?nèi)存的關(guān)系.我們可以看到.保存的數(shù)據(jù)量無論是大還是小,Map所占用的內(nèi)存始終是大于SparseArray的.數(shù)據(jù)量100000條時(shí)SparseArray要比HashMap要節(jié)約27%的內(nèi)存.也就是以犧牲效率的代價(jià)去節(jié)約內(nèi)存空間.我們知道Android對(duì)內(nèi)存的使用是極為苛刻的.堆區(qū)允許使用的最大內(nèi)存僅僅16M.很容易出現(xiàn)OOM現(xiàn)象的發(fā)生.因此在Android中內(nèi)存的使用是非常的重要的.因此官方才推薦去使用SparseArray<E>去替換HashMap<Integer,E>.官方也確實(shí)聲明這種差異性不會(huì)超過50%.所以犧牲了部分效率換來內(nèi)存其實(shí)在Android中也算是一種很好的選擇吧.
