源码的魅力 - ArrayMap的工作原理

ArrayMap的工作原理（Android 7.1源码）

其他相关文章

1. 源码的魅力 - ArrayDeque 的工作原理
2. 源码的魅力 - HashMap 的工作原理
3. 源码的魅力 - TreeMap 的工作原理
4. GankIo又一个ReactNative客户端

简介

鉴于HashMap的内存使用率太低，而内存又是Android设备系统中极其宝贵的资源，所以Google开发出ArrayMap来一定条件下取代HashMap (几乎平时的开发都可以使用这个结构，而不用HashMap)。

初始化

int[] mHashes;
Object[] mArray;
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);
}
mSize = 0;
}复制代码

ArrayMap的内部主要依靠mHashes以及mArray，构造函数中可以看出和HashMap一样一上来创建时并不会分配内存空间。此处的mhashes就是存放HashCode的数组，mArray时存放key与Value的数组。

put 方法

@Override
public V put(K key, V value) {
final int hash;
int index;
if (key == null) {
hash = 0;
index = indexOfNull();
} else {
hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
index = indexOf(key, hash);
}
if (index >= 0) {
index = (index<<1) + 1;
final V old = (V)mArray[index];
mArray[index] = value;
return old;
}
index = ~index;
if (mSize >= mHashes.length) {
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);
}
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);
}
mHashes[index] = hash;
mArray[index<<1] = key;
mArray[(index<<1)+1] = value;
mSize++;
return null;
}复制代码

• 当key为空时直接通过indexOfNull获取
  index
• 当key不为空时，hash = key.hashCode获取hash值，并且通过indexOf方法来获取位置(indexOf与indexOfNull将在下面详细分析)
• 如果返回的index大于零，直接通过index = （index << 1）+ 1来获取到mArray数组的索引直接替换数据(由于mArray存放的数据是一个key然后一个Value形式的, index* 2就是key的位置，再加一就是value的位置)
• 当没有找到key的位置时，返回的index是负数，通过取反来获取到新插入的位置。
• 当mHash列表满了的时候，执行扩容方法allocArrays() allocArrays与下面的freeArrays方法将在后面进行分析
• 将老数据分配到分配到新数组中。
• 由于此时需要在index位置新插入数据，所以需要将mHashcodes以及mArray中的数据向右移动，在mHashcodes数组中腾出一个位置，mArray中腾出两个位置。
• 将新数据插入，mSize自增

indexOf以及indexOfNull方法

由于indexOfNull其实就是hash参数为0的特殊版本，基本上是一样的所以就不赘述了。

//获取索引值
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;
}
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;
// value found
}
}
return ~lo;
// value not present
}复制代码

• 当之前没有数据时，则返回0的取反值。
• 通过二分法在ContainerHelpers.binarySearch()中查找数据
• 在binarySearch函数当数值并没有的时候，会返回lo的取反值，这个lo此时指向的位置是Value插入的位置。（其实这个取反以及其他位置的取反就是整个ArrayMap中巧妙的地方之一，binarySearch通过返回取反值既做到了数据不存在时返回负数，又提供了数据新插入的位置，一举多得。）
• 当返回的index为负数时，直接返回索引值。
• 如果key正好是在mArray的2*index的位置的数据，则直接返回index
• 如果还是不对，则通过mHashs向下查找，如果存在相同的hash值，并且对应的key也相等则返回index值。
• 反之则向下查找。
• 如果还是没有找到，直接返回end(end 是 等于index + 1)的值取反值

总结：indexOf函数返回正数时是存在key值的mHashCodes数组的索引值，否则返回负值就是在mHashCode新插入位置的索引的取反值，再取反就可以得到插入的位置

allocArrays以及freeArrays函数

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) {
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];
}
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");
}
}
}
}复制代码

ArrayMap通过两个数组mTwiceBaseCache以及mBaseCache两个数组来提供缓存内存空间，但只有在数组大小是4与8时发挥作用。

final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
: (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);复制代码

前面的put中扩展数组部分代码中，当小于4时扩展成4，小于8时扩展成8，否则增加一半的 mSize大小。
allocArrays与freeArrays在缓存部分是相对应的，作用是将原先的那部分内存空间保存住，不然垃圾回收器回收掉。

总结

ArrayMap在内存使用率上比HashMap高不少，但是插入速度在数据很多时会很慢，所以ArrayMap在数据量少时（千以内）比较适用，否则还是要使用HashMap。

更多好文章请关注微信公众号【Android技术栈】，猎豹移动大牛将提供给你更好的技术心得，公众号才刚刚起步希望大家多多支持。