Android內(nèi)存優(yōu)化（使用SparseArray和ArrayMap取代HashMap）

在Android開發(fā)時(shí)，我們使用的大部分都是Java的api，比方HashMap這個(gè)api，使用率非常高，可是對(duì)于Android這樣的對(duì)內(nèi)存非常敏感的移動(dòng)平臺(tái)，非常多時(shí)候使用一些java的api并不能達(dá)到更好的性能，相反反而更消耗內(nèi)存，所以針對(duì)Android這樣的移動(dòng)平臺(tái)，也推出了更符合自己的api，比方SparseArray、ArrayMap用來取代HashMap在有些情況下能帶來更好的性能提升。

介紹它們之前先來介紹一下HashMap的內(nèi)部存儲(chǔ)結(jié)構(gòu)。就明確為什么推薦使用SparseArray和ArrayMap

HashMap

HashMap內(nèi)部是使用一個(gè)默認(rèn)容量為16的數(shù)組來存儲(chǔ)數(shù)據(jù)的，而數(shù)組中每個(gè)元素卻又是一個(gè)鏈表的頭結(jié)點(diǎn)。所以，更準(zhǔn)確的來說，HashMap內(nèi)部存儲(chǔ)結(jié)構(gòu)是使用哈希表的拉鏈結(jié)構(gòu)（數(shù)組+鏈表），如圖：

這樣的存儲(chǔ)數(shù)據(jù)的方法叫做拉鏈法

image

且每個(gè)結(jié)點(diǎn)都是Entry類型，那么Entry是什么呢？我們來看看HashMap中Entry的屬性：

finalK key;
V value;
finalinthash;
HashMapEntry next;

從中我們得知Entry存儲(chǔ)的內(nèi)容有key、value、hash值、和next下一個(gè)Entry。那么。這些Entry數(shù)據(jù)是按什么規(guī)則進(jìn)行存儲(chǔ)的呢？就是通過計(jì)算元素key的hash值，然后對(duì)HashMap中數(shù)組長(zhǎng)度取余得到該元素存儲(chǔ)的位置。計(jì)算公式為hash(key)%len，比方：假設(shè)hash(14)=14,hash(30)=30,hash(46)=46，我們分別對(duì)len取余，得到

hash(14)%16=14，hash(30)%16=14，hash(46)%16=14，所以key為14、30、46的這三個(gè)元素存儲(chǔ)在數(shù)組下標(biāo)為14的位置，如：

image

從中能夠看出。假設(shè)有多個(gè)元素key的hash值相同的話。后一個(gè)元素并不會(huì)覆蓋上一個(gè)元素。而是採取鏈表的方式，把之后加進(jìn)來的元素加入鏈表末尾。從而攻克了hash沖突的問題。由此我們知道HashMap中處理hash沖突的方法是鏈地址法，在此補(bǔ)充一個(gè)知識(shí)點(diǎn)，處理hash沖突的方法有下面幾種：

開放地址法

再哈希法

鏈地址法

建立公共溢出區(qū)

說到這里，重點(diǎn)來了，我們知道HashMap中默認(rèn)的存儲(chǔ)大小就是一個(gè)容量為16的數(shù)組，所以當(dāng)我們創(chuàng)建出一個(gè)HashMap對(duì)象時(shí)，即使里面沒有不論什么元素。也要分別一塊內(nèi)存空間給它，并且，我們?cè)俨粩嗟南騂ashMap里put數(shù)據(jù)時(shí)，當(dāng)達(dá)到一定的容量限制時(shí)（這個(gè)容量滿足這樣的一個(gè)關(guān)系時(shí)候?qū)?huì)擴(kuò)容：HashMap中的數(shù)據(jù)量>容量*載入因子，而HashMap中默認(rèn)的載入因子是0.75），HashMap的空間將會(huì)擴(kuò)大，并且擴(kuò)大后新的空間一定是原來的2倍，我們能夠看put()方法中有這樣的一行代碼：

int newCapacity = oldCapacity * 2;

所以，重點(diǎn)就是這個(gè)，僅僅要一滿足擴(kuò)容條件，HashMap的空間將會(huì)以2倍的規(guī)律進(jìn)行增大。

假如我們有幾十萬、幾百萬條數(shù)據(jù)，那么HashMap要存儲(chǔ)完這些數(shù)據(jù)將要不斷的擴(kuò)容，并且在此過程中也須要不斷的做hash運(yùn)算，這將對(duì)我們的內(nèi)存空間造成非常大消耗和浪費(fèi)。并且HashMap獲取數(shù)據(jù)是通過遍歷Entry[]數(shù)組來得到相應(yīng)的元素，在數(shù)據(jù)量非常大時(shí)候會(huì)比較慢，所以在Android中，HashMap是比較費(fèi)內(nèi)存的，我們?cè)谝恍┣闆r下能夠使用SparseArray和ArrayMap來取代HashMap。

SparseArray

SparseArray比HashMap更省內(nèi)存，在某些條件下性能更好，主要是由于它避免了對(duì)key的自己主動(dòng)裝箱（int轉(zhuǎn)為Integer類型），它內(nèi)部則是通過兩個(gè)數(shù)組來進(jìn)行數(shù)據(jù)存儲(chǔ)的。一個(gè)存儲(chǔ)key，另外一個(gè)存儲(chǔ)value，為了優(yōu)化性能，它內(nèi)部對(duì)數(shù)據(jù)還採取了壓縮的方式來表示稀疏數(shù)組的數(shù)據(jù)，從而節(jié)約內(nèi)存空間。我們從源代碼中能夠看到key和value各自是用數(shù)組表示：

privateint[] mKeys;
privateObject[] mValues;

我們能夠看到，SparseArray僅僅能存儲(chǔ)key為int類型的數(shù)據(jù)。同一時(shí)候，SparseArray在存儲(chǔ)和讀取數(shù)據(jù)時(shí)候，使用的是二分查找法，我們能夠看看：

public void put(int key, E value) {       
 int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
...
} 
public E get(int key, E valueIfKeyNotFound) {  
      int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
...
}

也就是在put加入數(shù)據(jù)的時(shí)候。會(huì)使用二分查找法和之前的key比較當(dāng)前我們加入的元素的key的大小，然后依照從小到大的順序排列好，所以，SparseArray存儲(chǔ)的元素都是按元素的key值從小到大排列好的。

而在獲取數(shù)據(jù)的時(shí)候，也是使用二分查找法推斷元素的位置，所以，在獲取數(shù)據(jù)的時(shí)候非?？?，比HashMap快的多，由于HashMap獲取數(shù)據(jù)是通過遍歷Entry[]數(shù)組來得到相應(yīng)的元素。

加入數(shù)據(jù)

publicvoidput(intkey, Evalue)

刪除數(shù)據(jù)

publicvoidremove(intkey)

or

publicvoiddelete(intkey)

事實(shí)上remove內(nèi)部還是通過調(diào)用delete來刪除數(shù)據(jù)的

獲取數(shù)據(jù)

publicEget(intkey)

or

publicEget(intkey, E valueIfKeyNotFound)

該方法可設(shè)置假設(shè)key不存在的情況下默認(rèn)返回的value

特有方法

在此之外，SparseArray還提供了兩個(gè)特有方法。更方便數(shù)據(jù)的查詢：

獲取相應(yīng)的key：

publicintkeyAt(intindex)

獲取相應(yīng)的value：

publicEvalueAt(intindex)

SparseArray應(yīng)用場(chǎng)景：

雖說SparseArray性能比較好，可是由于其加入、查找、刪除數(shù)據(jù)都須要先進(jìn)行一次二分查找。所以在數(shù)據(jù)量大的情況下性能并不明顯，將減少至少50%。

滿足下面兩個(gè)條件我們能夠使用SparseArray取代HashMap：

數(shù)據(jù)量不大，最好在千級(jí)以內(nèi)

key必須為int類型，這中情況下的HashMap能夠用SparseArray取代：

HashMap map =newHashMap<>();用SparseArray取代:SparseArray array =newSparseArray<>();

ArrayMap

這個(gè)api的資料在網(wǎng)上能夠說差點(diǎn)兒沒有，然并卵，僅僅能看文檔了

ArrayMap是一個(gè)<key,value>映射的數(shù)據(jù)結(jié)構(gòu)，它設(shè)計(jì)上很多其他的是考慮內(nèi)存的優(yōu)化，內(nèi)部是使用兩個(gè)數(shù)組進(jìn)行數(shù)據(jù)存儲(chǔ)，一個(gè)數(shù)組記錄key的hash值。另外一個(gè)數(shù)組記錄Value值。它和SparseArray一樣。也會(huì)對(duì)key使用二分法進(jìn)行從小到大排序，在加入、刪除、查找數(shù)據(jù)的時(shí)候都是先使用二分查找法得到相應(yīng)的index，然后通過index來進(jìn)行加入、查找、刪除等操作，所以，應(yīng)用場(chǎng)景和SparseArray的一樣，假設(shè)在數(shù)據(jù)量比較大的情況下，那么它的性能將退化至少50%。

加入數(shù)據(jù)

publicVput(K key, Vvalue)

獲取數(shù)據(jù)

publicVget(Objectkey)

刪除數(shù)據(jù)

publicV remove(Objectkey)

特有方法

它和SparseArray一樣相同也有兩個(gè)更方便的獲取數(shù)據(jù)方法：

publicKkeyAt(intindex)
publicVvalueAt(intindex)

ArrayMap應(yīng)用場(chǎng)景

數(shù)據(jù)量不大，最好在千級(jí)以內(nèi)

數(shù)據(jù)結(jié)構(gòu)類型為Map類型

ArrayMap arrayMap = new ArrayMap<>();

【注】：假設(shè)我們要兼容aip19下面版本號(hào)的話，那么導(dǎo)入的包須要為v4包

import android.support.v4.util.ArrayMap;

總結(jié)

SparseArray和ArrayMap都差點(diǎn)兒相同，使用哪個(gè)呢？

假設(shè)數(shù)據(jù)量都在千級(jí)以內(nèi)的情況下：

1、假設(shè)key的類型已經(jīng)確定為int類型。那么使用SparseArray，由于它避免了自己主動(dòng)裝箱的過程，假設(shè)key為long類型，它還提供了一個(gè)LongSparseArray來確保key為long類型時(shí)的使用

2、假設(shè)key類型為其他的類型，則使用ArrayMap