一次面试被问到 ArrayMap，原理及源码分析详解
一、前言
在 《SparseArray 详解及源码简析》中，我们熟悉了 SparseArray 的基本用法、特点以及实现原理。而在 Android SDK 的这个工具包中还有一个同样重要的数据结构 ArrayMap，其目的也是在当数据量较小，比如几百个的时候，可以用来替代 HashMap，以提高内存的使用效率。
如果对 HashMap 的实现感兴趣的话，可以看看《HashMap 详解以及源码分析》，而这篇文章就来了解一下 ArrayMap 的使用及其实现原理。
二、 源码简析
1. demo 及其简析
分析代码之前同样先看一段 demo，后面同样通过 demo 进行实现原理的分析。
ArrayMap<String,String> arrayMap = new ArrayMap<>();
arrayMap.put(null,"张大哥");
arrayMap.put("abcd","A 大哥");
arrayMap.put("aabb","巴大哥");
arrayMap.put("aacc","牛大哥");
arrayMap.put("aadd","牛大哥");
arrayMap.put("abcd","B 大哥");
Set<ArrayMap.Entry<String,String>> sets = arrayMap.entrySet();
for (ArrayMap.Entry<String,String> set : sets) {
Log.d(TAG, "arrayMapSample: key = " + set.getKey() + ";value = " + set.getValue());
}
代码中，实际插入了 6 个 Key-Value，然而输出只有 5 个，其中 Key 为 “abcd” 的重复了而发生了覆盖。另外，还有一点注意的是 null 为 key 是允许插入的。以下是其输出的结果。
arrayMapSample: key = null;value = 张大哥 arrayMapSample: key = aabb;value = 巴大哥 arrayMapSample: key = aacc;value = 牛大哥 arrayMapSample: key = aadd;value = 牛大哥 arrayMapSample: key = abcd;value = B 大哥
通过 Android Studio 的 Debug 功能，也可以简单观察一下其在内存中的存储。
2.源码分析
先来简单看一下 ArrayMap 的类图结构。
与 HashMap 不同的是，它是直接实现自接口 map。同样，存储 key-value 的方式也不同。ArrayMap 是通过数组直接存储了所有的 key-value。其中，mHashes 在 index 处存储了 key 的 hash code，而 mArray 则在 hash code 的 index<<1 处存储 key，在 index<<1 + 1 处存储 value。简单点说就是偶数处存储 key，相邻奇数处存储 value。
ArrayMap 的初始化
/**
Create a new empty ArrayMap. The default capacity of an array map is 0, and
will grow once items are added to it.
*/
public ArrayMap() {
this(0, false);
}
/**
Create a new ArrayMap with a given initial capacity.
*/
public ArrayMap(int capacity) {
this(capacity, false);
}
/** {@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;
}
ArrayMap 的构造方法有 3 个重载的版本都列在上面了，一般我们都用默认的构造方法，那也就是说默认容量大小就是 0，需要等待到插入元素时才会进行扩容的动作。构造方法中的另一个参数 identityHashCode 控制 hashCode 是由 System 类产生还是由 Object.hashCode() 返回。
这两者之间的实现其实没太大区别，因为 System 类最终也是通过 Object.hashCode() 来实现的。其主要就是对 null 进行了特殊处理，比如一律为 0。而在 ArrayMap 的 put() 方法中，如果 key 为 null 也将其 hashCode 视为 0 了。所以这里 identityHashCode 为 true 或者 false 都是一样的。
插入元素 put()
public V put(K key, V value) {
final int osize = mSize;
// 1.计算 hash code 并获取 index
final int hash;
int index;
if (key == null) {
// 为空直接取 0
hash = 0;
index = indexOfNull();
} else {
// 否则取 Object.hashCode()
hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
index = indexOf(key, hash);
}
// 2
.如果 index 大于等于 0 ，说明之前存在相同的 hash code 且 key 也相同，则直接覆盖
if (index >= 0) {
index = (index<<1) + 1;
final V old = (V)mArray[index];
mArray[index] = value;
return old;
}
// 3.如果没有找到则上面的 indexOf() 或者 indexOfNull() 就会返回一个负数，而这个负数就是由将要插入的位置 index 取反得到的，所以这里再次取反就变成了将进行插入的位置
index = ~index;
// 4.判断是否需要扩容
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;
// 5.申请新的空间
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);
}
// 6.释放旧的数组
freeArrays(ohashes, oarray, osize);
}
if (index < osize) {
// 7.如果 index 在当前 size 之内，则需要将 index 开始的数据移到 index + 1 处，以腾出 index 的位置
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();
}
}
// 8.然后根据计算得到的 index 分别插入 hash，key，以及 code
mHashes[index] = hash;
mArray[index<<1] = key;
mArray[(index<<1)+1] = value;
mSize++;
return null;
}
put 方法调用了其他几个内部的方法，其中关于扩容以及如何释放空间，申请新的空间这些，从算法层来讲其实不重要，只要知道一点就是，扩容会发生数据的复制，这个是会影响效率的就可以了。
而与算法相关性较大的 indexOfNull() 方法以及 indexOf() 方法的实现。由于这两个方法的实现基本一样，因此这里只分析 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;
}
int index = binarySearchHashes(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;
}
其实它原来的注释已经很详细了，详细的步骤是：
(1) 如果当前为空表，则直接返回 ~0，注意不是 0 ，而是最大的负数。
(2) 在 mHashs 数组中进行二分查找，找到 hash 的 index。
(3) 如果 index < 0，说明没有找到。
(4) 如果 index >= 0，且在 mArray 中对应的 index<<1 处的 key 与要找的 key 又相同，则认为是同一个 key，说明找到了。
(5) 如果 key 不相同，说明只是 hash code 相同，那么分别向后和向前进行搜索，如果找到了就返回。如果没找到，那么对 end 取反就是当前需要插入的 index 位置。
再回过头来看 put() 方法， put() 方法的具体实现都在源码中加以了详细的说明，感兴趣的可以详细阅读一下。而从 put 方法得出以下几个结论：
(1) mHashs 数组以升序的方式保存了所有的 hash code。
(2) 通过 hash code 在 mHashs 数组里的 index 值来确定 key 以及 value 在 mArrays 数组中的存储位置。一般来说分别就是 index << 1 以及 index << 1 + 1。再简单点说就是 index * 2 以及 index * 2 + 1。
(3) hashCode 必然可能存在冲突，这里是怎么解决的呢？这个是由上面的第 3 步和第 7 步所决定。第 3 步是得出应该插入的 index 的位置，而第 7 步则是如果 index < osize ，则说明原来 mArrays 中必然已经存在相同 hashCode 的值了，那么就把数据全部往后移一位，从而在 mHashs 中插入多个相同的 hash code 并且一定是连接在一起的，而在 mArrays 中插入新的 key 和 value，最终得以解决 hash 冲突。
上面的结论可能还是让人觉得有点晕，那么再来看看下面的图吧，就一定能明白了。
上面图说， index == 0 时 和 index == 1 时的 hash code 是一样的，说明 key1 与 key2 的 hash code 是一样的，也就是存在 hash 冲突了。那么，如上，这里的解决办法就是 hash code 存储了 2 份，而 key-value 分别存储一份。
get() 方法
public V get(Object key) {
final int index = indexOfKey(key);
return index >= 0 ? (V)mArray[(index<<1)+1] : null;
}
主要就是通过 indexOfKey() 计算出 index，而 indexOfKey() 的实现就是调用 indexOfNull () 和 indexOf()，其具体的实现已经上面分析过了。这里如果返了 index >= 0，则说明一定是找到了，那么根据前面的规则，在 mArray 中，index<<1 + 1 就是所要获取的 value 了。
remove() 方法
public V remove(Object key) {
还未添加个人签名 2021.10.31 加入
还未添加个人简介
评论