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

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

• 由兩個數(shù)組組成，一個int[] mHashes用來存放Key的hash值，一個Object[] mArrays用來連續(xù)存放成對的Key和Value
• mHashes數(shù)組按非嚴格升序排列
• 初始默認容量為0
• 減容：
  • 刪除元素后如果當(dāng)前mHashes長度比BASE_SIZE*2大，但總元素個數(shù)又沒到當(dāng)前容量的 1/3 就減容
• 擴容：
  • 插入元素時，如果需要擴容：
  • 如果當(dāng)前長度大于8，就按1.5倍擴容
  • 如果當(dāng)前長度大于4，小于8，就擴容到8
  • 如果當(dāng)前長度小于4，擴容到4
• 由于使用了hash，可能存在哈希沖突，結(jié)局方式：將相同的hash的key連續(xù)存放
• mHashes的index和Key、Value的下標(biāo)對應(yīng)關(guān)系
  • key = mArrays[index*2] –> key = mArrays[index << 1]
  • value = mArrays[index*2 +1] --> value = mArrays[index<<1+1]

public final class ArrayMap<K, V> implements Map<K, V> {@UnsupportedAppUsage(maxTargetSdk = 28) // Hashes are an implementation detail. Use public key/value API.int[] mHashes;@UnsupportedAppUsage(maxTargetSdk = 28) // Storage is an implementation detail. Use public key/value API.Object[] mArray;@UnsupportedAppUsage(maxTargetSdk = 28) // Use size()int mSize;//擴容的判斷條件private static final int BASE_SIZE = 4;}

2. 插入

• public V put(K key, V value)

ArrayMap和HashMap一樣，允許Key為null，且其hash默認置為0，且可以通過判空或者equals()來進行Hash沖突時，對目標(biāo)Key的判斷。在插入時，主要做了：

1. 找到Key所在的mHashes下標(biāo)
2. 如果之前已經(jīng)添加過，直接覆蓋value
3. 如果之前沒有添加過，插入元素（可能需要先擴容）

@Override
public V put(K key, V value) {final int osize = mSize;final int hash;int index;if (key == null) {//key=null的時候認為hash=0，HashMap也是這樣設(shè)計的！hash = 0;//根據(jù)key=null去尋找合適的index//----------解釋(1)----------index = indexOfNull();} else {//如果key不為空，就可以獲取一個hash值，可以用系統(tǒng)的方法，也可以用這個對象本身的hashcode()hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();//由于可能用到對象本身的hashcode()這久無法避免出現(xiàn)hash沖突//通過hash和key來查找合適的下標(biāo)。為了避免hash沖突，還把key放進來了，可以通過equals()來處理hash沖突//----------解釋(2)----------index = indexOf(key, hash);}//假設(shè)index找到了，是個正數(shù)，說明之前已經(jīng)添加過這個key的元素了，直接對value進行替換！if (index >= 0) {//放在index/2+1的位置index = (index << 1) + 1;//把舊數(shù)據(jù)返回出去final V old = (V) mArray[index];//新數(shù)據(jù)填入mArray[index] = value;return old;}//如果之前沒有添加過這個Key的元素，這下要添加，就要移動數(shù)組后續(xù)部分//index又取反回來，得到了之前找的最后一步end所在的位置，也就是需要插入的位置index = ~index;//如果需要擴容if (osize >= mHashes.length) {//1. 如果舊size超過了 base_size*2，那么新的大小為 osize * 1.5;//2. 如果還沒超過 base_size*2://2.1 如果超過了 base_size， 那么新大小直接定為 base_size * 2;//2.2 否則，新大小直接定為 base_sizefinal int n =osize >= (BASE_SIZE * 2) ?(osize + (osize >> 1)) : (osize >= BASE_SIZE ? (BASE_SIZE * 2) : BASE_SIZE);final int[] ohashes = mHashes;//原來的hash數(shù)組final Object[] oarray = mArray;//原來的元素實體數(shù)組//根據(jù) n 去申請一個新的數(shù)組//----------解釋(3)----------allocArrays(n);if (mHashes.length > 0) {//把原來的值賦值填充到新的數(shù)組上去System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);System.arraycopy(oarray, 0, mArray, 0, oarray.length);}//“起死回生”，嘗試將無用的原有數(shù)組用作緩存，如果不能用作緩存，就直接釋放不管了//----------解釋(3)----------freeArrays(ohashes, oarray, osize);}//判斷是否需要擴容，并完成需要的擴容之后，開始插入元素//1. 平移一下，讓出位置if (index < osize) {if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (osize - index)+ " to " + (index + 1));//元素的hash是一個接一個的，所以只需要挪動一個位置即可System.arraycopy(mHashes, index, mHashes, index + 1, osize - index);//但是元素本身存儲，需要連著存儲其key和value，占用兩個數(shù)組單元，// 所以挪動的時候，需要將hash個數(shù)對應(yīng)兩倍的個數(shù)進行挪動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();}}//2. 插入數(shù)據(jù)//可以看出來，index*2和 index*2+1連續(xù)兩個位置，存放著key和value！// 也就是不用額外造一個對象，而是直接兩個數(shù)據(jù)一起填入//mArray放的是數(shù)據(jù)[key0,value0,key1,value1,...,keyN,valueN,...]//mHashes則是在對應(yīng)index存放key的hash值mHashes[index] = hash;mArray[index << 1] = key;mArray[(index << 1) + 1] = value;//更新mSizemSize++;//由于并沒有把誰“覆蓋掉”，所以不需要返回oldValue，直接返回null即可return null;
}

在此之前，認為讀者已經(jīng)熟知SparseArray的源碼，了解其中的按位取反~設(shè)計、二分查找設(shè)計的思想。來看一下插入的大概流程：

解釋(1)

• indexOfNull()

可以看到，如果要插入的Key為null，需要在mHashes中查找hash=0的元素位置。除了null的hash=0，其他元素的hash也有可能為0，所以需要進行hash沖突情況下的key查找：

int indexOfNull() {final int N = mSize;if (N == 0) {//~~0可以得到接下來可以插入的位置（為0）return ~0;}//先找hash=0是否存在int index = binarySearchHashes(mHashes, N, 0);//如果之前都沒有插入過hash=0的元素，直接返回一個負數(shù)//~index可以得到接下來可以插入的位置if (index < 0) {return index;}//如果存在hash=0，那么就找到對應(yīng)的Key，如果是null，就對了if (null == mArray[index << 1]) {return index;}//如果存在hash=0，但是對應(yīng)的key不是null，說明存在hash沖突int end;//index為Key的hash在mHashes[]中的下標(biāo)//end<<1 = end*2 即定位到mArrays中Key的位置//由于相同的hash在mHashes[]中是連續(xù)存放的，所以只需要向左向右遍歷判斷Key是否一致即可//從index處的key開始向右遍歷判斷for (end = index + 1; end < N && mHashes[end] == 0; end++) {//如果找到了一個Key為null，就返回這個indexif (null == mArray[end << 1]) return end;}//如果找到結(jié)尾了都沒找到，就往前找for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) {if (null == mArray[i << 1]) return i;}//如果整個mArrays[]都沒有null這個key，就返回一個負數(shù)表示沒有找到return ~end;
}

需要注意的是，二分查找找到一個hash，它不一定是一組連續(xù)相同hash的第一個index。

例如我們要查的Key的hash=10，相同的Key應(yīng)當(dāng)在mArrays中下標(biāo)為2位置：

首先根據(jù)Key的hash值來快速定位Key的大致位置

• 二分發(fā)現(xiàn)值為10的hash在mHashes數(shù)組中下標(biāo)index為2，其對應(yīng)的Key的下標(biāo)為index*2也就是4

進行hash沖突判斷

• 發(fā)現(xiàn)在mArrays中index=4的Key，并不是我們要找的Key（發(fā)生了hash沖突）

接下來就要在這一組相同hash中查找和目標(biāo)Key一樣的Key

• 先向右遍歷查找，找到了在mArrays中index=6的Key，但仍然不是我們要找的Key（假設(shè)我們要找的Key應(yīng)當(dāng)是mArrays中index=2的Key）
• 然后在向左遍歷查找，最后找到了在mArrays中index=2的Key

如果在這一組相同hash中都查不到和目標(biāo)Key一樣的Key，就返回一個負數(shù)~end，表示之前并沒有差如果這個Key。而且這個~end如果外界再次按位取反~~end就可以得到如果要插入該元素，應(yīng)該插在哪個下標(biāo)位置，進而移動數(shù)組，插入元素。

解釋(2)

• indexOf(Object key,int hash)

它的hash沖突處理方式與上述 解釋(1) 中的思路一致。區(qū)別是傳入?yún)?shù)，key是用來處理在hash沖突的情況下，找到正確的key。

hash直接使用的是key這個類自身的hashcode()或者系統(tǒng)的hash算法，不做額外處理：

hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
index = indexOf(key, hash);

還有一個區(qū)別是比較Key時不再為比較null，而是使用key.equals()來比較：

//hash為原始哈希值，可能是系統(tǒng)的，也可能是用戶自定義hashcode()的，
// key可以用來equals()來判斷處理哈希沖突
@UnsupportedAppUsage(maxTargetSdk = 28)
int indexOf(Object key, int hash) {final int N = mSize;//如果一個元素都沒有，直接返回負數(shù)，找不到，下一個插入的mHashes[]的位置為0if (N == 0) {//從0變?yōu)?-2^32return ~0;}//如果數(shù)組非空，就可以進行二分查找來找到下標(biāo)//需要注意的是，ArrayMap的int[] mHashes是用來存儲keys的hash的//通過它的下標(biāo)位置*2(+1)可以得到Key和Value在mArrays[]中的位置。//由于使用了hash，所以需要處理hash沖突，ArrayMap將相同的hash連續(xù)存放在mHashes[]中，可以遍歷這一組hash對應(yīng)的key來查找目標(biāo)Key// 也就是不論K的類型是什么，都以其hashcode作為key，升序保存//底層通過ContainerHelper來二分查找，如果是負數(shù)，說明沒找到//但是對該負數(shù)按位取反可以得到最后一個檢索到的下標(biāo)int index = binarySearchHashes(mHashes, N, hash);//如果沒找到，返回一個負數(shù)if (index < 0) {return index;}//如果之前插入的key有這個hash值的，那么定位到這個Key所在的位置（index*2)if (key.equals(mArray[index << 1])) {//如果沒有hash沖突，這個位置就是我們要找的key，直接返回return index;}int end;//ArrayMap將相同的hash連續(xù)存放在mHashes[]中，可以遍歷這一組hash對應(yīng)的key來查找目標(biāo)Key//mHashes[]從index+1開始往后找相同hash對應(yīng)的Keyfor (end = index + 1; end < N && mHashes[end] == hash; end++) {if (key.equals(mArray[end << 1])) return end;}//由于二分定位到的hash的下標(biāo)可能是這一組相同hash的中間某個元素，所以也要往前找一找for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {if (key.equals(mArray[i << 1])) return i;}//如果還是沒找到，返回一個負數(shù)//~~end=end，可以用作插入的下標(biāo)return ~end;
}

解釋(3)

• allocArrays(int size)

如果要擴容，就要根據(jù)新的長度去申請一塊新的數(shù)組。源碼中也發(fā)現(xiàn)了，擴容的邏輯是：

• 如果舊size超過了8，就按1.5倍來擴容
• 如果舊size在4和8之間，擴容到8
• 如果舊size小于4，擴容到4

@UnsupportedAppUsage(maxTargetSdk = 28)
private void allocArrays(final int size) {if (mHashes == EMPTY_IMMUTABLE_INTS) {throw new UnsupportedOperationException("ArrayMap is immutable");}//如果需要擴容到8if (size == (BASE_SIZE * 2)) {synchronized (sTwiceBaseCacheLock) {if (mTwiceBaseCache != null) {//緩存（長度為4*2=8），不要再另外申請開辟空間了，這個緩存來自 freeArrays()final Object[] array = mTwiceBaseCache;//直接使用緩存空間mArray = array;try {mTwiceBaseCache = (Object[]) array[0];mHashes = (int[]) array[1];if (mHashes != null) {//如果都是空，就可用，returnarray[0] = array[1] = null;mTwiceBaseCacheSize--;return;}} catch (ClassCastException e) {}mTwiceBaseCache = null;mTwiceBaseCacheSize = 0;}}} else if (size == BASE_SIZE) {//如果新容量為4synchronized (sBaseCacheLock) {if (mBaseCache != null) {//使用緩存(長度為4)，來自freeArrays()final Object[] array = mBaseCache;mArray = array;try {mBaseCache = (Object[]) array[0];mHashes = (int[]) array[1];if (mHashes != null) {array[0] = array[1] = null;mBaseCacheSize--;return;}} catch (ClassCastException e) {}mBaseCache = null;mBaseCacheSize = 0;}}}//如果擴容到更大的容量，或者緩存不可用，就新申請一塊空間mHashes = new int[size];mArray = new Object[size << 1];
}

由于開辟一個數(shù)組需要時間，對于只需要容量為4和8的兩種情況，直接嘗試復(fù)用即可，復(fù)用緩存的情況一般出現(xiàn)在減容的過程中，因為擴容時總會經(jīng)歷擴容到4和8的情況。減容時可以復(fù)用之前被free掉的4和8容量的緩存。超過8容量的擴容直接申請新的數(shù)組即可。

解釋(4)

put()過程中，如果需要擴容，緊接著就到了freeArrays()，釋放原有的數(shù)組。如果被釋放的數(shù)組長度為4或者8就分別緩存到mBaseCache和mTwiceBaseCache，更大的就不管了。這個緩存可以被 解釋(3) 使用。

@UnsupportedAppUsage(maxTargetSdk = 28) // Allocations are an implementation detail.
private static void freeArrays(final int[] hashes, final Object[] array, final int size) {//如果要釋放的數(shù)組元素長度為8if (hashes.length == (BASE_SIZE * 2)) {synchronized (sTwiceBaseCacheLock) {if (mTwiceBaseCacheSize < CACHE_SIZE) {//原有mArrays[0]轉(zhuǎn)為指向mTwiceBaseCache，第一次為nullarray[0] = mTwiceBaseCache;//原有mArrays[1]轉(zhuǎn)為指向hashes數(shù)組array[1] = hashes;//將mArrays中剩余元素置空for (int i = (size << 1) - 1; i >= 2; i--) {//將原有元素置空array[i] = null;}//這個mArrays[]被拿來復(fù)用，由mTwiceBaseCache記錄//每個ArrayMap允許有一個mTwiceBaseCache實例mTwiceBaseCache = array;//總緩存數(shù)+1,是類變量，全局唯一，避免整個進程出現(xiàn)過多的緩存mTwiceBaseCacheSize++;}}} else if (hashes.length == BASE_SIZE) {//如果要釋放的數(shù)組元素長度為4synchronized (sBaseCacheLock) {if (mBaseCacheSize < CACHE_SIZE) {//原有mArrays[0]轉(zhuǎn)為指向mBaseCache，第一次為nullarray[0] = mBaseCache;//原有mArrays[1]轉(zhuǎn)為指向hashes數(shù)組array[1] = hashes;//將mArrays中剩余元素置空for (int i = (size << 1) - 1; i >= 2; i--) {array[i] = null;}//這個mArrays[]被拿來復(fù)用，由mBaseCache記錄//每個ArrayMap允許有一個mBaseCache實例mBaseCache = array;//總緩存數(shù)+1,是類變量，全局唯一，避免整個進程出現(xiàn)過多的緩存mBaseCacheSize++;}}}
}

需要注意的是，整個進程中，mBaseCache和mTwiceBaseCache的數(shù)量都不允許超過 10。假設(shè)原先數(shù)組長度為4，但是需要擴容到8，則需要釋放的兩個數(shù)組被作為緩存，這個緩存的結(jié)構(gòu)如下圖所示：

可以通過arrayMap.mBaseCache訪問到被緩存的mArrays和mHashes，但mBaseCache在一個進程中不允許超過10個，mTwiceBaseCache也是一樣的。

需要注意的是，這里的mHashes并沒有清空，而mArrays被清空了。筆者認為有兩個原因：

• 原因之一就是處理內(nèi)存泄漏，mArrays對元素都是強引用，需要主動置空釋放引用。mHashes沒有引用問題，所以不用釋放。

• 另一個原因就是在減容的過程中，如果復(fù)用了緩存，將會把新的數(shù)據(jù)填充進去，原先的mHashes的值會被覆蓋，所以不用額外耗費精力去清空mHashes。

3. 刪除

• V remove(Object key)
• V removeAt(int index)

根據(jù)key刪除元素，如果元素存在，將Value返回出去。刪除元素過程中可能發(fā)生減容!!! 需要注意的是mHashes.length 和 mSize 是不同的。 mSize是真實元素個數(shù)， mHashes.length是容量。

如果發(fā)生了減容，并且減容后的容量為4或者8，就可能復(fù)用緩存。復(fù)用緩存的時候可以會把舊數(shù)組的數(shù)據(jù)拷貝進去。

@Override
public V remove(Object key) {//根據(jù)key找到元素在mHashes的下標(biāo)，如果沒找到返回負數(shù)final int index = indexOfKey(key);if (index >= 0) {//找到了該key在mHashes中的下標(biāo)，根據(jù)index來刪除元數(shù)，并返回value值return removeAt(index);}return null;
}//刪除元素
public V removeAt(int index) {//越界判斷if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) {throw new ArrayIndexOutOfBoundsException(index);}//記錄一下 舊Valuefinal Object old = mArray[(index << 1) + 1];//舊sizefinal int osize = mSize;//計算新sizefinal int nsize;if (osize <= 1) {//刪完后，為空// Now empty.//舊 mHashes[]final int[] ohashes = mHashes;//舊 mArrays[]final Object[] oarray = mArray;mHashes = EmptyArray.INT;mArray = EmptyArray.OBJECT;//嘗試將原有數(shù)組標(biāo)為緩存?zhèn)溆?#xff08;如果原數(shù)組容量為4或8，且全局緩存不超過10個）freeArrays(ohashes, oarray, osize);nsize = 0;} else {//如果刪完還剩下元素nsize = osize - 1;//如果空間浪費過多，就減容！//需要注意的是mHashes.length 和 mSize 是不同的。 mSize是真實元素個數(shù)， mHashes.length是容量if (mHashes.length > (BASE_SIZE * 2) && mSize < mHashes.length / 3) {//如果當(dāng)前容量比BASE_SIZE*2來的大，但真實元素個數(shù)又沒到當(dāng)前容量的1/3//就減容！！！ 核心目的就是為了減少內(nèi)存消耗final int n = osize > (BASE_SIZE * 2) ? (osize + (osize >> 1)) : (BASE_SIZE * 2);//舊數(shù)據(jù)final int[] ohashes = mHashes;final Object[] oarray = mArray;//申請一塊減容后長度的數(shù)組//如果減容后發(fā)現(xiàn)n=4或者8，可以嘗試直接使用緩存allocArrays(n);if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {throw new ConcurrentModificationException();}//拷貝時，就不拷貝該元素//先把這個元素之前的拷貝進去if (index > 0) {if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0");System.arraycopy(ohashes, 0, mHashes, 0, index);System.arraycopy(oarray, 0, mArray, 0, index << 1);}//再把這個元素之后的元素拷貝進去if (index < nsize) {if (DEBUG) Log.d(TAG, "remove: copy from " + (index + 1) + "-" + nsize+ " to " + index);System.arraycopy(ohashes, index + 1, mHashes, index, nsize - index);System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1,(nsize - index) << 1);}} else {//如果不需要減容，就把后續(xù)的元素往前拷貝一位就夠了，把要刪除的元素覆蓋掉if (index < nsize) {if (DEBUG) Log.d(TAG, "remove: move " + (index + 1) + "-" + nsize+ " to " + index);System.arraycopy(mHashes, index + 1, mHashes, index, nsize - index);System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1,(nsize - index) << 1);}//將最后一位清空，防止引用錯誤、以及輔助GCmArray[nsize << 1] = null;mArray[(nsize << 1) + 1] = null;}}if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {throw new ConcurrentModificationException();}//更新最新長度mSize = nsize;//返回舊的數(shù)據(jù)return (V) old;
}

4. 查找

• V get(Object key)

插入部分分析完之后，剩下的邏輯就非常簡單了。查找的邏輯就兩步，根據(jù)key查找元素的hash所在mHashes[]的下標(biāo)index，其Value位置對應(yīng)為index*2+1

@Override
public V get(Object key) {//查找Key的hash在mHashes[]中的下標(biāo)final int index = indexOfKey(key);//如果沒找到，返回null，如果找到了，返回valuereturn index >= 0 ? (V) mArray[(index << 1) + 1] : null;
}

5. 根據(jù)index查找Key或者Value

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

這部分代碼也非常好理解，先是防越界（這里的界不是容量的界，而是真實數(shù)據(jù)的界，為什么要這樣呢？因為有可能用到緩存，mHashes中，不再mSize范圍中的部分會有臟數(shù)據(jù)！）然后就是根據(jù)下標(biāo)計算拿到在mArrays中的Key或者Value

public K keyAt(int index) {if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) {// The array might be slightly bigger than mSize, in which case, indexing won't fail.// Check if exception should be thrown outside of the critical path.throw new ArrayIndexOutOfBoundsException(index);}return (K) mArray[index << 1];
}public V valueAt(int index) {if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) {// The array might be slightly bigger than mSize, in which case, indexing won't fail.// Check if exception should be thrown outside of the critical path.throw new ArrayIndexOutOfBoundsException(index);}return (V) mArray[(index << 1) + 1];
}

6. append() 插入

• ``append(K key, V value)`

和SparseArray的設(shè)計類似，如果連續(xù)插入hash遞增的Key的元素，每次都二分查找效率是不夠的，允許直接和當(dāng)前最大hash值做判斷。要么在末尾插入，要么二分查找合適的插入位置。

@UnsupportedAppUsage(maxTargetSdk = 28) // Storage is an implementation detail. Use put(K, V).
public void append(K key, V value) {int index = mSize;//先拿到key的hash值final int hash = key == null ? 0: (mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());if (index >= mHashes.length) {//如果插入會發(fā)生越界，直接報錯，不會智能地去擴容throw new IllegalStateException("Array is full");}if (index > 0 && mHashes[index - 1] > hash) {//如果key小，就正常的putput(key, value);return;}//否則，直接在最右邊插入新元素即可mSize = index + 1;mHashes[index] = hash;index <<= 1;mArray[index] = key;mArray[index + 1] = value;
}

9. 遍歷ArrayMap

• K keyAt(int index)
• V valueAt(int index)
• int size()

在Parcel.writeArrayMapInternal()中的使用：

final int N = map.size();
for(int i = 0; i < N ; i++){writeString(map.keyAt(i));writeValue(map.valueAt(i));
}

8. validate()

• validate()

使用append()可能導(dǎo)致ArrayMap失效，因為可能存在一樣的Key出現(xiàn)在多處，invalidate()方法可以判斷這個ArrayMap是否合法，如果有多處相同Key的問題存在，就拋出錯誤。主要用途還是用于判斷經(jīng)過IPC的unpack后的ArrayMap是否合法。也是因為IPC通信在發(fā)送端可能會有并發(fā)問題。

Android中的Bundle數(shù)據(jù)就是用ArrayMap來存儲的

BaseBundle.mMap是ArrayMap<String,Object>類型的

最后會將mMap的數(shù)據(jù)寫入Parcel

parcel.writeArrayMapInternal(map)

public void validate() {final int N = mSize;//如果只有一個元素，不可能出現(xiàn)重復(fù)Key的情況if (N <= 1) {// There can't be dups.return;}//需要前后比較hash是否相同，所以要先拿到第一個的hash值int basehash = mHashes[0];int basei = 0;for (int i = 1; i < N; i++) {int hash = mHashes[i];//如果遍歷到的hash和前一個不一樣if (hash != basehash) {//更新basehash = hash;basei = i;continue;}//如果hash一樣，說明當(dāng)時插入的時候出現(xiàn)了hash沖突// 這就需要檢查Key是否equals()了//先拿到cur = Keyfinal Object cur = mArray[i << 1];//從hash沖突的index開始往前看，是否存在相同的Keyfor (int j = i - 1; j >= basei; j--) {final Object prev = mArray[j << 1];if (cur == prev) {//如果Key相同，說明之前出現(xiàn)了并發(fā)錯誤throw new IllegalArgumentException("Duplicate key in ArrayMap: " + cur);}if (cur != null && prev != null && cur.equals(prev)) {//如果都是非空元素，但是Key相同，說明之前出現(xiàn)了并發(fā)錯誤throw new IllegalArgumentException("Duplicate key in ArrayMap: " + cur);}}//如果一切正常，這個方法就不會拋出任何異常。}
}

總結(jié)

ArrayMap與SparseArray、HashMap、TreeMap的時間復(fù)雜度分析：

任務(wù)	ArrayMap	說明	SparseArray	HashMap
刪除	O(N)	數(shù)組拷貝	O(logN)	O(1)
順序插入	O(1) or O(N)	O(1):append直接放在最后 O(N):移動數(shù)組	O(1) or O(N)	O(1)
隨機插入	O(logN) or O(N)	O(N):插入前可能要移動數(shù)組 O(logN)：二分查找插入位置	O(logN) or O(N)	O(1)
逆序插入	O(N)	O(logN):二分查找插入位置 O(N):必然要移動數(shù)組元素	O(N)	O(1)
更新	O(logN)	O(logN)：如果需要更新已存在的元素，只要二分查找的時間	O(logN)	O(1)

再來測算一下內(nèi)存占用：

//TreeMap
Entry<K,V> root;// 21 * N Byte
class Entry<K,V>{//至少21 ByteK key;//4 ByteV value;//4 ByteEntry<K,V> left;//4 ByteEntry<K,V> right;//4 ByteEntry<K,V> parent;//4 Byteboolean color = BLACK;//1 Byte
}
//HashMap
Node<K,V>[] table;//16 * N Byte
class Node<K,V>{//至少16 Bytefinal int hash;//4 Bytefinal K key;//4 ByteV value;//4 ByteNode<K,V> next;//4 Byte
}
//SparseArray
int[] mKeys;//4 * N Byte
Object[] mValues;//4 * N Byte
//ArrayMap
int[] mHashes;//4 * N Byte
Object[] mArrays;//4 * 2* N Byte

如果不考慮緩存等內(nèi)存占用：

• TreeMap一個元素至少占用 21 Byte
• HashMap一個元素至少占用 16 Byte
• SparseArray一個元素至少占用 8 Byte
• ArrayMap一個元素至少占用 12 Byte

ArrayMap雖然內(nèi)存占用比SparseArray多，但其Key可以為任意類型，不局限于Integer，在這個情況下，與Key為任意類型的HashMap相比，又減少了許多內(nèi)存占用。

所以，如果沒有速度需求，盡量減少內(nèi)存占用時：

• 如果Key為int類型，就使用SparseArray
• 如果Key為任意類型，就使用ArrayMap

隨機插入的情況下，在10_000數(shù)據(jù)量下，HashMap、SparseArray、ArrayMap的執(zhí)行速度差別并不大。