HashMap SparseArray ArrayMap

程式記憶體的管理是否合理高效對應用的性能有着很大的影響，有的時候對容器的使用不當也會導緻記憶體管理效率低下。Android為移動作業系統特意編寫了一些更加高效的容器，例如SparseArray，ArrayMap。

我們經常會使用到HashMap這個容器，它非常好用，但是卻很占用記憶體。

HashMap

HashMap内部是使用一個預設容量為16的數組來存儲資料的，而數組中每一個元素卻又是一個連結清單的頭結點，是以，更準确的來說，HashMap内部存儲結構是使用哈希表的拉鍊結構（數組+連結清單）這種存儲資料的方法叫做拉鍊法 

我們知道HashMap中預設的存儲大小就是一個容量為16的數組，是以當我們建立出一個HashMap對象時，即使裡面沒有任何元素，也要分别一塊記憶體空間給它，而且，我們再不斷的向HashMap裡put資料時，當達到一定的容量限制時（這個容量滿足這樣的一個關系時候将會擴容：HashMap中的資料量>容量*加載因子，而HashMap中預設的加載因子是0.75），HashMap的空間将會擴大，而且擴大後新的空間一定是原來的2倍，我們可以看put()方法中有這樣的一行代碼：

int newCapacity = oldCapacity * 2;
           

是以，重點就是這個，隻要一滿足擴容條件，HashMap的空間将會以2倍的規律進行增大。假如我們有幾十萬、幾百萬條資料，那麼HashMap要存儲完這些資料将要不斷的擴容，而且在此過程中也需要不斷的做hash運算，這将對我們的記憶體空間造成很大消耗和浪費，而且HashMap擷取資料是通過周遊Entry[]數組來得到對應的元素，在資料量很大時候會比較慢， 為了解決HashMap更占記憶體的弊端，Android提供了記憶體效率更高的SparseArray和ArrayMap。它内部使用兩個數組進行工作，其中一個數組記錄key hash過後的順序清單，另外一個數組按key的順序記錄Key-Value值。

SparseArray

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

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

我們可以看到，SparseArray隻能存儲key為int類型的資料，同時，SparseArray在存儲和讀取資料時候，使用的是二分查找法，也就是在put添加資料的時候，會使用二分查找法和之前的key比較目前我們添加的元素的key的大小，然後按照從小到大的順序排列好，是以，SparseArray存儲的元素都是按元素的key值從小到大排列好的。 

而在擷取資料的時候，也是使用二分查找法判斷元素的位置，是以，在擷取資料的時候非常快，比HashMap快的多，因為HashMap擷取資料是通過周遊Entry[]數組來得到對應的元素。

SparseArray應用場景：

資料量不大，最好在千級以内

key必須為int類型，這中情況下的HashMap可以用SparseArray代替：

ArrayMap

當你想擷取某個value的時候，ArrayMap會計算輸入key轉換過後的hash值，然後對hash數組使用二分查找法尋找到對應的index，然後我們可以通過這個index在另外一個數組中直接通路到需要的鍵值對。如果在第二個數組鍵值對中的key和前面輸入的查詢key不一緻，那麼就認為是發生了碰撞沖突。為了解決這個問題，我們會以該key為中心點，分别上下展開，逐個去對比查找，直到找到比對的值。

随着數組中的對象越來越多，查找通路單個對象的花費也會跟着增長，這是在記憶體占用與通路時間之間做權衡交換。

ArrayMap的插入與删除的效率是不夠高的，但是如果數組的清單隻是在一百這個數量級上，則完全不用擔心這些插入與删除的效率問題。

與HashMap相比，ArrayMap在循環周遊的時候也更加簡單高效

//ArrayMap
        for (int i=0;i<map.size();i++){
            Object keyAt=map.keyAt(i);
            Object valueAt=map.valueAt(i);
            ...
        }
       
        //HashMap
        for(Iterator it=map.keySet().iterator();it.hasNext();){
            Object next = it.next();
            ...
        };
           

ArrayMap應用場景：

前面講了很多ArrayMap的優點，但并不是所有情況下都适合使用ArrayMap，我們應該在滿足下面2個條件的時候才考慮使用ArrayMap：

對象個數的數量級最好是千以内；

資料組織形式包含Map結構。

SparseArray和ArrayMap

假設資料量都在千級以内的情況下：

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

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