ArrayMap 使用2个数组。它的对象实例内部有用来存储对象的 Object[] mArray 和 存储哈希值的 int[] mHashes。当插入一个键值对时：
- 键/值被自动装箱。
- 键对象被插入到 mArray[] 数组中的下一个空闲位置。
- 值对象也会被插入到 mArray[] 数组中与键对象相邻的位置。
- 键的哈希值会被计算出来并被插入到 mHashes[] 数组中的下一个空闲位置。
对于查找一个 key :
- 键的哈希值先被计算出来
- 在 mHashes[] 数组中二分查找此哈希值。这表明查找的时间复杂度增加到了 O(logN)。
- 一旦得到了哈希值所对应的索引 index，键值对中的键就存储在 mArray[2index] ，值存储在 mArray[2index+1]。
- 相比HashMap，这里的时间复杂度从 O(1) 上升到 O(logN)，但是内存效率提升了。当我们在 100 左右的数据量范围内尝试时，没有耗时的问题，察觉不到时间上的差异，但我们应用的内存效率获得了提高。
@Override
public V put(K key, V value) {
final int osize = mSize;
final int hash;
int index;
if (key == null) {
hash = 0;
index = indexOfNull();
} else {
hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
// 查找下标
index = indexOf(key, hash);
}
// 大于0说明找到对应的下标，替换value即可，并且返回原来的值
if (index >= 0) {
index = (index<<1) + 1;
final V old = (V)mArray[index];
mArray[index] = value;
return old;
}
/**
* 没有找到或者hashCode相同，但value没有equals的情况
*/
index = ~index;
// 如果存放hash值的数组空间快不够(<=osize)了，就进入扩容流程
if (osize >= mHashes.length) {
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);
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);
}
/**
* 如果hash碰撞的正好是数组的最后一个，那就不需要调整数组，
* 如果不是，那就进入流程，把index到最后一位全往后挪一位，给index位置空出来，方便后面赋值
* 这样就说明了，当发生碰撞的时候，新的一条数据是就近插入在碰撞index+1（见{@link #indexOf}返回值end的值变化）的位置，
*/
if (index < osize) {
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;
mArray[index<<1] = key;
mArray[(index<<1)+1] = value;
mSize++;
return null;
}
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;
}
// 二分法查找法去匹配hashCode，时间复杂度 O(logN)
int index = binarySearchHashes(mHashes, N, hash);
// If the hash code wasn't found, then we have no entry for this key.
// 如果找不到就返回一个负数 -1
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.
// 如果hashCode一样，值不一样，进入hash碰撞的流程
int end;
// 往后查找相邻的hashCode值相同的，看有没有插入过该值
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.
// 往前查找相邻的hashCode值相同的，看有没有插入过该值
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.
// 返回负值，既可以用来表示无法找到匹配的key，也可以用来为后续的插入数据所用。
// end的值是后面用来插入的下标，这就说明了发生hash碰撞的那几个值总是在数组相邻的位置
return ~end;
}
// TODO: 2018/3/15 扩容的源码会有空加上
参考
https://zhuanlan.zhihu.com/p/23224444
https://www.youtube.com/watch?v=ORgucLTtTDI
https://droidyue.com/blog/2017/02/12/dive-into-arraymap-in-android/
