今天無意間看到這篇關(guān)于內(nèi)存優(yōu)化的文章唧席，我認(rèn)為寫的很不錯尺借，所以就想保留下來驾讲。
轉(zhuǎn)載的文章出處：https://blog.csdn.net/u010687392/article/details/47809295
在Android開發(fā)時色难，我們使用的大部分都是Java的api稍计，比如HashMap這個api躁绸，使用率非常高，但是對于Android這種對內(nèi)存非常敏感的移動平臺，很多時候使用一些java的api并不能達(dá)到更好的性能净刮，相反反而更消耗內(nèi)存剥哑，所以針對Android這種移動平臺，也推出了更符合自己的api淹父，比如SparseArray星持、ArrayMap用來代替HashMap在有些情況下能帶來更好的性能提升。
介紹它們之前先來介紹一下HashMap的內(nèi)部存儲結(jié)構(gòu)弹灭，就明白為什么推薦使用SparseArray和ArrayMap
HashMap
HashMap內(nèi)部是使用一個默認(rèn)容量為16的數(shù)組來存儲數(shù)據(jù)的督暂，而數(shù)組中每一個元素卻又是一個鏈表的頭結(jié)點，所以穷吮，更準(zhǔn)確的來說逻翁，HashMap內(nèi)部存儲結(jié)構(gòu)是使用哈希表的拉鏈結(jié)構(gòu)（數(shù)組+鏈表），如圖：
這種存儲數(shù)據(jù)的方法叫做拉鏈法
且每一個結(jié)點都是Entry類型捡鱼，那么Entry是什么呢八回？我們來看看HashMap中Entry的屬性：
final K key;
V value;
final int hash;
HashMapEntry<K, V> next;
從中我們得知Entry存儲的內(nèi)容有key、value驾诈、hash值缠诅、和next下一個Entry，那么乍迄，這些Entry數(shù)據(jù)是按什么規(guī)則進(jìn)行存儲的呢管引？就是通過計算元素key的hash值，然后對HashMap中數(shù)組長度取余得到該元素存儲的位置闯两，計算公式為hash(key)%len褥伴，比如：假設(shè)hash(14)=14,hash(30)=30,hash(46)=46，我們分別對len取余漾狼，得到
hash(14)%16=14重慢，hash(30)%16=14，hash(46)%16=14逊躁，所以key為14似踱、30、46的這三個元素存儲在數(shù)組下標(biāo)為14的位置稽煤，如：
從中可以看出核芽，如果有多個元素key的hash值相同的話，后一個元素并不會覆蓋上一個元素念脯，而是采取鏈表的方式狞洋，把之后加進(jìn)來的元素加入鏈表末尾，從而解決了hash沖突的問題绿店，由此我們知道HashMap中處理hash沖突的方法是鏈地址法吉懊，在此補(bǔ)充一個知識點庐橙，處理hash沖突的方法有以下幾種：
- 開放地址法
- 再哈希法
- 鏈地址法
- 建立公共溢出區(qū)
講到這里，重點來了借嗽，我們知道HashMap中默認(rèn)的存儲大小就是一個容量為16的數(shù)組态鳖，所以當(dāng)我們創(chuàng)建出一個HashMap對象時，即使里面沒有任何元素恶导，也要分別一塊內(nèi)存空間給它浆竭，而且，我們再不斷的向HashMap里put數(shù)據(jù)時惨寿，當(dāng)達(dá)到一定的容量限制時（這個容量滿足這樣的一個關(guān)系時候?qū)U(kuò)容：HashMap中的數(shù)據(jù)量>容量*加載因子邦泄，而HashMap中默認(rèn)的加載因子是0.75），HashMap的空間將會擴(kuò)大裂垦，而且擴(kuò)大后新的空間一定是原來的2倍顺囊，我們可以看put()方法中有這樣的一行代碼：
int newCapacity = oldCapacity * 2;
所以，重點就是這個蕉拢，只要一滿足擴(kuò)容條件特碳，HashMap的空間將會以2倍的規(guī)律進(jìn)行增大。假如我們有幾十萬晕换、幾百萬條數(shù)據(jù)午乓，那么HashMap要存儲完這些數(shù)據(jù)將要不斷的擴(kuò)容，而且在此過程中也需要不斷的做hash運算闸准，這將對我們的內(nèi)存空間造成很大消耗和浪費益愈，而且HashMap獲取數(shù)據(jù)是通過遍歷Entry[]數(shù)組來得到對應(yīng)的元素，在數(shù)據(jù)量很大時候會比較慢恕汇，所以在Android中腕唧，HashMap是比較費內(nèi)存的或辖，我們在一些情況下可以使用SparseArray和ArrayMap來代替HashMap瘾英。
SparseArray
SparseArray比HashMap更省內(nèi)存，在某些條件下性能更好颂暇，主要是因為它避免了對key的自動裝箱（int轉(zhuǎn)為Integer類型）缺谴，它內(nèi)部則是通過兩個數(shù)組來進(jìn)行數(shù)據(jù)存儲的，一個存儲key耳鸯，另外一個存儲value湿蛔，為了優(yōu)化性能，它內(nèi)部對數(shù)據(jù)還采取了壓縮的方式來表示稀疏數(shù)組的數(shù)據(jù)县爬，從而節(jié)約內(nèi)存空間阳啥，我們從源碼中可以看到key和value分別是用數(shù)組表示：
private int[] mKeys;
private Object[] mValues;
我們可以看到，SparseArray只能存儲key為int類型的數(shù)據(jù)财喳，同時察迟，SparseArray在存儲和讀取數(shù)據(jù)時候斩狱，使用的是二分查找法，我們可以看看：
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ù)的時候扎瓶，會使用二分查找法和之前的key比較當(dāng)前我們添加的元素的key的大小所踊，然后按照從小到大的順序排列好，所以概荷，SparseArray存儲的元素都是按元素的key值從小到大排列好的秕岛。
而在獲取數(shù)據(jù)的時候，也是使用二分查找法判斷元素的位置误证，所以继薛，在獲取數(shù)據(jù)的時候非常快愈捅，比HashMap快的多惋增，因為HashMap獲取數(shù)據(jù)是通過遍歷Entry[]數(shù)組來得到對應(yīng)的元素。
添加數(shù)據(jù)
public void put(int key, E value)
刪除數(shù)據(jù)
public void remove(int key)
or
public void delete(int key)
其實remove內(nèi)部還是通過調(diào)用delete來刪除數(shù)據(jù)的
獲取數(shù)據(jù)
public E get(int key)
or
public E get(int key, E valueIfKeyNotFound)
該方法可設(shè)置如果key不存在的情況下默認(rèn)返回的value
特有方法
在此之外改鲫，SparseArray還提供了兩個特有方法诈皿，更方便數(shù)據(jù)的查詢：
獲取對應(yīng)的key：
public int keyAt(int index)
獲取對應(yīng)的value：
public E valueAt(int index)
SparseArray應(yīng)用場景：
雖說SparseArray性能比較好，但是由于其添加像棘、查找稽亏、刪除數(shù)據(jù)都需要先進(jìn)行一次二分查找，所以在數(shù)據(jù)量大的情況下性能并不明顯缕题，將降低至少50%截歉。
滿足下面兩個條件我們可以使用SparseArray代替HashMap：
- 數(shù)據(jù)量不大，最好在千級以內(nèi)
- key必須為int類型烟零，這中情況下的HashMap可以用SparseArray代替：
HashMap<Integer, Object> map = new HashMap<>();
用SparseArray代替:
SparseArray<Object> array = new SparseArray<>();
ArrayMap
這個api的資料在網(wǎng)上可以說幾乎沒有瘪松，然并卵，只能看文檔了
ArrayMap是一個<key,value>映射的數(shù)據(jù)結(jié)構(gòu)锨阿，它設(shè)計上更多的是考慮內(nèi)存的優(yōu)化宵睦，內(nèi)部是使用兩個數(shù)組進(jìn)行數(shù)據(jù)存儲，一個數(shù)組記錄key的hash值墅诡，另外一個數(shù)組記錄Value值壳嚎，它和SparseArray一樣，也會對key使用二分法進(jìn)行從小到大排序末早，在添加烟馅、刪除、查找數(shù)據(jù)的時候都是先使用二分查找法得到相應(yīng)的index然磷，然后通過index來進(jìn)行添加郑趁、查找、刪除等操作姿搜，所以寡润，應(yīng)用場景和SparseArray的一樣缺脉，如果在數(shù)據(jù)量比較大的情況下，那么它的性能將退化至少50%悦穿。
添加數(shù)據(jù)
public V put(K key, V value)
獲取數(shù)據(jù)
public V get(Object key)
刪除數(shù)據(jù)
public V remove(Object key)
特有方法
它和SparseArray一樣同樣也有兩個更方便的獲取數(shù)據(jù)方法：
public K keyAt(int index)
public V valueAt(int index)
ArrayMap應(yīng)用場景
- 數(shù)據(jù)量不大攻礼，最好在千級以內(nèi)
- 數(shù)據(jù)結(jié)構(gòu)類型為Map類型
ArrayMap<Key, Value> arrayMap = new ArrayMap<>();
【注】：如果我們要兼容aip19以下版本的話，那么導(dǎo)入的包需要為v4包
import android.support.v4.util.ArrayMap;
總結(jié)
SparseArray和ArrayMap都差不多栗柒，使用哪個呢礁扮？
假設(shè)數(shù)據(jù)量都在千級以內(nèi)的情況下：
1、如果key的類型已經(jīng)確定為int類型瞬沦，那么使用SparseArray太伊，因為它避免了自動裝箱的過程，如果key為long類型逛钻，它還提供了一個LongSparseArray來確保key為long類型時的使用
2僚焦、如果key類型為其它的類型，則使用ArrayMap
