Android內存優化：ArrayMap

通常我們在使用key-value存儲數據時，隨手就會打出HashMap的代碼，當數據量較小時，還可以，當數量比較多的時候，如果是PC機上，也還說得過去，但是如果使用設備是手機等移動設備，這是就要慎重了。因為手機的內存非常寶貴，不像PC那樣不計後果的使用，內存使用不當很容易就會引起OOM的問題。那Android開發團隊，也為我們找到了HashMap的替代品ArrayMap。

官方對ArrayMap也有說明：它不是一個適應大數據的數據結構，相比傳統的HashMap速度要慢，因為查找方法是二分法，並且當你刪除或者添加數據時，會對空間重新調整，在使用大量數據時，效率並不明顯，低於50%。

所以ArrayMap是犧牲了時間換區空間。在寫手機app時，適時的使用ArrayMap，會給內存使用帶來可觀的提升。

那HashMap和ArrayMap到底不同在哪呢，個人總結有以下方面：

1、存儲方式不同。

HashMap內部有一個HashMapEntry[]對象，每一個鍵值對都存儲在這個對象裡，當使用put方法添加鍵值對時，就會new一個HashMapEntry對象

 

    @Override public V put(K key, V value) {
        if (key == null) {
            return putValueForNullKey(value);
        }

        int hash = secondaryHash(key);
        HashMapEntry[] tab = table;
        int index = hash & (tab.length - 1);
		//先查找有沒有對應的key值，如果有，就改寫value，並返回改寫前的value值：oldValue
        for (HashMapEntry e = tab[index]; e != null; e = e.next) {
            if (e.hash == hash && key.equals(e.key)) {
                preModify(e);
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
        }

        // No entry for (non-null) key is present; create one
        modCount++;
        if (size++ > threshold) {
			//擴容，雙倍
            tab = doubleCapacity();
            index = hash & (tab.length - 1);
        }
        addNewEntry(key, value, hash, index);
        return null;
    }
	//創建對象存儲鍵值對
    void addNewEntry(K key, V value, int hash, int index) {
        table[index] = new HashMapEntry(key, value, hash, table[index]);
    }

ArrayMap的存儲中沒有Entry這個東西，他是由兩個數組來維護的

 

 

    int[] mHashes;
    Object[] mArray;

mHashes數組中保存的是每一項的HashCode值，mArray中就是鍵值對，每兩個元素代表一個鍵值對，前面保存key，後面的保存value，我們看看下面代碼的結果

 

 

		arraymap = new HashMap();
		a.put(a, a_value);
		a.put(b, b_value);

執行上面代碼後，arraymap中的存儲是這樣的

 

是不是能清楚地看到ArrayMap的存儲了，這種存儲在put代碼中如下

 

        mHashes[index] = hash;
        mArray[index<<1] = key;
        mArray[(index<<1)+1] = value;

2、添加數據時擴容時的處理不一樣

 

先來看看HashMap

 

        if (size++ > threshold) {
            tab = doubleCapacity();
            index = hash & (tab.length - 1);
        }

doubleCapacity進行雙倍擴容，它的代碼中有這麼一句話

 

 

HashMapEntry[] newTable = makeTable(newCapacity);

最終，這個newTable將作為擴容後的新對象返回，那麼makeTable做了什麼呢，如下：

 

 

    private HashMapEntry[] makeTable(int newCapacity) {
        @SuppressWarnings(unchecked) HashMapEntry[] newTable
                = (HashMapEntry[]) new HashMapEntry[newCapacity];
        table = newTable;
        threshold = (newCapacity >> 1) + (newCapacity >> 2); // 3/4 capacity
        return newTable;
    }

我們清楚地看到，這裡進行了new操作，重新創建對象，開銷很大。

 

那麼ArrayMap呢，看看吧

 

        //如果容量不夠
		if (mSize >= mHashes.length) {
            final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
                    : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);

            if (DEBUG) Log.d(TAG, put: grow from  + mHashes.length +  to  + n);

            final int[] ohashes = mHashes;
            final Object[] oarray = mArray;
        //分配數組
            allocArrays(n);

            if (mHashes.length > 0) {
                if (DEBUG) Log.d(TAG, put: copy 0- + mSize +  to 0);
                //特別注意這，是copy，而不是new，效率提升
                System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
                System.arraycopy(oarray, 0, mArray, 0, oarray.length);
            }
                //釋放無用空間，收縮數組
            freeArrays(ohashes, oarray, mSize);
        }

 

ArrayMap用的是copy數據，所以效率相對要高。

 

3、ArrayMap提供了數組收縮的功能，在clear或remove後，會重新收縮數組，是否空間

4、ArrayMap采用二分法查找（見 android.support.v4.util.ContainerHelpers中的binarySearch方法）