ArrayMap及SparseArray是android的系統(tǒng)API畜晰，是專門為移動設(shè)備而定制的砾莱。用于在一定情況下取代HashMap而達到節(jié)省內(nèi)存的目的。
一.源碼分析(由于篇幅限制凄鼻，源碼分析部分會放在單獨的文章中)
二.實現(xiàn)原理及數(shù)據(jù)結(jié)構(gòu)對比
三.性能測試對比
四.總結(jié)
一.源碼分析
稍后會在下一篇文章中補充（都寫在一篇腊瑟，篇幅太長了）
二.實現(xiàn)原理及數(shù)據(jù)結(jié)構(gòu)對比
1. hashMap
從hashMap的結(jié)構(gòu)中可以看出，首先對key值求hash块蚌，根據(jù)hash結(jié)果確定在table數(shù)組中的位置闰非，當(dāng)出現(xiàn)哈希沖突時采用開放鏈地址法進行處理。Map.Entity的數(shù)據(jù)結(jié)構(gòu)如下：
static class HashMapEntry<K, V> implements Entry<K, V> {
final K key;
V value;
final int hash;
HashMapEntry<K, V> next;
}
具體的hashmap源碼細節(jié)會在其他文章中進行分析峭范，這里可以看出來的是财松，從空間的角度分析，HashMap中會有一個利用率不超過負載因子（默認為0.75）的table數(shù)組，其次辆毡，對于HashMap的每一條數(shù)據(jù)都會用一個HashMapEntry進行記錄菜秦，除了記錄key，value外舶掖，還會記錄下hash值球昨，及下一個entity的指針。
時間效率方面访锻，利用hash算法褪尝，插入和查找等操作都很快闹获，且一般情況下期犬，每一個數(shù)組值后面不會存在很長的鏈表（因為出現(xiàn)hash沖突畢竟占比較小的比例），所以不考慮空間利用率的話避诽，HashMap的效率非常高龟虎。
2.ArrayMap
ArrayMap利用兩個數(shù)組，mHashes用來保存每一個key的hash值沙庐，mArrray大小為mHashes的2倍鲤妥，依次保存key和value。源碼的細節(jié)方面會在下一篇文章中說明」俺現(xiàn)在我們先拋開細節(jié)部分棉安，只看關(guān)鍵語句：
mHashes[index] = hash;
mArray[index<<1] = key;
mArray[(index<<1)+1] = value;
相信看到這大家都明白了原理了。但是它怎么查詢呢铸抑？答案是二分查找贡耽。當(dāng)插入時，根據(jù)key的hashcode()方法得到hash值鹊汛，計算出在mArrays的index位置蒲赂，然后利用二分查找找到對應(yīng)的位置進行插入，當(dāng)出現(xiàn)哈希沖突時刁憋，會在index的相鄰位置插入滥嘴。
總結(jié)一下，空間角度考慮至耻，ArrayMap每存儲一條信息若皱，需要保存一個hash值，一個key值尘颓，一個value值走触。對比下HashMap 粗略的看，只是減少了一個指向下一個entity的指針泥耀。還有就是節(jié)省了一部分可見空間上的內(nèi)存節(jié)省也不是特別明顯饺汹。是不是這樣呢？后面會驗證痰催。
時間效率上看兜辞，插入和查找的時候因為都用的二分法迎瞧，查找的時候應(yīng)該是沒有hash查找快，插入的時候呢逸吵，如果順序插入的話效率肯定高凶硅，但如果是隨機插入，肯定會涉及到大量的數(shù)組搬移扫皱，數(shù)據(jù)量大足绅，肯定不行，再想一下韩脑，如果是不湊巧氢妈，每次插入的hash值都比上一次的小，那就得次次搬移段多，效率一下就扛不住了的感腳首量。
3.SparseArray
sparseArray相對來說就簡單的多了，但是不要以為它可以取代前兩種进苍，sparseArray只能在key為int的時候才能使用加缘，注意是int而不是Integer，這也是sparseArray效率提升的一個點觉啊，去掉了裝箱的操作!拣宏。
因為key為int也就不需要什么hash值了，只要int值相等杠人，那就是同一個對象勋乾，簡單粗暴。插入和查找也是基于二分法搜吧，所以原理和Arraymap基本一致市俊，這里就不多說了。
總結(jié)一下：空間上對比滤奈，與HashMap摆昧，去掉了Hash值的存儲空間，沒有next的指針占用蜒程，還有其他一些小的內(nèi)存占用绅你，看著節(jié)省了不少。
時間上對比：插入和查找的情形和Arraymap基本一致昭躺，可能存在大量的數(shù)組搬移忌锯。但是它避免了裝箱的環(huán)節(jié)，不要小看裝箱過程领炫，還是很費時的偶垮。所以從源碼上來看，效率誰快，就看數(shù)據(jù)量大小了似舵。
好啦脚猾，說半天都是分析，下面來點實際的砚哗，用數(shù)據(jù)說話龙助！
三.性能測試對比
我們從插入和查詢兩方面來比對試試看。
1.插入性能時間對比
測試代碼：
long start = System.currentTimeMillis();
Map<Integer, String> hash = new HashMap<Integer, String>();
for (int i = 0; i < MAX; i++) {
hash.put(i, i+"");
}
long ts = System.currentTimeMillis() - start;
就貼這一段吧蛛芥，其他兩段代碼無非就是把HashMap換掉提鸟，通過改變Max值就行對比。
分析：從結(jié)果上來看仅淑，數(shù)據(jù)量小的時候称勋，差異并不大（當(dāng)然了，數(shù)據(jù)量小漓糙，時間基準(zhǔn)小铣缠，內(nèi)容太多,就不貼數(shù)據(jù)表了，確實差異不大）昆禽，當(dāng)數(shù)據(jù)量大于5000左右，SparseArray蝇庭，最快醉鳖，HashMap最慢，乍一看哮内，好像SparseArray是最快的盗棵，但是要注意，這是順序插入的北发。也就是SparseArray和Arraymap最理想的情況纹因。
來個逆序插入的試試
long start = System.currentTimeMillis();
HashMap<Integer, String> hash = new HashMap<Integer, String>();
for (int i = 0; i < MAX; i++) {
hash.put(MAX-1-i, i+"");
}
long ts = System.currentTimeMillis() - start;
分析：從結(jié)果上來看，果然琳拨，HashMap遠超Arraymap和SparseArray瞭恰，也前面分析一致。
當(dāng)然了狱庇，數(shù)據(jù)量小的時候惊畏，例如1000以下，這點時間差異也是可以忽略的密任。
下面來看看空間對比：先說一下測試方法颜启，因為測試內(nèi)存，所以尤其要注意的一點浪讳，就是測試的過程不要發(fā)生GC缰盏，如果發(fā)生了GC，那數(shù)據(jù)就不準(zhǔn)了，想了想口猜，用了個比較簡單的方法：
Runtime.getRuntime().totalMemory()//獲取應(yīng)用已經(jīng)申請到的總的內(nèi)存
Runtime.getRuntime().freeMemory()//獲取應(yīng)用內(nèi)存的free部分
兩個方法的差值就是應(yīng)用已經(jīng)使用的內(nèi)存部分形葬。
值得注意的是當(dāng)MAX值很大的時候，可能在代碼執(zhí)行過程發(fā)生GC暮的，此時可以同時用Android Monitor的Memory窗口監(jiān)視內(nèi)存笙以，沒有發(fā)生gc的過程結(jié)果才有效。假設(shè)數(shù)據(jù)量比較大的時候冻辩，每測完一次手動GC一次猖腕，這樣基本上每次都能測試成功；因為數(shù)據(jù)量也不是特別大恨闪，只有很少一部分情況測試過程會發(fā)生GC倘感，所以也沒有去進一步探究其他方式，比如設(shè)置虛擬機參數(shù)來延長GC時間咙咽，有空了可以搞一下老玛。上數(shù)據(jù)：
可見，SparseArray在內(nèi)存占用方面的確要優(yōu)于HashMap和ArrayMap不少钧敞，通過數(shù)據(jù)觀察蜡豹，大致節(jié)省30%左右，而ArrayMap的表現(xiàn)正如前面說的溉苛，優(yōu)化作用有限镜廉，幾乎和HashMap相同。
2.查找性能對比
long start = System.currentTimeMillis();
SparseArray<String> hash = new SparseArray<String>();
for (int i = 0; i < MAX; i++) {
hash.get(i);
}
long ts = System.currentTimeMillis() - start;
發(fā)現(xiàn)SparseArray比HashMap要快愚战，和前面假設(shè)的不符娇唯，二分查找難道比Hash快？
再一想寂玲，因為用這樣的代碼測試有點不公平塔插，因為SparseArray沒有裝箱，HashMap有個裝箱的過程拓哟，似乎不太公平想许。那么想個辦法再來測試下，
ArrayList<IntEntity> intEntityList=new ArrayList<IntEntity>();
private void boxing(){
for(int i=0;i<MAX;i++){
IntEntity entity=new IntEntity();
entity.i1=i;
entity.i2=Integer.valueOf(i);
intEntityList.add(entity);
}
}
class IntEntity{
int i1;
Integer i2;
}
給HashMap和ArrayMap的時候給它提前裝箱彰檬，這樣似乎公平些伸刃。
long start = System.currentTimeMillis();
HashMap<Integer, String> hash = new HashMap<Integer, String>();
for (int i = 0; i < MAX; i++) {
// hash.get(i);
hash.get(intEntityList.get(i).i2);
}
long ts = System.currentTimeMillis() - start;
果然結(jié)果不一樣了，HashMap才是查詢最快的逢倍，這才符合邏輯嘛捧颅，但是我們正常用的時候是不管裝不裝箱的，所以綜合起來還是使用SparseArray效率最高较雕。
扯了這么多碉哑，終于到了該總結(jié)的時候了挚币。
四、總結(jié)
1.在數(shù)據(jù)量小的時候一般認為1000以下扣典，當(dāng)你的key為int的時候妆毕，使用SparseArray確實是一個很不錯的選擇，內(nèi)存大概能節(jié)省30%贮尖，相比用HashMap笛粘，因為它key值不需要裝箱，所以時間性能平均來看也優(yōu)于HashMap,建議使用湿硝！
2.ArrayMap相對于SparseArray薪前，特點就是key值類型不受限，任何情況下都可以取代HashMap,但是通過研究和測試發(fā)現(xiàn)关斜，ArrayMap的內(nèi)存節(jié)省并不明顯示括，也就在10%左右，但是時間性能確是最差的痢畜，當(dāng)然了垛膝，1000以內(nèi)的數(shù)據(jù)量也無所謂了，加上它只有在API>=19才可以使用丁稀，個人建議沒必要使用吼拥！還不如用HashMap放心。估計這也是為什么我們再new一個HashMap的時候google也沒有提示讓我們使用的原因吧二驰。
目前本人在公司負責(zé)熱修復(fù)相關(guān)的工作扔罪，主要是基于robust的熱修復(fù)相關(guān)工作。感興趣的同學(xué)歡迎進群交流桶雀。
