一、前言

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

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

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

二、優(yōu)缺點(diǎn)

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é)約自動(dòng)裝箱開銷的優(yōu)點(diǎn)外，還提到SparseArray因?yàn)樯倭诵枰狹ap.Entry<K, V>作為輔助的存儲(chǔ)結(jié)構(gòu)引入的內(nèi)存開銷。

因?yàn)镸ap<K, V>的泛型聲明，key必須是Integer不能是int，所以確實(shí)會(huì)帶來自動(dòng)裝箱的問題。

這兩個(gè)優(yōu)點(diǎn)都是讓SparseArraymore memory efficient的，這是因?yàn)镾parseArray的誕生就是針對(duì)某些Android設(shè)備內(nèi)存比較緊張的情況的。

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

三、使用

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

存/取

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

遍歷

SpareArray的遍歷要稍微麻煩些。

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

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

具體的遍歷代碼：

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

和hashmap比較

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

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

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

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

存/取

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

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

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

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

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

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

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

刪/gc

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

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

這樣做的好處有兩個(gè)：

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

擴(kuò)容/縮容

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

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

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

總結(jié)

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

最后

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

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