不再害怕面試問ArrayMap一文完全看懂Android ArrayMap原始碼解析
前言
ArrayMap是谷歌推出的在安卓等裝置上用於替代HashMap的資料結構，和HashMap相比，具有更高的記憶體使用率，因此適合在Android等記憶體較為緊張的移動裝置，下面結合原始碼分析ArrayMap實現原理，主要分為新增資料、查詢資料、刪除資料以及快取四部分，注意本文基於api29。
正文
建構函式
首先先來來康康ArrayMap的建構函式如下： ``` /* {@hide} / public ArrayMap(int capacity, boolean identityHashCode) { mIdentityHashCode = identityHashCode;
// If this is immutable, use the sentinal EMPTY_IMMUTABLE_INTS
// instance instead of the usual EmptyArray.INT. The reference
// is checked later to see if the array is allowed to grow.
if (capacity < 0) {
mHashes = EMPTY_IMMUTABLE_INTS;
mArray = EmptyArray.OBJECT;
} else if (capacity == 0) {
mHashes = EmptyArray.INT;
mArray = EmptyArray.OBJECT;
} else {
allocArrays(capacity);
}
mSize = 0;
}
```
初始化了兩個空陣列，其中mHashes是用來升序存放key的hash值，mArrays 是用來存放key和value的，所以的mArrays的長度是mHashes的兩倍，key和value是緊挨著存放的，如果將key所對應的hash在mHashes的位置記作為index，key在 mArrays 中的位置記作 keyIndex,value在 mArrays 中的位置記作valueIndex,他們之間有如下關係:
keyIndex = index<<1,valueIndex= index<<1+1= keyIndex+1,如下圖：
新增資料
新增資料主要看下put方法,提取部分關鍵程式碼如下： ```java public V put(K key, V value) { final int osize = mSize; final int hash; int index; if (key == null) { hash = 0; //關鍵程式碼1 index = indexOfNull(); } else { hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode(); //關鍵程式碼2 index = indexOf(key, hash); } //關鍵程式碼3 if (index >= 0) { index = (index<<1) + 1; final V old = (V)mArray[index]; mArray[index] = value; return old; } //關鍵程式碼4 index = ~index; if (osize >= mHashes.length) { //關鍵程式碼5 final int n = osize >= (BASE_SIZE2) ? (osize+(osize>>1)) : (osize >= BASE_SIZE ? (BASE_SIZE2) : BASE_SIZE); final int[] ohashes = mHashes; final Object[] oarray = mArray; allocArrays(n);
if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
throw new ConcurrentModificationException();
}
if (mHashes.length > 0) {
if (DEBUG) Log.d(TAG, "put: copy 0-" + osize + " to 0");
System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
System.arraycopy(oarray, 0, mArray, 0, oarray.length);
}
freeArrays(ohashes, oarray, osize);
}
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();
}
}
//關鍵程式碼6
mHashes[index] = hash;
mArray[index<<1] = key;
mArray[(index<<1)+1] = value;
mSize++;
return null;
} ```
這個時候假設我們通過put給ArayMap新增一個key為null的值，這裡null的hash值為0，如下：
```
ArrayMap
會走到註釋關鍵程式碼1處的indexOfNull(),如下：
int indexOfNull() {
final int N = mSize;
if (N == 0) {
return ~0;
}
int index = binarySearchHashes(mHashes, N, 0);
if (index < 0) {
return index;
}
if (null == mArray[index<<1]) {
return index;
}
int end;
for (end = index + 1; end < N && mHashes[end] == 0; end++) {
if (null == mArray[end << 1]) return end;
}
for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) {
if (null == mArray[i << 1]) return i;
}
return ~end;
} ```
由於這個時候ArraMap還是空的，因此mSize=0,直接返回~0，這個時候走到了關鍵程式碼4，對返回的結果再次取反，index= ~index,index等於0,由於此時ArrayMap是空的，流程走到了關鍵程式碼5，開始給ArrayMap擴容，可以知道經過擴容mHashs的長度為4，mArray的長度為8，繼續往下走到關鍵程式碼6,插入資料，插入完成之後，ArrayMap的結構示意圖如下:
接下來我們來再來看看對於一個不空的 ArryMap 是怎樣執行插入邏輯的,假設ArryMap現有資料如下圖:
此時再往裡面插入資料key4/value4,假設4的hash值為20，這事流程走到關鍵程式碼2的 indexOf 函式，最終走到了ContainerHelper的binarySearch(),見名知義通過二分查詢找key4的hash值20對應的位置，程式碼如下：
```
static int binarySearch(int[] array, int size, int value) {
int lo = 0;
int hi = size - 1;
while (lo <= hi) {
final int mid = (lo + hi) >>> 1;
final int midVal = array[mid];
if (midVal < value) {
lo = mid + 1;
} else if (midVal > value) {
hi = mid - 1;
} else {
return mid;
}
}
return ~lo;
} ``` 顯然mHashes裡面找不到，返回~lo,注意此時lo的值為2，可以發現這個2就是key4的hash值的正確插入位置,對lo取反返回,取反是為了能夠走到關鍵程式碼4,關鍵程式碼4對返回值再次取反，獲得key4的hash值的正確插入位置，走到了關鍵程式碼7，為key4的插入騰出空間，就是比20大的往後面挪動一位,最後到關鍵程式碼6執行插入，插入之後，如下圖所示：
衝突解決
假設當前 ArayMap 資料如下：
此時再往裡面插入資料key4/value4,假設4的hash值為15，這事流程走到關鍵程式碼2的 indexOf 函式，最終走到了ContainerHelper的binarySearch(),通過二分查詢找key4的hash值15對應的位置為1：
int indexOf(Object key, int hash) {
final int N = mSize;
if (N == 0) {
return ~0;
}
//註釋1 index=1
int index = binarySearchHashes(mHashes, N, hash);
if (index < 0) {
return index;
}
//註釋2
if (key.equals(mArray[index<<1])) {
return index;
}
int end;
//註釋3
for (end = index + 1; end < N && mHashes[end] == hash; end++) {
//註釋4
if (key.equals(mArray[end << 1])) return end;
}
for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
//註釋5
if (key.equals(mArray[i << 1])) return i;
}
return ~end;
}
如上程式碼註釋1，此時index為1，走到註釋2，通過index<<1所以得到key2,顯然key4不等於key2,走到註釋3處，找到了key4的的插入位置為2，如果走到註釋4的return,說明從當前index往後遍歷key4已經存在的的值，直接返回索引，否則的話就往前遍歷，如果走到註釋5的return說明key4已經存在直接返回更新(因為採用的是二分查詢，找到的index在此過程中可能會跨過若干個hash值等於15的書其中可能包含等於key的的資料)如果都沒有返回end的取反走到插入資料關鍵程式碼4的邏輯，插入之後，資料如下：
刪除資料
呼叫remove方法最終會走到removeAt，程式碼如下：
``` public V removeAt(int index) { //註釋1 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); }
final Object old = mArray[(index << 1) + 1];
final int osize = mSize;
final int nsize;
//註釋2
if (osize <= 1) {
// Now empty.
if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0");
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
mHashes = EmptyArray.INT;
mArray = EmptyArray.OBJECT;
freeArrays(ohashes, oarray, osize);
nsize = 0;
} else {
nsize = osize - 1;
//註釋3
if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
final int n = osize > (BASE_SIZE*2) ? (osize + (osize>>1)) : (BASE_SIZE*2);
if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n);
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
allocArrays(n);
if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
throw new ConcurrentModificationException();
}
//註釋4 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 { //註釋5 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); } //註釋6 mArray[nsize << 1] = null; mArray[(nsize << 1) + 1] = null; } } if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) { throw new ConcurrentModificationException(); } mSize = nsize; return (V)old; } ```
註釋1處如果index大於當前ArrayMap的size，丟擲陣列越界，註釋2如果當前的size小於等於1，直接將mHashes和mArrays置空，然後釋放記憶體。註釋3處如果mHashes的長度大於兩倍的BASE_SIZE也就是8並且ArrayMap的size小於 mHashes 的長度三分之一，這個時候記憶體利用率不高，觸發收縮邏輯，開始對mHashes和mArrays進行收縮，節省記憶體，具體的收縮策略是如果當前的size大於8那麼就把陣列長度設為size的1.5倍，否則就是8，這樣的好處是避免size在兩倍的BASE_SIZE和BASE_SIZE之間頻繁的擴容和收縮，影響效能。邏輯走到註釋4也就是刪除兩個陣列中與index對應的資料即把index前面和後面的資料移動到一起。註釋5處說明沒有觸發收縮邏輯，把index後面的資料往前移動一位，末尾的資料置空。
取資料
看下get函式：
@Override
public V get(Object key) {
final int index = indexOfKey(key);
return index >= 0 ? (V)mArray[(index<<1)+1] : null;
}
比較簡單，就是通過key二分查詢index,如果index大於0，直接返回找到的值否則返回null
快取資料
ArrayMap為了避免頻繁GC，會對陣列進行快取，以便複用，快取分為插入快取與取快取
插入快取
插入快取的程式碼在freeArrays,主要在擴容和刪除收縮的時候觸發如下： ``` private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
if (hashes.length == (BASE_SIZE*2)) {
synchronized (ArrayMap.class) {
if (mTwiceBaseCacheSize < CACHE_SIZE) {
array[0] = mTwiceBaseCache;
array[1] = hashes;
for (int i=(size<<1)-1; i>=2; i--) {
array[i] = null;
}
mTwiceBaseCache = array;
mTwiceBaseCacheSize++;
if (DEBUG) Log.d(TAG, "Storing 2x cache " + array
+ " now have " + mTwiceBaseCacheSize + " entries");
}
}
} else if (hashes.length == BASE_SIZE) {
synchronized (ArrayMap.class) {
if (mBaseCacheSize < CACHE_SIZE) {
//註釋1
array[0] = mBaseCache;
array[1] = hashes;
註釋2
for (int i=(size<<1)-1; i>=2; i--) {
array[i] = null;
}
註釋2
mBaseCache = array;
mBaseCacheSize++;
if (DEBUG) Log.d(TAG, "Storing 1x cache " + array
+ " now have " + mBaseCacheSize + " entries");
}
}
}
} ``` 可以看到只對長度為BASE_SIZE以及兩倍BASE_SIZE進行快取，快取的大小為10，mBaseCacheSize為當前快取大小，mBaseCache以長度BASE_SIZE為例，mBaseCache為上次快取的長度為BASE_SIZE的mArrays,註釋1處將array的第0位賦值為上次快取的mArrays,第1位賦值為mHashs,然後註釋2處將array後面的值全部置空，更新mBaseCache，mBaseCacheSize加1，如此反覆，最後BASE_SIZE快取結構如圖，其實感覺就是一個變形的連結串列，如圖：
取快取
邏輯在allocArrays,程式碼如下： ``` private void allocArrays(final int size) { if (mHashes == EMPTY_IMMUTABLE_INTS) { throw new UnsupportedOperationException("ArrayMap is immutable"); } if (size == (BASE_SIZE*2)) { synchronized (ArrayMap.class) { if (mTwiceBaseCache != null) { final Object[] array = mTwiceBaseCache; mArray = array; mTwiceBaseCache = (Object[])array[0]; mHashes = (int[])array[1]; array[0] = array[1] = null; mTwiceBaseCacheSize--; if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes + " now have " + mTwiceBaseCacheSize + " entries"); return; } } } else if (size == BASE_SIZE) { synchronized (ArrayMap.class) { //註釋1 判空 if (mBaseCache != null) { //註釋2 取出當前mBaseCache指向的快取 final Object[] array = mBaseCache; mArray = array; //註釋3 mBaseCache指向下一個快取 mBaseCache = (Object[])array[0]; mHashes = (int[])array[1]; //註釋4 清理資料 array[0] = array[1] = null; //註釋5 快取的大小減一 mBaseCacheSize--; if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes + " now have " + mBaseCacheSize + " entries"); return; } } }
mHashes = new int[size];
mArray = new Object[size<<1];
} ``` 註釋寫的很清楚，這裡就不在贅述。
總結
ArrayMap 根據官方文件的定義就是為了更加有效的利用記憶體，從原始碼剖析可以看出無論從插入資料的的擴容策略還是刪除資料的回收策略都是儘可能的減小大容量的申請，並且增加快取提高記憶體利用率,另外無論是插入刪除還是查詢都涉及的二分查詢以及陣列搬運，因此效率較低，因此要區分不同的使用場景來選擇是使用ArrayMap還是HashMap。打完收工，如果覺得對您有幫助記得點個贊加個關注