一、概論

????在移動設(shè)備端，內(nèi)存資源很珍貴，HashMap 為實現(xiàn)快速查詢帶來了很大內(nèi)存的浪費。為此，2013年5月20日 Google 工程師 Dianne Hackborn 在 Android 系統(tǒng)源碼中新增 ArrayMap 類，從 Android 源碼中發(fā)現(xiàn)有不少提交，專門把之前使用 HashMap 的地方改用 ArrayMap，不僅如此，大量的應(yīng)用開發(fā)者中也廣為使用。

ArrayMap 是 Android 專門針對內(nèi)存優(yōu)化而設(shè)計的，用于取代 Java API 中的 HashMap 數(shù)據(jù)結(jié)構(gòu)。

為了更進一步優(yōu)化 key 是 int 類型的 Map，Android 再次提供效率更高的數(shù)據(jù)結(jié)構(gòu) SparseArray，可避免自動裝箱過程。對于 key 為其他類型，則可以使用 ArrayMap。

HashMap 的查找和插入時間復(fù)雜度為 O(1) 的代價是犧牲大量的內(nèi)存來實現(xiàn)的，而 SparseArray 和 ArrayMap 性能略遜于 HashMap，但更節(jié)省內(nèi)存。
接下來帶著這幾個問題來學(xué)習(xí) ArrayMap的底層原理：

• 1）ArrayMap 與 HashMap 有什么差異
• 2）ArrayMap 的優(yōu)點與缺點
• 3）ArrayMap 與 HashMap 的取舍

二、源碼解析

2.1 基本成員變量

public final class ArrayMap<K, V> implements Map<K, V> {

    private static final boolean CONCURRENT_MODIFICATION_EXCEPTIONS = true;
    
    private static final int BASE_SIZE = 4;  // 容量增量的最小值
    private static final int CACHE_SIZE = 10; // 緩存數(shù)組的上限

    static Object[] mBaseCache; // 用于緩存大小為 4 的 ArrayMap    
    static Object[] mTwiceBaseCache; // 用于緩存大小為 8 的 ArrayMap
    
    static int mBaseCacheSize; // 緩存大小為 4 的 ArrayMap  的長度
    static int mTwiceBaseCacheSize; // 緩存大小為 8 的 ArrayMap  的長度

    final boolean mIdentityHashCode;
    int[] mHashes;         // 由 key 的 hashcode 所組成的數(shù)組
    Object[] mArray;       // 由 key-value 對所組成的數(shù)組，是 mHashes 大小的 2 倍
    int mSize;             // 成員變量的個數(shù)
}

ArrayMap 對象的數(shù)據(jù)儲存格式如下圖所示：

• mHashes 是一個記錄所有 key 的 hashcode 值組成的數(shù)組，是從小到大的排序方式
• mArray 是一個記錄著 key-value 鍵值對所組成的數(shù)組，是 mHashes 大小的2倍
  
  ArrayMap 對象的數(shù)據(jù)儲存格式

其中 mSize 記錄著該 ArrayMap 對象中有多少對數(shù)據(jù)，執(zhí)行 put() 或者 append() 操作，則 mSize 會加 1，執(zhí)行 remove()，則 mSize 會減 1。

mSize 往往小于 mHashes.length，如果 mSize 大于或等于 mHashes.length，則說明 mHashes 和 mArray 需要擴容。

ArrayMap 類有兩個非常重要的靜態(tài)成員變量 mBaseCache 和 mTwiceBaseCache，用于 ArrayMap 所在進程的全局緩存功能：

• mBaseCache：用于緩存大小為 4 的 ArrayMap，mBaseCacheSize 記錄著當(dāng)前已緩存的數(shù)量，超過 10 個則不再緩存
• mTwiceBaseCache：用于緩存大小為 8 的 ArrayMap，mTwiceBaseCacheSize 記錄著當(dāng)前已緩存的數(shù)量，超過 10 個則不再緩存。

為了減少頻繁地創(chuàng)建和回收 Map 對象，ArrayMap 采用了兩個大小為 10 的緩存隊列來分別保存大小為 4 和 8 的 Map 對象。為了節(jié)省內(nèi)存使用了更加保守的內(nèi)存擴張以及內(nèi)存收縮策略。 接下來分別說說緩存機制和擴容機制。

這也是 ArrayMap 所特有的，與HashMap不同，ArrayMap所具有的緩存機制。

2.2 緩存機制

????ArrayMap 是專為 Android 優(yōu)化而設(shè)計的 Map 對象，使用場景比較高頻，很多場景可能起初都是數(shù)據(jù)很少，為了減少頻繁地創(chuàng)建和回收，特意設(shè)計了兩個緩存池，分別緩存大小為 4 和 8 的 ArrayMap 對象。要理解緩存機制，那就需要看看內(nèi)存分配 (allocArrays) 和內(nèi)存釋放 (freeArrays)。

與其說這是兩個緩存池，不如說是兩個緩存鏈

2.2.1 ArrayMap.freeArrays

private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
    if (hashes.length == (BASE_SIZE*2)) {  // 當(dāng)釋放的是大小為 8 的對象
        synchronized (ArrayMap.class) {
            // 當(dāng)大小為 8 的緩存池的數(shù)量小于 10 個，則將其放入緩存池
            if (mTwiceBaseCacheSize < CACHE_SIZE) { 
                array[0] = mTwiceBaseCache;  // array[0] 指向原來的緩存池
                array[1] = hashes;
                for (int i=(size<<1)-1; i>=2; i--) {
                    array[i] = null;  // 清空其他數(shù)據(jù)
                }
                mTwiceBaseCache = array; // mTwiceBaseCache 指向新加入緩存池的 array
                mTwiceBaseCacheSize++; 
            }
        }
    } else if (hashes.length == BASE_SIZE) {  // 當(dāng)釋放的是大小為 4 的對象，原理同上
        synchronized (ArrayMap.class) {
            if (mBaseCacheSize < CACHE_SIZE) {
                array[0] = mBaseCache;
                array[1] = hashes;
                for (int i=(size<<1)-1; i>=2; i--) {
                    array[i] = null;
                }
                mBaseCache = array;
                mBaseCacheSize++;
            }
        }
    }
}

1. 最初 mTwiceBaseCache 和 mBaseCache 緩存池中都沒有數(shù)據(jù)，
2. 在 freeArrays 釋放內(nèi)存時，如果同時滿足釋放的 array 大小等于 4 或者 8
3. 且相對應(yīng)的緩沖池個數(shù)未達上限，則會把該 arrya 加入到緩存池中。

• 加入的方式是將數(shù)組 array 的第 0 個元素指向原有的緩存池，
• 第 1 個元素指向 hashes 數(shù)組的地址，
• 第 2 個元素以后的數(shù)據(jù)全部置為 null。
• 再把緩存池的頭部指向最新的 array 的位置，并將該緩存池大小執(zhí)行加 1 操作。具體如下所示。
  dn.net/liuwg1226/article/details/118885316

freeArray操作步驟

從這個步驟模型可以看出這是一個緩存鏈，每個數(shù)組的第0個元素都保存上一次的緩存。
ArrayMap 的 freeArrays() 的觸發(fā)條件：

• 當(dāng)執(zhí)行 removeAt() 移除最后一個元素的情況
• 當(dāng)執(zhí)行 clear() 清理的情況
• 當(dāng)執(zhí)行 ensureCapacity() 在當(dāng)前容量小于預(yù)期- 容量的情況下，先執(zhí)行 allocArrays，再執(zhí)行 freeArrays
• 當(dāng)執(zhí)行 put() 在容量滿的情況下，先執(zhí)行 allocArrays，再執(zhí)行 freeArrays

2.2.1 ArrayMap.allocArrays

private void allocArrays(final int size) {
    if (size == (BASE_SIZE*2)) {  // 當(dāng)分配大小為 8 的對象，先查看緩存池
        synchronized (ArrayMap.class) {
            if (mTwiceBaseCache != null) { // 當(dāng)緩存池不為空時
                final Object[] array = mTwiceBaseCache; 
                mArray = array;         // 從緩存池中取出 mArray
                mTwiceBaseCache = (Object[])array[0]; // 將緩存池指向上一條緩存地址
                mHashes = (int[])array[1];  // 從緩存中 mHashes
                array[0] = array[1] = null;
                mTwiceBaseCacheSize--;  // 緩存池大小減 1
                return;
            }
        }
    } else if (size == BASE_SIZE) { // 當(dāng)分配大小為 4 的對象，原理同上
        synchronized (ArrayMap.class) {
            if (mBaseCache != null) {
                final Object[] array = mBaseCache;
                mArray = array;
                mBaseCache = (Object[])array[0];
                mHashes = (int[])array[1];
                array[0] = array[1] = null;
                mBaseCacheSize--;
                return;
            }
        }
    }
    
    // 分配大小除了 4 和 8 之外的情況，則直接創(chuàng)建新的數(shù)組
    mHashes = new int[size];
    mArray = new Object[size<<1];
}

當(dāng) allocArrays 分配內(nèi)存時，如果所需要分配的大小等于 4 或者 8，且相對應(yīng)的緩沖池不為空，則會從相應(yīng)緩存池中取出緩存的 mArray 和 mHashes。

從緩存池取出緩存的方式是：

1. 將當(dāng)前緩存池賦值給 mArray，
2. 將緩存池指向上一條緩存地址，
3. 將緩存池的第 1 個元素賦值為 mHashes，
4. 再把 mArray 的第 0 和第 1 個位置的數(shù)據(jù)置為 null

5. 并將該緩存池大小執(zhí)行減 1 操作，具體如下所示。

   
   
   緩存鏈條獲取

ArrayMap 的 allocArrays 的觸發(fā)時機：

• 當(dāng)執(zhí)行 ArrayMap 的構(gòu)造函數(shù)的情況
• 當(dāng)執(zhí)行 removeAt() 在滿足容量收緊機制的情況
• 當(dāng)執(zhí)行 ensureCapacity() 在當(dāng)前容量小于預(yù)期容量的情況下，先執(zhí)行 allocArrays，再執(zhí)行 freeArrays
• 當(dāng)執(zhí)行 put() 在容量滿的情況下，先執(zhí)行 allocArrays，再執(zhí)行 freeArrays
  這里需要注意的是只有大小為 4 或者 8 的內(nèi)存分配，才有可能從緩存池取數(shù)據(jù)，因為 freeArrays 過程放入緩存池的大小只有 4 或 8，對于其他大小的內(nèi)存分配則需要創(chuàng)建新的數(shù)組。

優(yōu)化小技巧，對于分配數(shù)據(jù)不超過 8 的對象的情況下，一定要創(chuàng)建 4 或者 8 大小，否則浪費了緩存機制。比如 ArrayMap[7] 就是不友好的寫法，建議寫成 ArrayMap[8]。

2.3 容量機制

2.3.1 容量擴張

public V put(K key, V value) {
    final int osize = mSize;
    if (osize >= mHashes.length) { // 當(dāng) mSize 大于或等于 mHashes 數(shù)組長度時需要擴容
        final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))
                : (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
        allocArrays(n);  // 分配更大的內(nèi)存【小節(jié)2.2.2】
    }
}

當(dāng) mSize 大于或等于 mHashes 數(shù)組長度時，則擴容，完成擴容后需要將老的數(shù)組拷貝到新分配的數(shù)組，并釋放老的數(shù)組內(nèi)存。

• 當(dāng) map 個數(shù)滿足條件 osize<4 時，則擴容后的大小為 4
• 當(dāng) map 個數(shù)滿足條件 4<= osize < 8 時，則擴容后的大小為 8
• 當(dāng) map 個數(shù)滿足條件 osize>=8 時，則擴容后的大小為原來的 1.5 倍
  可見 ArrayMap 大小在不斷增加的過程，size 的取值一般情況依次會是 4，8，12，18，27，40，60，…

2.3.2 容量收緊

public V removeAt(int index) {
    final int osize = mSize;
    final int nsize;
    if (osize > 1) {  // 當(dāng) mSize 大于 1 的情況，需要根據(jù)情況來決定是否要收緊
        nsize = osize - 1;
        if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
            final int n = osize > (BASE_SIZE*2) ? (osize + (osize>>1)) : (BASE_SIZE*2);
            allocArrays(n); // 分配更小的內(nèi)存【小節(jié)2.2.2】
        } 
    }
}

當(dāng) mHashes 的大小大于 8，且已存儲數(shù)據(jù)的個數(shù) mSize 小于數(shù)組空間大小的 1/3 的情況下，需要收緊數(shù)據(jù)的內(nèi)容容量，分配新的數(shù)組，老的內(nèi)存靠虛擬機自動回收。

• 如果 mSize<=8，則設(shè)置新大小為 8
• 如果 mSize> 8，則設(shè)置新大小為 mSize 的1.5倍
  也就是說在 mHashes.length 較大的情況下，當(dāng) 使用量（mSize）不足 1/3 的情況下，內(nèi)存數(shù)組會收緊。

2.4 基本成員方法

2.4.1 構(gòu)造方法

public ArrayMap() {
    this(0, false);
}

// 指定初始容量大小
public ArrayMap(int capacity) {
    this(capacity, false);
}

/** {@hide} */ 這是一個隱藏方法
public ArrayMap(int capacity, boolean identityHashCode) {
    mIdentityHashCode = identityHashCode;

    if (capacity < 0) {
        mHashes = EMPTY_IMMUTABLE_INTS;
        mArray = EmptyArray.OBJECT;
    } else if (capacity == 0) {
        mHashes = EmptyArray.INT;
        mArray = EmptyArray.OBJECT;
    } else {
        allocArrays(capacity); // 分配內(nèi)存【小節(jié)2.2.2】
    }
    mSize = 0;  //初始值為0
}

public ArrayMap(ArrayMap<K, V> map) {
    this();
    if (map != null) {
        putAll(map);  
    }
}

public void putAll(Map<? extends K, ? extends V> map) {
    // 確保 map 的大小至少為 mSize + map.size()，如果默認已滿足條件則不用擴容
    ensureCapacity(mSize + map.size()); 
    for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
        put(entry.getKey(), entry.getValue());
    }
}

針對構(gòu)造方法，如果指定大小則會去分配相應(yīng)大小的內(nèi)存，如果沒有指定默認為 0，當(dāng)需要添加數(shù)據(jù)的時候再擴容。

2.4.2 put()

public V put(K key, V value) {
    final int osize = mSize; // osize 記錄當(dāng)前 map 大小
    final int hash;
    int index;
    if (key == null) {
        hash = 0;
        index = indexOfNull();
    } else {
        // 默認 mIdentityHashCode=false
        hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
        // 采用二分查找法，從 mHashes 數(shù)組中查找值等于 hash 的 key
        index = indexOf(key, hash); 
    }
    // 當(dāng) index 大于零，則代表的是從數(shù)據(jù) mHashes 中找到相同的 key，執(zhí)行的操作等價于修改相應(yīng)位置的 value
    if (index >= 0) {
        index = (index<<1) + 1;  // index 的 2 倍 +1 所對應(yīng)的元素存在相應(yīng) value 的位置
        final V old = (V)mArray[index];
        mArray[index] = value;
        return old;
    }

    // 當(dāng) index<0，則代表是插入新元素
    index = ~index;
    if (osize >= mHashes.length) { // 當(dāng) mSize 大于或等于 mHashes 數(shù)組長度時，需要擴容【小節(jié)2.3.1】
        final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))
                : (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);

        final int[] ohashes = mHashes;
        final Object[] oarray = mArray;
        allocArrays(n);  // 分配更大的內(nèi)存【小節(jié)2.2.2】

        // 由于 ArrayMap 并非線程安全的類，不允許并行，如果擴容過程其他線程調(diào)整 mSize 則拋出異常
        if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
            throw new ConcurrentModificationException();
        }

        if (mHashes.length > 0) {
            // 將原來老的數(shù)組拷貝到新分配的數(shù)組
            System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
            System.arraycopy(oarray, 0, mArray, 0, oarray.length);
        }
        freeArrays(ohashes, oarray, osize); // 釋放原來老的內(nèi)存【小節(jié)2.2.2】
    }

    // 當(dāng)需要插入的位置不在數(shù)組末尾時，需要將 index 位置后的數(shù)據(jù)通過拷貝往后移動一位
    if (index < osize) {
        System.arraycopy(mHashes, index, mHashes, index + 1, osize - index);
        System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
    }

    if (CONCURRENT_MODIFICATION_EXCEPTIONS) {
        if (osize != mSize || index >= mHashes.length) {
            throw new ConcurrentModificationException();
        }
    }
    // 將 hash、key、value 添加相應(yīng)數(shù)組的位置，數(shù)據(jù)個數(shù) mSize 加 1
    mHashes[index] = hash;
    mArray[index<<1] = key;
    mArray[(index<<1)+1] = value;
    mSize++; 
    return null;
}

put() 設(shè)計巧妙地將 修改已有數(shù)據(jù)對(key-value) 和 插入新的數(shù)據(jù)對 合二為一個方法，主要是依賴 indexOf() 過程中采用的 二分查找法，
當(dāng)找到相應(yīng) key 時則返回正值，當(dāng)找不到 key 則返回負值，
按位取反所對應(yīng)的值代表的是需要插入的位置 index。

put() 在插入時，如果當(dāng)前數(shù)組內(nèi)容已填充滿時，則會先進行擴容，再通過 System.arraycopy 來進行數(shù)據(jù)拷貝，最后在相應(yīng)位置寫入數(shù)據(jù)。

2.4.4 append()

public void append(K key, V value) {
    int index = mSize;
    final int hash = key == null ? 0
            : (mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());
    //使用append前必須保證mHashes的容量足夠大，否則拋出異常
    if (index >= mHashes.length) {
        throw new IllegalStateException("Array is full");
    }
    //當(dāng)數(shù)據(jù)需要插入到數(shù)組的中間，則調(diào)用put來完成
    if (index > 0 && mHashes[index-1] > hash) {
        put(key, value); // 【小節(jié)2.4.1】
        return;
    }
    //否則，數(shù)據(jù)直接添加到隊尾
    mSize = index+1;
    mHashes[index] = hash;
    index <<= 1;
    mArray[index] = key;
    mArray[index+1] = value;
}

append() 與 put() 類似，append 的差異在于，該方法不會去做擴容的操作，是一個輕量級的插入方法。

Q：那么什么場景適合使用 append() 方法呢？
A：應(yīng)就是對于明確知道肯定會插入隊尾的情況下使用 append() 性能更好，因為 put() 上來先做 binarySearchHashes() 二分查找，時間復(fù)雜度為 O(logN)，而 append() 的時間復(fù)雜度為 O(1)。

2.4.5 remove()

public V remove(Object key) {
    final int index = indexOfKey(key); // 通過二分查找 key 的 index
    if (index >= 0) {
        return removeAt(index); // 移除相應(yīng)位置的數(shù)據(jù)
    }
    return null;
}

public V removeAt(int index) {
    final Object old = mArray[(index << 1) + 1];
    final int osize = mSize;
    final int nsize;
    if (osize <= 1) {  // 當(dāng)被移除的是 ArrayMap 的最后一個元素，則釋放該內(nèi)存
        freeArrays(mHashes, mArray, osize);
        mHashes = EmptyArray.INT;
        mArray = EmptyArray.OBJECT;
        nsize = 0;
    } else {
        nsize = osize - 1;
        // 根據(jù)情況來收緊容量 【小節(jié)2.3.2】
        if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
            final int n = osize > (BASE_SIZE*2) ? (osize + (osize>>1)) : (BASE_SIZE*2);

            final int[] ohashes = mHashes;
            final Object[] oarray = mArray;
            allocArrays(n); // 分配一個更小內(nèi)存的容量

            // 禁止并發(fā)
            if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
                throw new ConcurrentModificationException();
            }

            if (index > 0) {
                System.arraycopy(ohashes, 0, mHashes, 0, index);
                System.arraycopy(oarray, 0, mArray, 0, index << 1);
            }
            if (index < nsize) {
                System.arraycopy(ohashes, index + 1, mHashes, index, nsize - index);
                System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1,
                        (nsize - index) << 1);
            }
        } else {
            if (index < nsize) { // 當(dāng)被移除的元素不是數(shù)組最末尾的元素時，則需要將后面的數(shù)組往前移動
                System.arraycopy(mHashes, index + 1, mHashes, index, nsize - index);
                System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1,
                        (nsize - index) << 1);
            }
            // 再將最后一個位置設(shè)置為 null
            mArray[nsize << 1] = null;
            mArray[(nsize << 1) + 1] = null;
        }
    }
    if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
        throw new ConcurrentModificationException();
    }
    mSize = nsize; // 大小減1
    return (V)old;
}

remove() 過程：通過二分查找 key 的 index，再根據(jù) index 來選擇移除動作；

• 當(dāng)被移除的是 ArrayMap 的最后一個元素，則釋放該內(nèi)存，
• 否則只做移除操作，這時會根據(jù)容量收緊原則來決定是否要收緊，當(dāng)需要收緊時會創(chuàng)建一個更小內(nèi)存的容量。

2.4.5 clear()

public void clear() {
    if (mSize > 0) { // 當(dāng)容量中元素不為空的情況 才會執(zhí)行內(nèi)存回收操作
        final int[] ohashes = mHashes;
        final Object[] oarray = mArray;
        final int osize = mSize;
        mHashes = EmptyArray.INT;
        mArray = EmptyArray.OBJECT;
        mSize = 0;
        freeArrays(ohashes, oarray, osize); //【小節(jié)2.2.1】
    }
    if (CONCURRENT_MODIFICATION_EXCEPTIONS && mSize > 0) {
        throw new ConcurrentModificationException();
    }
}

clear() 清理操作會執(zhí)行 freeArrays() 方法來回收內(nèi)存，而類似的方法 erase() 則只會清空數(shù)組內(nèi)的數(shù)據(jù)，并不會回收內(nèi)存。

三、缺陷分析

3.1 缺陷原因

由于 ArrayMap 是非線程安全的，除了靜態(tài)變量 mBaseCache 和 mTwiceBaseCache 加類鎖保護，其他成員變量并沒有保護?？赡苄薷?array[0] 的地方 put、append、removeAt、erase 等方法，此處省去分析過程，最終有兩種情況：

• 場景一：這條緩存數(shù)據(jù) array 在放入緩存池 (freeArrays) 后，被修改
• 場景二：剛從緩存池取出來 (allocArrays) 的同時，數(shù)據(jù)立刻被其他地方修改

從 [小節(jié)2.2.1] freeArrays() 可知，

1. 每一次放入緩存池 mBaseCache 時，一定會把 array[0] 指向 Object[] 類型的緩沖頭。
2. 并且 mBaseCache 的所有操作，都通過 synchronized 加鎖 ArrayMap.class 保護，不可能會有修改其他線程并發(fā)修改 mBaseCache。
3. 雖然 mBaseCache 會加鎖保護，但 mArray 并沒有加鎖保護。如果有機會把 mBaseCache 的引用傳遞出去，在其他地方修改的話是有可能出現(xiàn)問題的。

3.2 修復(fù)方案

Google 工程師 Suprabh Shukla 在 2018.5.14 提交修復(fù)方案，合入 Android 9.0 的代碼。方案的思路是利用局部變量保存 mArray，再斬斷對外的引用。修復(fù)代碼如下：

public V removeAt(int index) {
    final int osize = mSize;
    if (osize <= 1) {
        final int[] ohashes = mHashes; 
        final Object[] oarray = mArray;  // 利用局部變量 oarray 先保存 mArray
        mHashes = EmptyArray.INT;
        mArray = EmptyArray.OBJECT;      // 再將 mArray 引用置空
        freeArrays(ohashes, oarray, osize); 
        nsize = 0;
    } else {

**除了 removeAt()，其他調(diào)用 freeArrays() 的地方都會在調(diào)用之前先修改 mArray 內(nèi)容引用，從而不會干擾緩存回收的操作。

四、類比分析

4.1 HashMap

4.1.1 HashMap 概論

詳細的知識內(nèi)容可以參考之前的文章進行學(xué)習(xí)hashMap原理解析,這里進行以下簡要的概括：

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable
{
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4； // 默認初始大小為 16
    static final float DEFAULT_LOAD_FACTOR = 0.75； // 默認負載因子
    static final int TREEIFY_THRESHOLD = 8;  // 當(dāng)鏈表個數(shù)超過 8，則轉(zhuǎn)紅黑樹
    
    // 用于存放數(shù)據(jù)的核心數(shù)組，老版本是 HashMapEntry，
    transient Node<K,V>[] table； 
    transient int size; // 實際存儲的鍵值對的個數(shù)
    int threshold;  // 閾值，等于 capacity*loadFactory
    
    final float loadFactor = DEFAULT_LOAD_FACTOR; // 當(dāng)前負載因子
    transient int modCount;  // 用于檢測是否存在并發(fā)修改，transient 修飾則不會進入序列化
}

在不考慮哈希沖突的情況下，在哈希表中的增減、查找操作的時間復(fù)雜度為的 O(1)。
HashMap 是如何做到這么優(yōu)秀的 O(1) 呢？
核心在于哈希函數(shù)能將 key 直接轉(zhuǎn)換成哈希表中的存儲位置，而哈希表本質(zhì)是一個數(shù)組，在指定下標(biāo)的情況下查找數(shù)組成員是一步到位的。

hashMap

那么哈希函數(shù)設(shè)計的好壞，會影響哈希沖突的概率，進而影響哈希表查找的性能。為了解決哈希沖突，也就是兩個不同 key，經(jīng)過 hash 轉(zhuǎn)換后指向同一個 bucket，這時該 bucket 把相同 hash 值的 key 組成一個鏈表，每次插入鏈表的表頭。(頭插法)
可見 HashMap 是由數(shù)組+鏈表組成的，鏈表是為了處理哈希碰撞而存在的，所以鏈表出現(xiàn)得越少，其性能越好。

想想一種極端情況，所有 key 都發(fā)生碰撞，那么 HashMap 就退化成鏈表，其時間復(fù)雜度一下就退化到 O(n)，這時比 ArrayMap 的性能還差，從 Android sdk26 開始，當(dāng)鏈表長度超過 8 則轉(zhuǎn)換為紅黑樹，讓最壞情況的時間復(fù)雜度為 O(logn)。網(wǎng)上有大量介紹 HashMap 的資料，其中 table 是HashMapEntry<K,V>[]，那說明是老版本，新版為支持 RBTree 的功能，已切換到 Node 類。
用圖表示為：

4.1.1 HashMap 擴容機制

• 擴容觸發(fā)條件是當(dāng)發(fā)生哈希沖突，并且當(dāng)前實際鍵值對個數(shù)是否大于或等于閾值 threshold，默認為 0.75*capacity
• 擴容操作是針對哈希表 table 來分配內(nèi)存空間，每次擴容是至少是當(dāng)前大小的 2 倍，擴容的大小一定是 2^n。
• 另外，擴容后還需要將原來的數(shù)據(jù)都 transfer 到新的 table，同時計算新的ihash值，映射新的index下標(biāo)，這是耗時操作。

4.2 SparseArray

public class SparseArray<E> implements Cloneable {
    private static final Object DELETED = new Object();
    private boolean mGarbage = false; // 標(biāo)記是否存在待回收的鍵值對

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

SparseArray 對應(yīng)的 key 只能是 int 類型，它不會對 key 進行裝箱操作。它使用了兩個數(shù)組，一個保存 key，一個保存 value。 從內(nèi)存使用上來說，SparseArray 不需要保存 key 所對應(yīng)的哈希值，所以比 ArrayMap 還能再節(jié)省 1/3 的內(nèi)存。

SparseArray

SparseArray 使用二分查找來找到 key 對應(yīng)的插入位置，保證 mKeys 數(shù)組從小到大的排序。

4.2.1 SparseArray 的延遲回收機制

public void delete(int key) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    if (i >= 0) {
        if (mValues[i] != DELETED) {
            mValues[i] = DELETED;  // 標(biāo)記該數(shù)據(jù)為 DELETE
            mGarbage = true; // 設(shè)置存在 GC
        }
    }
}

當(dāng)執(zhí)行 delete() 或者 removeAt() 刪除數(shù)據(jù)的操作，只是將相應(yīng)位置的數(shù)據(jù)標(biāo)記為 DELETE，并設(shè)置 mGarbage=true，而不會直接執(zhí)行數(shù)據(jù)拷貝移動的操作。

當(dāng)執(zhí)行 clear() 會清空所有的數(shù)據(jù)，并設(shè)置 mGarbage=false；另外有很多時機(比如實際數(shù)據(jù)大于等于數(shù)組容量)都有可能會主動調(diào)用 gc() 方法來清理 DELETE 數(shù)據(jù)，代碼如下：

private void gc() {
    int n = mSize;
    int o = 0;
    int[] keys = mKeys;
    Object[] values = mValues;

    for (int i = 0; i < n; i++) {
        Object val = values[i];
        if (val != DELETED) { // 將所有沒有標(biāo)記為 DELETE 的 value 移動到隊列的頭部
            if (i != o) {
                keys[o] = keys[i];
                values[o] = val;
                values[i] = null;
            }
            o++;
        }
    }
    mGarbage = false; // 垃圾整理完成
    mSize = o;
}

延遲回收機制的好處在于：首先刪除方法效率更高，同時減少數(shù)組數(shù)據(jù)來回拷貝的次數(shù)，比如刪除某個數(shù)據(jù)后被標(biāo)記刪除，接著又需要在相同位置插入數(shù)據(jù)，則不需要任何數(shù)組元素的來回移動操作。可見，對于 SparseArray 適合頻繁刪除和插入來回執(zhí)行的場景，性能很好。

4.3 ArraySet

ArraySet 也是 Android 特有的數(shù)據(jù)結(jié)構(gòu)，用于替代 HashSet 的，跟 ArrayMap 出自同一個作者，從源碼來看 ArraySet 跟 ArrayMap 幾乎完全一致，包含緩存機制，擴容機制。唯一的不同在于 ArrayMap 是一個 key-value 鍵值對的集合，而 ArraySet 是一個集合，mArray[] 保存所有的 value 值，而 mHashes[] 保存相應(yīng) value 所對應(yīng)的hash 值。

當(dāng)然 ArraySet 也有 ArrayMap 一樣原理的缺陷，這一點 Google 修復(fù)如下：

private void allocArrays(final int size) {
    if (size == (BASE_SIZE * 2)) {
        ...
    } else if (size == BASE_SIZE) {
        synchronized (ArraySet.class) {
            if (sBaseCache != null) {
                final Object[] array = sBaseCache;
                try {
                    mArray = array;
                    sBaseCache = (Object[]) array[0];
                    mHashes = (int[]) array[1];
                    array[0] = array[1] = null;
                    sBaseCacheSize--;
                    return;
                } catch (ClassCastException e) {
                }
                // 從下面這段日志，可以看出谷歌工程師也發(fā)現(xiàn)了存在這個問題
                // Whoops!  Someone trampled the array (probably due to not protecting
                // their access with a lock).  Our cache is corrupt; report and give up.
                sBaseCache = null;
                sBaseCacheSize = 0;
            }
        }
    }

    mHashes = new int[size];
    mArray = new Object[size];
}

ArraySet

對于 ClassCastException 異常，這個有可能不是當(dāng)前 ArraySet 使用不到導(dǎo)致的，也無法追溯，所以谷歌直接 catch 住這個異常，然后把緩沖池清空，再創(chuàng)建數(shù)組。這樣可以解決問題，但這樣有什么不足嗎？ 這樣的不足在于當(dāng)發(fā)生異常時會讓緩存機制失效。

五、總結(jié)分析

從以下幾個角度進行總結(jié)分析：

數(shù)據(jù)結(jié)構(gòu)

• ArrayMap 和 SparseArray 采用的都是兩個數(shù)組，Android 專門針對內(nèi)存優(yōu)化而設(shè)計的
• HashMap 采用的是數(shù)據(jù)+鏈表+紅黑樹

內(nèi)存優(yōu)化

• ArrayMap 比 HashMap 更節(jié)省內(nèi)存，綜合性能方面在數(shù)據(jù)量不大的情況下，推薦使用 ArrayMap
• Hash 需要創(chuàng)建一個額外對象來保存每一個放入 map 的 entry（數(shù)組），且容量的利用率比 ArrayMap 低，整體更消耗內(nèi)存
• SparseArray 比 ArrayMap 節(jié)省 1/3 的內(nèi)存，但 SparseArray 只能用于 key 為 int 類型的 Map，所以 int 類型的 Map 數(shù)據(jù)推薦使用 SparseArray

性能方面

• ArrayMap 查找時間復(fù)雜度 O(logN)；ArrayMap 增加、刪除操作需要移動成員，速度相比較慢，對于個數(shù)小于 1000 的情況下，性能基本沒有明顯差異
• HashMap 查找、修改的時間復(fù)雜度為 O(1)；
• SparseArray 適合頻繁刪除和插入來回執(zhí)行的場景，性能比較好

緩存機制

• ArrayMap 針對容量為 4 和 8 的對象進行緩存，可避免頻繁創(chuàng)建對象而分配內(nèi)存與 GC 操作，這兩個緩存池大小的上限為 10 個，防止緩存池?zé)o限增大
• HashMap 沒有緩存機制
• SparseArray 有延遲回收機制，提供刪除效率，同時減少數(shù)組成員來回拷貝的次數(shù)

擴容機制

• ArrayMap 是在容量滿的時機觸發(fā)容量擴大至原來的 1.5 倍，在容量不足 1/3 時觸發(fā)內(nèi)存收縮至原來的 0.5 倍，更節(jié)省的內(nèi)存擴容機制
• HashMap 是在容量的 0.75 倍時觸發(fā)容量擴大至原來的 2 倍，且沒有內(nèi)存收縮機制。HashMap 擴容過程有 - hash 重建，相對耗時。所以能大致知道數(shù)據(jù)量，可指定創(chuàng)建指定容量的對象，能減少性能浪費

并發(fā)問題

• ArrayMap 是非線程安全的類，大量方法中通過對 mSize 判斷是否發(fā)生并發(fā)，來決定拋出異常。但沒有覆蓋到所有并發(fā)場景，比如大小沒有改變而成員內(nèi)容改變的情況就沒有覆蓋
• HashMap 是在每次增加、刪除、清空操作的過程將 modCount 加 1，在關(guān)鍵方法內(nèi)進入時記錄當(dāng)前 mCount，執(zhí)行完核心邏輯后，再檢測 mCount 是否被其他線程修改，來決定拋出異常。這一點的處理比 ArrayMap 更有全面

回到一開始的那幾個問題，我們來簡單回答一下：

• ArrayMapa和HashMap的區(qū)別？

1. ArrayMap的存在是為了解決HashMap占用內(nèi)存大的問題，它內(nèi)部使用了一個int數(shù)組用來存儲元素的hashcode，使用了一個Object數(shù)組用來存儲元素，兩者根據(jù)索引對應(yīng)形成key-value結(jié)構(gòu)，這樣就不用像HashMap那樣需要額外的創(chuàng)建Entry對象來存儲，減少了內(nèi)存占用。
2. 但是在數(shù)據(jù)量比較大時，ArrayMap的性能就會遠低于HashMap,因為ArrayMap基于二分查找算法來查找元素的，并目數(shù)組的插入操作如果不是末尾的話需要挪動數(shù)組元素，效率較低。
3. 而HashMap內(nèi)部基于數(shù)組+單向鏈表+紅黑樹實現(xiàn)，也是key-value結(jié)構(gòu)，正如剛才提到的，HashMap每put一個元素都需要創(chuàng)建一個Enty來存放元素，導(dǎo)致它的內(nèi)存占用會比較大，但是在大數(shù)據(jù)量的時候，因為HashMap中當(dāng)出現(xiàn)沖突時，沖突的數(shù)據(jù)量大于8，就會從單向鏈表轉(zhuǎn)換成紅黑樹，而紅黑樹的插入、刪除、查找的時間復(fù)雜度為O(logn),相對于ArrayMapl的數(shù)組而言在插入和刪除操作上要快不少，所以數(shù)據(jù)量上百的情況下，使用HashMap:會有更高的效率。

在ArrayMap中，假設(shè)存在沖突的話，并不會像HashMap那樣使用單向鏈表或紅黑樹來保留這些沖突的元素，而是全部key、value都存儲到一個數(shù)組當(dāng)中，然后查找的話通過二分查找進行，這也就是當(dāng)數(shù)據(jù)量大時不宜用ArrayMap的原因了。