本文SimpleArrayMap源碼分析是基于support v4 23.3.0版本的。
另外，因ArrayMap涉及的多是算法知識(shí)，而主要的思想比較簡(jiǎn)單，所以本文會(huì)主要以代碼為主，細(xì)講其每個(gè)實(shí)現(xiàn)。
為什么要引入ArrayMap？
在Android設(shè)備上，因?yàn)锳pp的內(nèi)存限制，出現(xiàn)OOM的錯(cuò)誤，導(dǎo)致開(kāi)發(fā)者不得不關(guān)注一些底層數(shù)據(jù)結(jié)構(gòu)以及去分析App的內(nèi)存使用情況。提及數(shù)據(jù)結(jié)構(gòu)，HashMap是我們最經(jīng)常使用到的，而我們是否會(huì)注意其實(shí)現(xiàn)的細(xì)節(jié)以及有什么優(yōu)缺點(diǎn)呢？
這里簡(jiǎn)單提及一下HashMap在擴(kuò)容時(shí)采取的做法是：將當(dāng)前的數(shù)據(jù)結(jié)構(gòu)所占空間*2，而這對(duì)安卓稀缺的資源來(lái)說(shuō)，可是非常大的消耗。所以就誕生了ArrayMap，它是在API19引入的，這樣我們?cè)诩嫒菀郧鞍姹镜臅r(shí)候，support包就派上用場(chǎng)了，可是為什么不直接是使用ArrayMap，而會(huì)多出來(lái)一個(gè)SimpleArrayMap呢？不得不說(shuō)這是谷歌的厚道、人性化處，考慮我們使用ArrayMap時(shí)，可能不需要使用Java標(biāo)準(zhǔn)的集合API，而給我們提供的一個(gè)純算法實(shí)現(xiàn)的ArrayMap。
上面提到的集合API，是SimpleArrayMap跟v4包中的ArrayMap最大的區(qū)別，證明就是ArrayMap繼承了SimpleArrayMap，又實(shí)現(xiàn)了Map的接口；主要的操作，則是通過(guò)引入MapCollections類，使用Map中的Entry結(jié)構(gòu)，這樣在ArrayMap中就可以通過(guò)Iterator來(lái)進(jìn)行數(shù)據(jù)的的迭代操作。
實(shí)現(xiàn)思想
簡(jiǎn)單地了解一下其思想，是我們接下來(lái)進(jìn)行源碼分析的必要步驟，方便我們帶著問(wèn)題去驗(yàn)證我們所想。兵馬未動(dòng)，糧草先行。做事前一定要先把準(zhǔn)備工作做好，事情理順，盡量地充分考慮工作的細(xì)節(jié) ，再開(kāi)始進(jìn)行工作。正如我們現(xiàn)在項(xiàng)目開(kāi)發(fā)之前，一定要先進(jìn)行任務(wù)點(diǎn)的分解，而這時(shí)思維導(dǎo)圖、UML建模工具則是我們必須玩轉(zhuǎn)的東西。
- 思想：SimpleArrayMap采用了兩個(gè)數(shù)組來(lái)進(jìn)行hash值與key、value值得保存，另外，數(shù)組大小超過(guò)8時(shí)，并需要進(jìn)行擴(kuò)容時(shí)，只增大當(dāng)前數(shù)組大小的一半，并對(duì)大小為4和8的數(shù)組進(jìn)行緩存。這樣最后帶來(lái)的好處就是最大程度保證了數(shù)組空間都能夠被使用，一定程度上避免了內(nèi)存空間的浪費(fèi)。
- 數(shù)據(jù)結(jié)構(gòu)方式：使用了兩個(gè)數(shù)組，一個(gè)是Hash數(shù)組，另一個(gè)是大小*2的Array數(shù)組，為了保證通用性，這里所使用的是Object數(shù)組。Array數(shù)組中使用key+value間隔存取的方式，偶數(shù)為即
0 -> key1 1 -> value1 2 -> key2 3 -> value2。另外Hash數(shù)組，則是對(duì)應(yīng)的Key的Hash值數(shù)組，并且這是一個(gè)有序的int數(shù)組，這樣在進(jìn)行Key的查找時(shí)，使用二分查找則是最有效率的方式了。如下圖：
數(shù)據(jù)結(jié)構(gòu)定義
1.數(shù)據(jù)結(jié)構(gòu)
int[] mHashes;
Object[] mArray;
int mSize;
代碼中，mHashes數(shù)組為mArray中的key對(duì)應(yīng)的hash值得數(shù)組，而mArray即是HashMap中key與value間隔混合的一個(gè)數(shù)組。
2.初始化
- 默認(rèn)構(gòu)造器(初始大小為0)
/**
* Create a new empty ArrayMap. The default capacity of an array map is 0, and
* will grow once items are added to it.
*/
public SimpleArrayMap() {
mHashes = ContainerHelpers.EMPTY_INTS;
mArray = ContainerHelpers.EMPTY_OBJECTS;
mSize = 0;
}
- 指定初始大小
/**
* Create a new ArrayMap with a given initial capacity.
*/
public SimpleArrayMap(int capacity) {
if (capacity == 0) {
mHashes = ContainerHelpers.EMPTY_INTS;
mArray = ContainerHelpers.EMPTY_OBJECTS;
} else {
allocArrays(capacity);
}
mSize = 0;
}
- 通過(guò)SimpleArrayMap賦值
/**
* Create a new ArrayMap with the mappings from the given ArrayMap.
*/
public SimpleArrayMap(SimpleArrayMap map) {
this();
if (map != null) {
putAll(map);
}
}
3.釋放
/**
* Make the array map empty. All storage is released.
*/
public void clear() {
if (mSize != 0) {
freeArrays(mHashes, mArray, mSize);
mHashes = ContainerHelpers.EMPTY_INTS;
mArray = ContainerHelpers.EMPTY_OBJECTS;
mSize = 0;
}
}
代碼中提及的EMPTY_INTS及EMPTY_OBJECTS，僅僅如下的兩個(gè)空數(shù)組:
static final int[] EMPTY_INTS = new int[0];
static final Object[] EMPTY_OBJECTS = new Object[0];
算法
1. 存數(shù)據(jù)put(key, value)
存數(shù)據(jù)的操作，按我們數(shù)據(jù)結(jié)構(gòu)的定義，應(yīng)該是需要針對(duì)key，獲取其對(duì)應(yīng)的hash值，在Hash數(shù)組中，采取二分查找，定位到指定hash值所對(duì)應(yīng)的index值；之后根據(jù)index值，來(lái)調(diào)整并存放key跟value的值。來(lái)看看源碼的實(shí)現(xiàn)吧：
/**
* Add a new value to the array map.
* @param key The key under which to store the value. <b>Must not be null.</b> If
* this key already exists in the array, its value will be replaced.
* @param value The value to store for the given key.
* @return Returns the old value that was stored for the given key, or null if there
* was no such key.
*/
public V put(K key, V value) {
final int hash;
int index;
if (key == null) {
// 查找key為null的情況
hash = 0;
index = indexOfNull();
} else {
hash = key.hashCode();
index = indexOf(key, hash);
}
if (index >= 0) {
// 數(shù)組中存在相同的key，則更新并返回舊的值
index = (index<<1) + 1;
final V old = (V)mArray[index];
mArray[index] = value;
return old;
}
index = ~index;
if (mSize >= mHashes.length) {
// 當(dāng)容量不夠時(shí)，需要建立一個(gè)新的數(shù)組，來(lái)進(jìn)行擴(kuò)容操作。
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");
System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
System.arraycopy(oarray, 0, mArray, 0, oarray.length);
}
freeArrays(ohashes, oarray, mSize);
}
// 將index之后的數(shù)據(jù)進(jìn)行后移
if (index < mSize) {
if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index)
+ " to " + (index+1));
System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index);
System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
}
// 賦值給index位置上hash值
mHashes[index] = hash;
// 更新array數(shù)組中對(duì)應(yīng)的key跟value值。
mArray[index<<1] = key;
mArray[(index<<1)+1] = value;
mSize++;
return null;
}
代碼中，可以看出arrayMap允許key為空，所有的key都不能重復(fù)。
另外，在進(jìn)行容量修改的時(shí)候，進(jìn)行的操作是：mSize跟hash數(shù)組長(zhǎng)度的判斷，當(dāng)大于等于的時(shí)候，需要對(duì)數(shù)組的容量進(jìn)行一些擴(kuò)容，并拷貝數(shù)組到新的數(shù)組中。（擴(kuò)容操作：當(dāng)size大于8, 取size + size /2 ; 當(dāng)size大于4小于8時(shí)， 取8 ，當(dāng)size小于4時(shí)，取4）
2. 取數(shù)據(jù)get（key)
/**
* Retrieve a value from the array.
* @param key The key of the value to retrieve.
* @return Returns the value associated with the given key,
* or null if there is no such key.
*/
public V get(Object key) {
final int index = indexOfKey(key);
return index >= 0 ? (V)mArray[(index<<1)+1] : null;
}
通過(guò)key來(lái)獲取數(shù)據(jù)就非常簡(jiǎn)單了，根據(jù)key獲取到相應(yīng)的index值，在array數(shù)據(jù)中根據(jù)index乘2加1返回相應(yīng)的value即可。
3. 刪除數(shù)據(jù)remove（key）
/**
* Remove an existing key from the array map.
* @param key The key of the mapping to remove.
* @return Returns the value that was stored under the key, or null if there
* was no such key.
*/
public V remove(Object key) {
final int index = indexOfKey(key);
if (index >= 0) {
return removeAt(index);
}
return null;
}
根據(jù)key來(lái)刪除時(shí)，先會(huì)根據(jù)key來(lái)獲取其對(duì)應(yīng)的index值，再通過(guò)removeAt(int index)方法來(lái)進(jìn)行刪除操作。
/**
* Remove the key/value mapping at the given index.
* @param index The desired index, must be between 0 and {@link #size()}-1.
* @return Returns the value that was stored at this index.
*/
public V removeAt(int index) {
final Object old = mArray[(index << 1) + 1];
if (mSize <= 1) {
// Now empty.
if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0");
freeArrays(mHashes, mArray, mSize);
mHashes = ContainerHelpers.EMPTY_INTS;
mArray = ContainerHelpers.EMPTY_OBJECTS;
mSize = 0;
} else {
// 滿足條件，對(duì)數(shù)組進(jìn)行加入緩存的操作。
if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
// Shrunk enough to reduce size of arrays. We don't allow it to
// shrink smaller than (BASE_SIZE*2) to avoid flapping between
// that and BASE_SIZE.
final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>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);
mSize--;
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 < mSize) {
if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + mSize
+ " to " + index);
System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index);
System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1,
(mSize - index) << 1);
}
} else {
mSize--;
if (index < mSize) {
if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + mSize
+ " to " + index);
System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index);
System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1,
(mSize - index) << 1);
}
mArray[mSize << 1] = null;
mArray[(mSize << 1) + 1] = null;
}
}
return (V)old;
}
這里先忽略hash數(shù)組長(zhǎng)度的判斷（主要進(jìn)行數(shù)組緩存的操作）只看主要的代碼，即最后的一個(gè)else的代碼，使用System.arraycopy方法將hash數(shù)組跟array數(shù)組中index之后的數(shù)據(jù)往前移動(dòng)1位，而將最后一位的數(shù)據(jù)進(jìn)行至空。
4. indexOfKey (key)
上面代碼中，都可以看到indexOfKey身影的出現(xiàn)，來(lái)看到其中如何實(shí)現(xiàn)的：
/**
* Returns the index of a key in the set.
*
* @param key The key to search for.
* @return Returns the index of the key if it exists, else a negative integer.
*/
public int indexOfKey(Object key) {
return key == null ? indexOfNull() : indexOf(key, key.hashCode());
}
由上發(fā)現(xiàn)允許key為null，進(jìn)行index的查詢，當(dāng)key不為空時(shí)，通過(guò)key及其key的hashCode,來(lái)進(jìn)行查詢。
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;
}
int index = ContainerHelpers.binarySearch(mHashes, N, hash);
// If the hash code wasn't found, then we have no entry for this key.
if (index < 0) {
return index;
}
// If the key at the returned index matches, that's what we want.
if (key.equals(mArray[index<<1])) {
return index;
}
// 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;
}
// 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;
}
// 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;
}
代碼中，是先對(duì)Hash數(shù)組進(jìn)行二分查找，獲取index，之后根據(jù)index獲取hash數(shù)組中對(duì)應(yīng)的值，通過(guò)與key來(lái)比較是否相等，相等則直接返回，若不相等，則先從index之后的數(shù)據(jù)進(jìn)行比較，沒(méi)找到，則再找之前的數(shù)據(jù)。可以看出這樣是支持存在多個(gè)key的hash值相同的情況，那再看看支不支持多個(gè)key為null的情況呢？
int indexOfNull() {
final int N = mSize;
// Important fast case: if nothing is in here, nothing to look for.
if (N == 0) {
return ~0;
}
int index = ContainerHelpers.binarySearch(mHashes, N, 0);
// If the hash code wasn't found, then we have no entry for this key.
！if (index < 0) {
return index;
}
// If the key at the returned index matches, that's what we want.
if (null == mArray[index<<1]) {
return index;
}
// Search for a matching key after the index.
int end;
for (end = index + 1; end < N && mHashes[end] == 0; end++) {
if (null == mArray[end << 1]) return end;
}
// Search for a matching key before the index.
for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) {
if (null == mArray[i << 1]) return i;
}
// 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;
}
從上可以看出當(dāng)key為null的時(shí)候，采取獲取的方法跟key不為null獲取是很相似的了，都要進(jìn)行整個(gè)數(shù)組的遍歷，不過(guò)這里對(duì)應(yīng)的hash都是為0。但key為null只能在數(shù)組中存在一個(gè)的，因?yàn)樵跀?shù)據(jù)的put操作的時(shí)候，會(huì)對(duì)key進(jìn)行檢查，這樣保證了key為null只能存在一個(gè)。
5.二分查找
這里，回顧一下，上面代碼中一直會(huì)用到的，經(jīng)典的二分查找的算法：
// This is Arrays.binarySearch(), but doesn't do any argument validation.
static int binarySearch(int[] array, int size, int value) {
int lo = 0;
int hi = size - 1;
while (lo <= hi) {
int mid = (lo + hi) >>> 1;
int midVal = array[mid];
if (midVal < value) {
lo = mid + 1;
} else if (midVal > value) {
hi = mid - 1;
} else {
return mid; // value found
}
}
return ~lo; // value not present
}
代碼中，采用右移操作來(lái)進(jìn)行除2的操作，而通過(guò)三個(gè)大于號(hào)，則表示無(wú)符號(hào)操作。
緩存的實(shí)現(xiàn)
講到這里，就基本可以結(jié)束了，而源碼中看到了兩個(gè)神奇的數(shù)組，他倆主要的目的是對(duì)固定的數(shù)組來(lái)進(jìn)行緩存，官方給的說(shuō)法是避免內(nèi)存抖動(dòng)，畢竟這里是純數(shù)組來(lái)實(shí)現(xiàn)的，而當(dāng)數(shù)組容量不夠的時(shí)候，就需要建立一個(gè)新的數(shù)組，這樣舊的數(shù)組不就浪費(fèi)了，所以這里的緩存還是灰常必要的。接下來(lái)看看他倆是怎樣玩的，不感興趣的可以略過(guò)這里了。先看一下數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)：
1.數(shù)據(jù)結(jié)構(gòu)
/**
* The minimum amount by which the capacity of a ArrayMap will increase.
* This is tuned to be relatively space-efficient.
*/
private static final int BASE_SIZE = 4;
/**
* Maximum number of entries to have in array caches.
*/
private static final int CACHE_SIZE = 10;
/**
* Caches of small array objects to avoid spamming garbage. The cache
* Object[] variable is a pointer to a linked list of array objects.
* The first entry in the array is a pointer to the next array in the
* list; the second entry is a pointer to the int[] hash code array for it.
*/
static Object[] mBaseCache;
static int mBaseCacheSize;
static Object[] mTwiceBaseCache;
static int mTwiceBaseCacheSize;
代碼中有兩個(gè)靜態(tài)的Object數(shù)組，這兩個(gè)靜態(tài)數(shù)組采用鏈表的方式來(lái)緩存所有的數(shù)組。即Object數(shù)組會(huì)用來(lái)指向array數(shù)組，而這個(gè)array的第一個(gè)值為指針，指向下一個(gè)array，而第二個(gè)值是對(duì)應(yīng)的hash數(shù)組，其他的值則為空。另外，緩存數(shù)組即baseCache和twiceBaseCache，它倆大小容量的限制：最小值為4，最大值為10，而B(niǎo)aseCache數(shù)組主要存儲(chǔ)的是容量為4的數(shù)組，twiceBaseCache主要存儲(chǔ)容量為8的數(shù)組。如圖：
2.緩存數(shù)據(jù)添加
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) {
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");
}
}
}
}
這個(gè)方法主要調(diào)用的地方在于ArrayMap進(jìn)行容量改變時(shí)，代碼中，會(huì)對(duì)當(dāng)前數(shù)組的array進(jìn)行清空操作，但第一個(gè)值指向之前cache數(shù)組，第二個(gè)值指向hash數(shù)組。
3.緩存數(shù)組使用
private void allocArrays(final int size) {
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) {
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;
}
}
}
mHashes = new int[size];
mArray = new Object[size<<1];
}
這個(gè)時(shí)候，當(dāng)size跟緩存的數(shù)組大小相同，即要么等于4，要么等于8，即可從緩存中拿取數(shù)組來(lái)用。這里主要的操作就是baseCache指針的移動(dòng)，指向array[0]指向的指針，hash數(shù)組即為array[0]，而當(dāng)前的這個(gè)array咱們就可以使用了。
總結(jié)
- SimpleArrayMap是可以替代ArrayMap來(lái)使用的，區(qū)別只是其內(nèi)部采用單純的數(shù)組來(lái)實(shí)現(xiàn)，而ArrayMap中采用了EntrySet跟KeySet的結(jié)構(gòu)，這樣方便使用
Iterator來(lái)數(shù)據(jù)的遍歷獲取。 - ArrayMap適用于少量的數(shù)據(jù)，因?yàn)榇嫒〉膹?fù)雜度，對(duì)數(shù)量過(guò)大的就不太合適。這個(gè)量筆者建議破百就放棄ArrayMap的使用吧。
- ArrayMap支持key為null，但數(shù)組只能有一個(gè)key為null的存在。另外，允許多個(gè)key的hash值相同，不過(guò)盡量避免吧，不然二分查找獲取不到，又會(huì)進(jìn)行遍歷查找；而key都必須是唯一，不能重復(fù)的。
- 主要目的是避免占用大量的內(nèi)存切無(wú)法得到地充分利用。
- 對(duì)容量為4和容量為8的數(shù)組，進(jìn)行緩存，來(lái)防止內(nèi)存抖動(dòng)的發(fā)生。
PS: 轉(zhuǎn)載請(qǐng)注明原文鏈接
