一、前言

在Android開發(fā)中，當(dāng)需要存儲鍵值對時，一般都是用JAVA自帶的HashMap。但是細(xì)心的同學(xué)可能會發(fā)現(xiàn)，有時候如果實際的HashMap的key-vaule中的key是Integer時，AndroidStudio會提示一個warnning，具體是說推薦使用SparseArray替代HashMap：

Android數(shù)據(jù)結(jié)構(gòu)之SparseArray

雖然說warnning不影響實際功能，但是有個warnning放在那里總讓人不爽。因為是lint靜態(tài)掃描報的，可以用@SuppressLint("UseSparseArrays")忽略掉。但是既然google特地出了這么一個類用來替代key為Integer的HashMap，那是不是真的比HashMap更好用？

二、優(yōu)缺點

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有節(jié)約自動裝箱開銷的優(yōu)點外，還提到SparseArray因為少了需要Map.Entry<K, V>作為輔助的存儲結(jié)構(gòu)引入的內(nèi)存開銷。

因為Map<K, V>的泛型聲明，key必須是Integer不能是int，所以確實會帶來自動裝箱的問題。

這兩個優(yōu)點都是讓SparseArraymore memory efficient的，這是因為SparseArray的誕生就是針對某些Android設(shè)備內(nèi)存比較緊張的情況的。

但是一般來說，SparseArray是比Hashmap慢的，在數(shù)據(jù)集大小只有上百個的時候，差別不大。

三、使用

不管是HashMap還是SpareArray，他們的作用都是維護(hù)一組邏輯上的key-value的對應(yīng)關(guān)系。那么，在這組關(guān)系上最常做的操作就是存和取了。

存/取

HashMap的存操作和取操作分別對應(yīng)方法put(K key, V value)和get(Object key)，大概用過HashMap的沒有不知道這兩個方法的。而SpareArray對的兩個方法分別是put(int key, E value)和get(int key)，和HashMap的方法看起來幾乎沒有區(qū)別，key為Integer的hashmap的相關(guān)代碼可以無縫換成SpareArray。

遍歷

SpareArray的遍歷要稍微麻煩些。

首先先建立一個概念，SparseArray執(zhí)行put的時候其實是按照key的大小有序插入的。簡單來說，SparseArray維護(hù)了各個鍵值對的排序關(guān)系，具體的規(guī)則是以key升序排列。所以不同于HashMap只能通過key查找value，Sparse還能通過index查找value(或者key)，方法是valueAt(int index)(或者keyAt(int index))。這里的index是升序排序中鍵值對的位置，index是SparseArray相比Map多出來的概念，看了后面的源碼實現(xiàn)分析就好理解了。

拿上面的代碼舉例，put了key為100和200的兩個鍵值對，size為2，200-"firstValue"這對key-value對在index 0的位置，100-"secondValue"這對鍵值對在index 1的位置。順序是根據(jù)key的大小排的，跟put的先后順序無關(guān)。所以valueAt(0)拿到的是"secondValue"。

具體的遍歷代碼：

四、實現(xiàn)細(xì)節(jié)

和hashmap比較

大致講下hashmao的原理。hashmap使用key的hashcode來決定entry的存放位置，解決hash沖突使用的開散列方法，所以hashmap的底層數(shù)據(jù)結(jié)構(gòu)看起來是一個鏈表的數(shù)組，鏈表的節(jié)點是包含了key和value的Entry類。看起來就像下圖：

而SparseArray的底層數(shù)據(jù)結(jié)構(gòu)更簡單，只有int[] mKeys和Object[] mValues兩個數(shù)組。那這里就有個問題了：不同于HashMap專門用一個Entry的類存放key跟value，SpareArray里key和value分別存放在兩個數(shù)組里，那key和value是怎么對應(yīng)上的？

答案就是，是根據(jù)index對應(yīng)的，mKeys和mValues中index一樣的key和value就是相互對應(yīng)的。所以SparseArray實際存儲的數(shù)據(jù)看起來是這樣的：

HashMap中基于Entry建立的key-value對應(yīng)關(guān)系會導(dǎo)致Entry占用內(nèi)存，而sparse基于index的對應(yīng)關(guān)系是邏輯的，節(jié)省下了Entry類的內(nèi)存，這又是SparseArray的一個優(yōu)點。

存/取

前面提到，SparseArray中實際存儲的數(shù)據(jù)是有序的。那么保證有序的關(guān)鍵就在每次的存和刪操作中：在原本有序的情況下，保證存和刪操作后還是有序的。

看存操作的實現(xiàn)，注釋說明了關(guān)鍵點：

所以保證所有存儲的數(shù)據(jù)都是有序排列的關(guān)鍵就在于每次插入的時候如何確定插入的新數(shù)據(jù)插入的位置。上面看到每次確定實際插入的位置是基于二分查找確定的。舉個例子：

原先的數(shù)據(jù)是mIndexs = {1, 4, 6, 8}，size為4
要插入的key是7
第一次二分查找返回的index是-3，說明現(xiàn)在的數(shù)據(jù)中沒有這個index，這個key應(yīng)該被插入index為3的位置
調(diào)用GrowingArrayUtils.insert將7插入index為3的位置，實際會引發(fā)mKeys擴(kuò)容到8，原先的key8往右移
最后的數(shù)據(jù)是mIndexs = {1, 4, 6 ,7, 8}，保持了有序

其實實際插入數(shù)據(jù)的過程類似于優(yōu)化后的插入排序，確定了插入的位置后把這個位置后面的數(shù)據(jù)移動一位，然后把新數(shù)據(jù)放入空出來的位置。

取的過程很簡單，同樣是根據(jù)二分查找找到如果有這個key的話它應(yīng)該在哪個位置，如果找到的index<0反過來就證明了沒有這個key：

HashMap的取操作在hash分桶時時間復(fù)雜度為O(1)，但是在發(fā)生hash沖突的時候最后會在鏈表中順序查找，而SparseArray的取操作完全依賴于二分查找，時間復(fù)雜度理論上總是O(nlogn)，沒有hash沖突導(dǎo)致訪問慢的問題；不過HashMap的hash沖突一般很少，總體來說SparseArray總是比HashMap慢些；而且二分查找的時間復(fù)雜度也決定了SparseArray不適合大量數(shù)據(jù)的場景。

刪/gc

SparseArray刪除數(shù)據(jù)是通過delete(int key)方法刪除的。在刪除一條數(shù)據(jù)的時候，不是直接執(zhí)行實際的刪除操作，而是先把要刪除的數(shù)據(jù)標(biāo)記為DELETE狀態(tài)，在需要獲取size、擴(kuò)容、取數(shù)據(jù)的時候，會執(zhí)行g(shù)c，一次性真正把前面標(biāo)記的所有刪除數(shù)據(jù)刪掉。

gc的過程有點類似虛擬機的gc中的標(biāo)記整理算法。具體就是遍歷所有數(shù)據(jù)，收集所有沒有被刪除的數(shù)據(jù)移動到最前面。

這樣做的好處有兩個：

如果在剛delete了一條數(shù)據(jù)后又放了一條相同key的數(shù)據(jù)進(jìn)來，這條數(shù)據(jù)因為被覆蓋了后面也不用執(zhí)行真正的gc了，節(jié)省了操作時間
如果一次性delete多條數(shù)據(jù)，可以把真正的刪除操作放在一次gc中而不是多次gc中，節(jié)省時間

擴(kuò)容/縮容

前面提到，在put數(shù)據(jù)的時候可能會引發(fā)擴(kuò)容。擴(kuò)容的時機很簡單，當(dāng)?shù)讓拥臄?shù)組沒有空余的空間存放新的數(shù)據(jù)時就會引發(fā)擴(kuò)容。擴(kuò)容的算法很簡單，基本上就是翻倍，GrowingArrayUtils#growSize：

不過需要注意的是，growSize算出來size不一定是擴(kuò)容操作后真正的size，因為擴(kuò)容時新的數(shù)組是調(diào)用ArrayUtils#newUnpaddedArray生成新數(shù)組的，這個方法涉及內(nèi)存對齊，實際返回的數(shù)組的size一般比要求的大小要大。

SparseArray是沒有縮容機制的。假如前面存了大量的數(shù)據(jù)導(dǎo)致數(shù)組擴(kuò)容到了1024，哪怕調(diào)用clear清空所有數(shù)據(jù)底層數(shù)組的大小還是1024。所以先存放大量數(shù)據(jù)在刪到只剩少量需要長期持有的數(shù)據(jù)場景下，用SpareArray可能會導(dǎo)致空間的浪費。

總結(jié)

建議使用SparseArray替換HashMap是因為得益于下面幾點，SparseArray可能比HashMap更節(jié)省內(nèi)存，而某些android設(shè)備上內(nèi)存是緊缺資源：
避免了Integer的自動裝箱
基于index建立的key和value的映射關(guān)系相比Map基于Entry結(jié)構(gòu)建立key和value的映射關(guān)系節(jié)約內(nèi)存
某些場景如hash沖突下訪問速度可能優(yōu)于hashmap；不適合數(shù)據(jù)集比較大的場景。
SparseArray沒有縮容機制。某些場景下不適合使用，比如：大量地put后大量地delete，然后長久持有SparseArray，導(dǎo)致大量的空位置沒法被虛擬機gc，浪費內(nèi)存
SparseArray一般來說比Hashmap慢，因為二分查找比較慢，而且插入刪除數(shù)據(jù)涉及數(shù)組的copy。在數(shù)據(jù)集不大時不明顯
SparseArray每次插入刪除數(shù)據(jù)都保證了所有存儲數(shù)據(jù)的排列有序
SparseArray可以通過index定位數(shù)據(jù)，Hashmap不行

最后

如果你看到了這里，覺得文章寫得不錯就給個贊唄！歡迎大家評論討論！如果你覺得那里值得改進(jìn)的，請給我留言。一定會認(rèn)真查詢，修正不足，定期免費分享技術(shù)干貨。感興趣的小伙伴可以點一下關(guān)注哦。謝謝！

轉(zhuǎn)載自今日頭條 Android架構(gòu)師丨小熊