一、前言
在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:

雖然說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)師丨小熊