Android內存優化(使用SparseArray和ArrayMap代替HashMap)

Android內存優化(使用SparseArray和ArrayMap代替HashMap),在Android開發時,我們使用的大部分都是Java的api,比如HashMap這個api,使用率非常高,但是對於android這種對內存非常敏感的移動平臺,很多時候使用一些java的api並不能達到更好的性能,相反反而更消耗內存,所以針對Android這種移動平臺,也推出瞭更符合自己的api,比如SparseArray、ArrayMap用來代替HashMap在有些情況下能帶來更好的性能提升。

介紹它們之前先來介紹一下HashMap的內部存儲結構,就明白為什麼推薦使用SparseArray和ArrayMap

HashMap

HashMap內部是使用一個默認容量為16的數組來存儲數據的,而數組中每一個元素卻又是一個鏈表的頭結點,所以,更準確的來說,HashMap內部存儲結構是使用哈希表的拉鏈結構(數組+鏈表),如圖:
這種存儲數據的方法叫做拉鏈法。

且每一個結點都是Entry類型,那麼Entry是什麼呢?我們來看看HashMap中Entry的屬性:

final K key;
V value;
final int hash;
HashMapEntry next;

從中我們得知Entry存儲的內容有key、value、hash值、和next下一個Entry,那麼,這些Entry數據是按什麼規則進行存儲的呢?就是通過計算元素key的hash值,然後對HashMap中數組長度取餘得到該元素存儲的位置,計算公式為hash(key)%len,比如:假設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的這三個元素存儲在數組下標為14的位置。

從中可以看出,如果有多個元素key的hash值相同的話,後一個元素並不會覆蓋上一個元素,而是采取鏈表的方式,把之後加進來的元素加入鏈表末尾,從而解決瞭hash沖突的問題,由此我們知道HashMap中處理hash沖突的方法是鏈地址法,在此補充一個知識點,處理hash沖突的方法有以下幾種:

開放地址法
再哈希法
鏈地址法
建立公共溢出區
講到這裡,重點來瞭,我們知道HashMap中默認的存儲大小就是一個容量為16的數組,所以當我們創建出一個HashMap對象時,即使裡面沒有任何元素,也要分別一塊內存空間給它,而且,我們再不斷的向HashMap裡put數據時,當達到一定的容量限制時(這個容量滿足這樣的一個關系時候將會擴容:HashMap中的數據量>容量*加載因子,而HashMap中默認的加載因子是0.75),HashMap的空間將會擴大,而且擴大後新的空間一定是原來的2倍,我們可以看put()方法中有這樣的一行代碼:

int newCapacity = oldCapacity * 2;

所以,重點就是這個,隻要一滿足擴容條件,HashMap的空間將會以2倍的規律進行增大。假如我們有幾十萬、幾百萬條數據,那麼HashMap要存儲完這些數據將要不斷的擴容,而且在此過程中也需要不斷的做hash運算,這將對我們的內存空間造成很大消耗和浪費,而且HashMap獲取數據是通過遍歷Entry[]數組來得到對應的元素,在數據量很大時候會比較慢,所以在Android中,HashMap是比較費內存的,我們在一些情況下可以使用SparseArray和ArrayMap來代替HashMap。

SparseArray

SparseArray比HashMap更省內存,在某些條件下性能更好,主要是因為它避免瞭對key的自動裝箱(int轉為Integer類型),它內部則是通過兩個數組來進行數據存儲的,一個存儲key,另外一個存儲value,為瞭優化性能,它內部對數據還采取瞭壓縮的方式來表示稀疏數組的數據,從而節約內存空間,我們從源碼中可以看到key和value分別是用數組表示:

    private int[] mKeys;
    private Object[] mValues;

我們可以看到,SparseArray隻能存儲key為int類型的數據,同時,SparseArray在存儲和讀取數據時候,使用的是二分查找法,我們可以看看:

 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添加數據的時候,會使用二分查找法和之前的key比較當前我們添加的元素的key的大小,然後按照從小到大的順序排列好,所以,SparseArray存儲的元素都是按元素的key值從小到大排列好的。
而在獲取數據的時候,也是使用二分查找法判斷元素的位置,所以,在獲取數據的時候非常快,比HashMap快的多,因為HashMap獲取數據是通過遍歷Entry[]數組來得到對應的元素。

添加數據

public void put(int key, E value)

刪除數據

 public void remove(int key)

or

public void delete(int key)

其實remove內部還是通過調用delete來刪除數據的

獲取數據

public E get(int key)

or

public E get(int key, E valueIfKeyNotFound)

該方法可設置如果key不存在的情況下默認返回的value

特有方法

在此之外,SparseArray還提供瞭兩個特有方法,更方便數據的查詢:
獲取對應的key:

public int keyAt(int index)

獲取對應的value:

public E valueAt(int index)

SparseArray應用場景:

雖說SparseArray性能比較好,但是由於其添加、查找、刪除數據都需要先進行一次二分查找,所以在數據量大的情況下性能並不明顯,將降低至少50%。

滿足下面兩個條件我們可以使用SparseArray代替HashMap:

數據量不大,最好在千級以內
key必須為int類型,這中情況下的HashMap可以用SparseArray代替:

HashMap map = new HashMap<>();
用SparseArray代替:
SparseArray array = new SparseArray<>();

ArrayMap

這個api的資料在網上可以說幾乎沒有,然並卵,隻能看文檔瞭
ArrayMap是一個

添加數據

public V put(K key, V value)

獲取數據

public V get(Object key)

刪除數據

public V remove(Object key)

特有方法

它和SparseArray一樣同樣也有兩個更方便的獲取數據方法:

public K keyAt(int index)
public V valueAt(int index)

ArrayMap應用場景

數據量不大,最好在千級以內 數據結構類型為Map類型

ArrayMap arrayMap = new ArrayMap<>();

【註】:如果我們要兼容aip19以下版本的話,那麼導入的包需要為v4包

import android.support.v4.util.ArrayMap;

總結

SparseArray和ArrayMap都差不多,使用哪個呢?
假設數據量都在千級以內的情況下:

1、如果key的類型已經確定為int類型,那麼使用SparseArray,因為它避免瞭自動裝箱的過程,如果key為long類型,它還提供瞭一個LongSparseArray來確保key為long類型時的使用

2、如果key類型為其它的類型,則使用ArrayMap

You May Also Like