一、前言
在Android開發中，當需要存儲鍵值對時，一般都是用JAVA自帶的HashMap。但是細心的同學可能會發現，有時候如果實際的HashMap的key-vaule中的key是Integer時，AndroidStudio會提示一個warnning，具體是說推薦使用SparseArray替代HashMap：
雖然說warnning不影響實際功能，但是有個warnning放在那里總讓人不爽。因為是lint靜態掃描報的，可以用@SuppressLint("UseSparseArrays")忽略掉。但是既然google特地出了這么一個類用來替代key為Integer的HashMap，那是不是真的比HashMap更好用？
二、優缺點
It is intended to be more memory efficient than using a HashMap to map Integers to Objects, both because it avoids auto-boxing keys and its data structure doesn't rely on an extra entry object for each mApping.
源碼的注釋除了提到SparseArray有節約自動裝箱開銷的優點外，還提到SparseArray因為少了需要Map.Entry<K, V>作為輔助的存儲結構引入的內存開銷。
因為Map<K, V>的泛型聲明，key必須是Integer不能是int，所以確實會帶來自動裝箱的問題。
這兩個優點都是讓SparseArraymore memory efficient的，這是因為SparseArray的誕生就是針對某些Android設備內存比較緊張的情況的。
但是一般來說，SparseArray是比Hashmap慢的，在數據集大小只有上百個的時候，差別不大。
三、使用
不管是HashMap還是SpareArray，他們的作用都是維護一組邏輯上的key-value的對應關系。那么，在這組關系上最常做的操作就是存和取了。
存/取
HashMap的存操作和取操作分別對應方法put(K key, V value)和get(Object key)，大概用過HashMap的沒有不知道這兩個方法的。而SpareArray對的兩個方法分別是put(int key, E value)和get(int key)，和HashMap的方法看起來幾乎沒有區別，key為Integer的hashmap的相關代碼可以無縫換成SpareArray。
遍歷
SpareArray的遍歷要稍微麻煩些。
首先先建立一個概念，SparseArray執行put的時候其實是按照key的大小有序插入的。簡單來說，SparseArray維護了各個鍵值對的排序關系，具體的規則是以key升序排列。所以不同于HashMap只能通過key查找value，Sparse還能通過index查找value(或者key)，方法是valueAt(int index)(或者keyAt(int index))。這里的index是升序排序中鍵值對的位置，index是SparseArray相比Map多出來的概念，看了后面的源碼實現分析就好理解了。
拿上面的代碼舉例，put了key為100和200的兩個鍵值對，size為2，200-"firstValue"這對key-value對在index 0的位置，100-"secondValue"這對鍵值對在index 1的位置。順序是根據key的大小排的，跟put的先后順序無關。所以valueAt(0)拿到的是"secondValue"。
具體的遍歷代碼：
四、實現細節
和hashmap比較
大致講下hashmao的原理。hashmap使用key的hashcode來決定entry的存放位置，解決hash沖突使用的開散列方法，所以hashmap的底層數據結構看起來是一個鏈表的數組，鏈表的節點是包含了key和value的Entry類。看起來就像下圖：
而SparseArray的底層數據結構更簡單，只有int[] mKeys和Object[] mValues兩個數組。那這里就有個問題了：不同于HashMap專門用一個Entry的類存放key跟value，SpareArray里key和value分別存放在兩個數組里，那key和value是怎么對應上的？
答案就是，是根據index對應的，mKeys和mValues中index一樣的key和value就是相互對應的。所以SparseArray實際存儲的數據看起來是這樣的：
HashMap中基于Entry建立的key-value對應關系會導致Entry占用內存，而sparse基于index的對應關系是邏輯的，節省下了Entry類的內存，這又是SparseArray的一個優點。
存/取
前面提到，SparseArray中實際存儲的數據是有序的。那么保證有序的關鍵就在每次的存和刪操作中：在原本有序的情況下，保證存和刪操作后還是有序的。
看存操作的實現，注釋說明了關鍵點：
所以保證所有存儲的數據都是有序排列的關鍵就在于每次插入的時候如何確定插入的新數據插入的位置。上面看到每次確定實際插入的位置是基于二分查找確定的。舉個例子：
- 原先的數據是mIndexs = {1, 4, 6, 8}，size為4
- 要插入的key是7
- 第一次二分查找返回的index是-3，說明現在的數據中沒有這個index，這個key應該被插入index為3的位置
- 調用GrowingArrayUtils.insert將7插入index為3的位置，實際會引發mKeys擴容到8，原先的key8往右移
- 最后的數據是mIndexs = {1, 4, 6 ,7, 8}，保持了有序
其實實際插入數據的過程類似于優化后的插入排序，確定了插入的位置后把這個位置后面的數據移動一位，然后把新數據放入空出來的位置。
取的過程很簡單，同樣是根據二分查找找到如果有這個key的話它應該在哪個位置，如果找到的index<0反過來就證明了沒有這個key：
HashMap的取操作在hash分桶時時間復雜度為O(1)，但是在發生hash沖突的時候最后會在鏈表中順序查找，而SparseArray的取操作完全依賴于二分查找，時間復雜度理論上總是O(nlogn)，沒有hash沖突導致訪問慢的問題；不過HashMap的hash沖突一般很少，總體來說SparseArray總是比HashMap慢些；而且二分查找的時間復雜度也決定了SparseArray不適合大量數據的場景。
刪/gc
SparseArray刪除數據是通過delete(int key)方法刪除的。在刪除一條數據的時候，不是直接執行實際的刪除操作，而是先把要刪除的數據標記為DELETE狀態，在需要獲取size、擴容、取數據的時候，會執行gc，一次性真正把前面標記的所有刪除數據刪掉。
gc的過程有點類似虛擬機的gc中的標記整理算法。具體就是遍歷所有數據，收集所有沒有被刪除的數據移動到最前面。
這樣做的好處有兩個：
- 如果在剛delete了一條數據后又放了一條相同key的數據進來，這條數據因為被覆蓋了后面也不用執行真正的gc了，節省了操作時間
- 如果一次性delete多條數據，可以把真正的刪除操作放在一次gc中而不是多次gc中，節省時間
擴容/縮容
前面提到，在put數據的時候可能會引發擴容。擴容的時機很簡單，當底層的數組沒有空余的空間存放新的數據時就會引發擴容。擴容的算法很簡單，基本上就是翻倍，GrowingArrayUtils#growSize：
不過需要注意的是，growSize算出來size不一定是擴容操作后真正的size，因為擴容時新的數組是調用ArrayUtils#newUnpaddedArray生成新數組的，這個方法涉及內存對齊，實際返回的數組的size一般比要求的大小要大。
SparseArray是沒有縮容機制的。假如前面存了大量的數據導致數組擴容到了1024，哪怕調用clear清空所有數據底層數組的大小還是1024。所以先存放大量數據在刪到只剩少量需要長期持有的數據場景下，用SpareArray可能會導致空間的浪費。
總結
- 建議使用SparseArray替換HashMap是因為得益于下面幾點，SparseArray可能比HashMap更節省內存，而某些android設備上內存是緊缺資源：
- 避免了Integer的自動裝箱
- 基于index建立的key和value的映射關系相比Map基于Entry結構建立key和value的映射關系節約內存
- 某些場景如hash沖突下訪問速度可能優于hashmap；不適合數據集比較大的場景。
- SparseArray沒有縮容機制。某些場景下不適合使用，比如：大量地put后大量地delete，然后長久持有SparseArray，導致大量的空位置沒法被虛擬機gc，浪費內存
- SparseArray一般來說比Hashmap慢，因為二分查找比較慢，而且插入刪除數據涉及數組的copy。在數據集不大時不明顯
- SparseArray每次插入刪除數據都保證了所有存儲數據的排列有序
- SparseArray可以通過index定位數據，Hashmap不行
最后
如果你看到了這里，覺得文章寫得不錯就給個贊唄！歡迎大家評論討論！如果你覺得那里值得改進的，請給我留言。一定會認真查詢，修正不足，定期免費分享技術干貨。感興趣的小伙伴可以點一下關注哦。謝謝！
轉載自今日頭條 Android架構師丨小熊
