前面介紹過(guò)HashMap和SparseArray的原理，今天簡(jiǎn)單看一下另一種數(shù)據(jù)結(jié)構(gòu)，ArrayMap。實(shí)際上ArrayMap和SparseArray都是二分查找，它們的查詢時(shí)間復(fù)雜度都是O(log n)。兩者的數(shù)據(jù)結(jié)構(gòu)存在差異，SparseArray是維持兩個(gè)Object類(lèi)型的數(shù)組，分別存放key和value，ArrayMap是維持一個(gè)int類(lèi)型的hash數(shù)組，用于排序和搜索，和一個(gè)Object類(lèi)型的數(shù)組，同時(shí)存放key和value。為了避免對(duì)象的頻繁創(chuàng)建和回收，ArrayMap可以最多維持大小為4和8的兩種緩存數(shù)組各10個(gè)。
構(gòu)造函數(shù)
首先看一下ArrayMap有兩個(gè)數(shù)組，一個(gè)int類(lèi)型的數(shù)組mHashes用來(lái)存儲(chǔ)key值的hash，一個(gè)Object類(lèi)型的數(shù)組mArray，用來(lái)存儲(chǔ)key和value的鍵值對(duì)，它的大小是mHashes的兩倍。mSize用來(lái)記錄現(xiàn)存在多少對(duì)數(shù)據(jù)。
int[] mHashes;
Object[] mArray;
int mSize;
同時(shí)ArrayMap本身維持兩個(gè)緩存數(shù)組，這種緩存機(jī)制是為了避免對(duì)象的頻繁創(chuàng)建和回收。mBaseCache容量大小是4，mTwiceBaseCache容量是8，最大緩存數(shù)組個(gè)數(shù)都是10.
static Object[] mBaseCache;
static Object[] mTwiceBaseCache;
要理解緩存機(jī)制，必須看一下內(nèi)存分配和內(nèi)存釋放的過(guò)程。
構(gòu)造函數(shù)有兩個(gè)參數(shù)，capacity是容量，默認(rèn)是0。identityHashCode是判斷采用哪種hashCode。這里不詳細(xì)介紹，可以看下hashCode和System.identityHashCode方法的區(qū)別。我的理解是hashCode方法是可以被重寫(xiě)的。
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) {//1
mHashes = EMPTY_IMMUTABLE_INTS;
mArray = EmptyArray.OBJECT;
} else if (capacity == 0) {//1
mHashes = EmptyArray.INT;
mArray = EmptyArray.OBJECT;
} else {//2
allocArrays(capacity);
}
mSize = 0;//3
}
1.如果capacity小于等于0，構(gòu)造兩個(gè)空數(shù)組；
其中EmptyArray是一個(gè)final類(lèi)，EmptyArray.OBJECT相當(dāng)于new Object[0];EmptyArray.INT相當(dāng)于new int[0];
2.如果capacity大于0，通過(guò)allocArrays分配內(nèi)存。
3.初始狀態(tài)下沒(méi)有數(shù)據(jù)，mSize=0。
接下來(lái)看看allocArrays分配內(nèi)存的方法。
private void allocArrays(final int size) {
if (mHashes == EMPTY_IMMUTABLE_INTS) {
throw new UnsupportedOperationException("ArrayMap is immutable");
}
if (size == (BASE_SIZE*2)) {//1
synchronized (ArrayMap.class) {
if (mTwiceBaseCache != null) {//緩存不為空
final Object[] array = mTwiceBaseCache;//取出第一個(gè)緩存數(shù)組
mArray = array;//賦值給mArray
mTwiceBaseCache = (Object[])array[0];//將mTwiceBaseCache指向下一個(gè)緩存數(shù)組
mHashes = (int[])array[1];//將mHashes指向下一個(gè)hash數(shù)組
array[0] = array[1] = null;//將原來(lái)已取出的數(shù)組回收
mTwiceBaseCacheSize--;//緩存數(shù)組數(shù)量減一
if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes
+ " now have " + mTwiceBaseCacheSize + " entries");
return;
}
}
} else if (size == BASE_SIZE) {//2
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--;
if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes
+ " now have " + mBaseCacheSize + " entries");
return;
}
}
}
//3
mHashes = new int[size];
mArray = new Object[size<<1];
}
1.如果需要分配的capacity容量等于8，直接將緩存數(shù)組mTwiceBaseCache賦值給mArray，然后將mTwichBaseCache指向下一個(gè)緩存數(shù)組，這里實(shí)際上是一個(gè)鏈表結(jié)構(gòu)，最后回收已取出的緩存數(shù)組；
2.如果capacity容量等于4，將緩存數(shù)組mBaseCache賦值給mArray ，原理同上；
3.其他情況下，不使用緩存數(shù)組，直接通過(guò)new構(gòu)建新數(shù)組。
數(shù)據(jù)獲取
先看一下get方法。
@Override
public V get(Object key) {
final int index = indexOfKey(key);
return index >= 0 ? (V)mArray[(index<<1)+1] : null;
}
它首先通過(guò)indexOfKey方法查找該元素所在的位置。
public int indexOfKey(Object key) {
return key == null ? indexOfNull()
: indexOf(key, mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());
}
如果key不為null，通過(guò)indexOf方法查找。接下來(lái)看下indexOf的代碼。
int indexOf(Object key, int hash) {
final int N = mSize;
// Important fast case: if nothing is in here, nothing to look for.
if (N == 0) {
return ~0;//1
}
int index = binarySearchHashes(mHashes, N, hash);//2
// If the hash code wasn't found, then we have no entry for this key.
if (index < 0) {
return index;//3
}
// If the key at the returned index matches, that's what we want.
if (key.equals(mArray[index<<1])) {
return index;//4
}
// Search for a matching key after the index.
int end;
for (end = index + 1; end < N && mHashes[end] == hash; end++) {
if (key.equals(mArray[end << 1])) return end;//5
}
// Search for a matching key before the index.
for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
if (key.equals(mArray[i << 1])) return i;//6
}
// Key not found -- return negative value indicating where a
// new entry for this key should go. We use the end of the
// hash chain to reduce the number of array entries that will
// need to be copied when inserting.
return ~end;//7
}
1.如果當(dāng)前數(shù)組大小為0，直接返回0的反碼；
2.注釋2處是一個(gè)二分查找方法binarySearchHashes，之前已經(jīng)分析過(guò)；
3.如果index小于0，該key不存在，直接返回；
4.如果該索引位置key值相等，返回索引index；因?yàn)閙Array存放的是key和value的鍵值對(duì)，大小是mHashes的兩倍，所以需要對(duì)索引index左移一位，作乘2運(yùn)算。
5.如果該位置key值不相等，說(shuō)明存在沖突，從index往后尋找，找到key值直接返回。
6.從index往前查找，找到key值直接返回。
7.如果沒(méi)有找到，說(shuō)明key值不存在，返回當(dāng)前位置的反碼。
數(shù)據(jù)插入
數(shù)據(jù)插入主要是put方法。
public V put(K key, V value) {
final int osize = mSize;
final int hash;
int index;
if (key == null) {//1
hash = 0;
index = indexOfNull();
} else {//2
hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
index = indexOf(key, hash);
}
if (index >= 0) {//3
index = (index<<1) + 1;
final V old = (V)mArray[index];
mArray[index] = value;
return old;
}
index = ~index;
if (osize >= mHashes.length) {//4
final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))
: (osize >= 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);//5
if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
throw new ConcurrentModificationException();
}
if (mHashes.length > 0) {//6
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);//7
}
if (index < osize) {//8
if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (osize-index)
+ " to " + (index+1));
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();
}
}
mHashes[index] = hash;//9
mArray[index<<1] = key;
mArray[(index<<1)+1] = value;
mSize++;
return null;
}
1.如果key值等于null，尋找null的索引；
2.key值不等于null，通過(guò)二分查找尋找索引；
3.如果key值存在，直接替換value，返回舊的value；
4.如果當(dāng)前元素個(gè)數(shù)大于等于數(shù)組容量，需要進(jìn)行擴(kuò)容，如果數(shù)組容量小于8，以4或8為單位進(jìn)行擴(kuò)容；
5.擴(kuò)容后需要通過(guò)allocArrays方法重新進(jìn)行內(nèi)存的分配；
6.如果舊的數(shù)組不為空，將舊數(shù)組內(nèi)容復(fù)制到新數(shù)組；
6.將舊數(shù)組內(nèi)存釋放；
7.如果索引位置在原數(shù)組中間，將索引以后的內(nèi)容后移；
8.插入key和value。
接下來(lái)看一下上面注釋6處對(duì)內(nèi)存的回收方法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;//1
array[1] = hashes;//2
for (int i=(size<<1)-1; i>=2; i--) {
array[i] = null;//3
}
mTwiceBaseCache = array;//4
mTwiceBaseCacheSize++;//5
if (DEBUG) Log.d(TAG, "Storing 2x cache " + array
+ " now have " + mTwiceBaseCacheSize + " entries");
}
}
} else if (hashes.length == BASE_SIZE) {//6
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++;
if (DEBUG) Log.d(TAG, "Storing 1x cache " + array
+ " now have " + mBaseCacheSize + " entries");
}
}
}
}
1.將回收的數(shù)組指向mTwiceBaseCache第一個(gè)元素位置；
2.回收的hash指向mTwiceBaseCache第二個(gè)元素位置；
3.該數(shù)組其它位置被賦值null，對(duì)象回收；
4.將mTwiceBaseCache指向數(shù)組；
5.緩存數(shù)量加1；
6.如果回收的數(shù)組長(zhǎng)度是4，原理同上，增加一個(gè)mBaseCache 緩存。
最后舉一個(gè)例子，從初始狀態(tài)開(kāi)始，mArray，mHashes，mBaseCache和mTwiceBaseCache是4個(gè)空數(shù)組，都沒(méi)有分配內(nèi)存。
1.首先通過(guò)put插入第一對(duì)數(shù)據(jù)；
2.通過(guò)indexOf方法查找應(yīng)該插入的索引位置，因?yàn)榇藭r(shí)mSize等于0，返回了0的反碼；
3.因?yàn)閿?shù)組容量是0，需要進(jìn)行擴(kuò)容，分配4個(gè)單位的內(nèi)存；
4.在allocArrays方法中對(duì)mHashes和mArray進(jìn)行初始化，長(zhǎng)度分別是4和8，但是這里只是創(chuàng)建了兩個(gè)引用數(shù)組，并沒(méi)有創(chuàng)建對(duì)象，沒(méi)有在堆中分配內(nèi)存；
5.將hash插入mHashes數(shù)組的第一個(gè)位置，將key插入mArray數(shù)組第一個(gè)位置，value插入數(shù)組第二個(gè)位置，這里創(chuàng)建了對(duì)象也分配了內(nèi)存；
6.通過(guò)put方法插入第二對(duì)數(shù)據(jù)，假設(shè)第二對(duì)數(shù)據(jù)的hash比原來(lái)小，將原來(lái)數(shù)據(jù)后移一位，往前面插入數(shù)據(jù)，重復(fù)3次，這樣已經(jīng)插入4對(duì)數(shù)據(jù)；
7.插入第五個(gè)數(shù)據(jù)的時(shí)候就需要擴(kuò)容，分配8個(gè)單位的內(nèi)存；
8.然后將原來(lái)的數(shù)組內(nèi)存釋放，這個(gè)時(shí)候就將原來(lái)的數(shù)組賦值給mBaseCache；
9.如果同個(gè)進(jìn)程內(nèi)的另外一塊代碼使用了allocArrays，請(qǐng)求分配4個(gè)單位的內(nèi)存，就可以將mBaseCache分配給該方法。這樣就避免了減少頻繁地創(chuàng)建和回收Map對(duì)象。
參考：
http://gityuan.com/2019/01/13/arraymap/
https://droidyue.com/blog/2017/02/12/dive-into-arraymap-in-android/
