之前我们了解到如果 key 是 int 类型的 map， 使用 SparseArray 可避免自动装箱过程，从而提高效率。那如果 key 是其他类型呢？我们就得用 HashMap 了吗？其实不然，Android 还提供了 ArrayMap，在内存使用上比 HashMap 更有效率，但是它也有自身的缺点，比如说查找和插入的时间复杂度比 HashMap 差了点。下面就让我们揭开其神秘的面纱。
类结构
public final class ArrayMap<K, V> implements Map<K, V> {
private static final boolean CONCURRENT_MODIFICATION_EXCEPTIONS = true;
private static final int BASE_SIZE = 4; // 容量增量的最小值
private static final int CACHE_SIZE = 10; // 缓存数组的上限
static Object[] mBaseCache; //用于缓存大小为4的ArrayMap
static int mBaseCacheSize;
static Object[] mTwiceBaseCache; //用于缓存大小为8的ArrayMap
static int mTwiceBaseCacheSize;
final boolean mIdentityHashCode;
int[] mHashes; //由key的hashcode所组成的数组
Object[] mArray; //由key-value对所组成的数组，是mHashes大小的2倍
int mSize; //成员变量的个数
}
- mHashes，int 数组，用来保存 key 的 hashCode。
- mArray，Object 数组，用来保存 key-value，长度时 mHashes 的 2 倍。
- mBaseCache，Object 数组，用来缓存大小为 4 的 ArrayMap，mBaseCacheSize 记录当前已缓存的数量，超过 10 个即不再缓存。
-
mTwiceBaseCacheSize，Object 数组，用来缓存大小为 8 的 ArrayMap，mTwiceBaseCacheSize 记录当前已缓存的数量，超过 10 个则不再缓存。
ArrayMap 的内部数据结构可用下图来表示：
put 方法
put 方法的逻辑主要分为以下几个部分：
- key 为 null 时的插入
- key 不为 null 时的插入
- 如有需要进行扩容处理
源码如下：
public V put(K key, V value) {
final int osize = mSize; // 当前 map 大小
final int hash;
int index;
if (key == null) {
hash = 0; // 如果 key 为 null，其 hashCode 算作 0
index = indexOfNull();
} else {
hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
index = indexOf(key, hash); // 通过二分法在 mHashes 数组中查找值等于 hash 的 key
}
// index 大于等于 0 时，更新 key 对应 value 并返回旧值。
if (index >= 0) {
index = (index<<1) + 1;
final V old = (V)mArray[index];
mArray[index] = value;
return old;
}
// 当 index < 0 ，则代表是插入新元素
index = ~index;
// 当 osize >= mHashes.length 时进行扩容
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) {
// 将 mHashes 和 mArray 的旧数组复制到新分配的数组中
System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
System.arraycopy(oarray, 0, mArray, 0, oarray.length);
}
// 释放掉旧数据的内存
freeArrays(ohashes, oarray, osize);
}
// 当插入的位置不在数组末尾时，需要将 index 位置后的数据往后移动一位
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();
}
}
// 完成数据插入，mSize 个数加1
mHashes[index] = hash;
mArray[index<<1] = key;
mArray[(index<<1)+1] = value;
mSize++;
return null;
}
append 方法
append 方法的过程与 put() 很相似，append 的差异在于该方法不会去做扩容处理，是一个轻量级的操作，适合于提前知道会插入队尾的情况下，这样会比 put() 方法性能更好。put() 方法上来先做 binarySearchHashes 二分查找，时间复杂度为 O(logN)，而 append() 的时间复杂读为 O(1)，append 方法如下：
public void append(K key, V value) {
int index = mSize;
final int hash = key == null ? 0
: (mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());
//当 index 大于等于 mHashes.length 时抛出异常
if (index >= mHashes.length) {
throw new IllegalStateException("Array is full");
}
//当数据插入到数组的中间，会调用put来完成
if (index > 0 && mHashes[index-1] > hash) {
put(key, value);
return;
}
//数据直接添加到队尾
mSize = index+1;
mHashes[index] = hash;
index <<= 1;
mArray[index] = key;
mArray[index+1] = value;
}
remove() 方法
调用 remove() 方法可以删除 ArrayMap 的一项数据，主要逻辑如下：
- 如果当前 ArrayMap 只有一项数据，则会置空 mHashes、mArray，将 mSize 置为 0 。
- 如果当前 ArrayMap 容量过大（大于 8）并且持有数据量过小（不足 1/3）则降低 ArrayMap 的容量，减少内存占用。
- 上述情况都不满足时，则从 mHashes 删除相应的值，将 mArray 中对应的索引置为 null。
源码如下：
public V remove(Object key) {
final int index = indexOfKey(key); // 二分法查找key的index
if (index >= 0) {
return removeAt(index); // 移除相应位置的数据
}
return null;
}
public V removeAt(int index) {
final Object old = mArray[(index << 1) + 1];
final int osize = mSize;
final int nsize;
if (osize <= 1) { // 如果被移除的是ArrayMap的最后一个元素，则释放该内存
freeArrays(mHashes, mArray, osize);
mHashes = EmptyArray.INT;
mArray = EmptyArray.OBJECT;
nsize = 0;
} else {
nsize = osize - 1;
// 容量过大时收紧容量
if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
final int n = osize > (BASE_SIZE*2) ? (osize + (osize>>1)) : (BASE_SIZE*2);
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
allocArrays(n);
// 并发时抛出异常
if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
throw new ConcurrentModificationException();
}
if (index > 0) {
System.arraycopy(ohashes, 0, mHashes, 0, index);
System.arraycopy(oarray, 0, mArray, 0, index << 1);
}
if (index < nsize) {
System.arraycopy(ohashes, index + 1, mHashes, index, nsize - index);
System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1,
(nsize - index) << 1);
}
} else {
//当被移除的元素不是数组最末尾的元素时，则需要将后面的数组往前移动
if (index < nsize) {
System.arraycopy(mHashes, index + 1, mHashes, index, nsize - index);
System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1,
(nsize - index) << 1);
}
//再将最后一个位置设置为null
mArray[nsize << 1] = null;
mArray[(nsize << 1) + 1] = null;
}
}
if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
throw new ConcurrentModificationException();
}
mSize = nsize; //大小减1
return (V)old;
}
clear() 方法与 earse() 方法
clear() 方法会通过 freeArrays() 方法来回收内存，而 earse(）则会清空数组的数据，不会回收内存，它们的源码如下：
/**
* Make the array map empty. All storage is released.
*/
@Override
public void clear() {
if (mSize > 0) {
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
final int osize = mSize;
mHashes = EmptyArray.INT;
mArray = EmptyArray.OBJECT;
mSize = 0;
freeArrays(ohashes, oarray, osize);
}
if (CONCURRENT_MODIFICATION_EXCEPTIONS && mSize > 0) {
throw new ConcurrentModificationException();
}
}
/**
* @hide
* Like {@link #clear}, but doesn't reduce the capacity of the ArrayMap.
*/
public void erase() {
if (mSize > 0) {
final int N = mSize<<1;
final Object[] array = mArray;
for (int i=0; i<N; i++) {
array[i] = null;
}
mSize = 0;
}
}
缓存机制
如上所述，put() 方法增加数据，会扩大容量；remove() 方法会删除数据，减少容量。这会频繁低出现多个 4 和 8 的 int 数组和 Object 数组，所以为了减少内存回收的压力，ArrayMap 引入了缓存机制，主要涉及到了以下两个方法：
- freeArrays
freeArrays 在释放内存时，如果释放的 array 大小等于 4 或者 8 时，且相应的缓冲池未达上限时(10)，则会把 array 加入到缓冲池中，源码如下：
private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
if (hashes.length == (BASE_SIZE*2)) { //当释放的是大小为8的对象
synchronized (ArrayMap.class) {
// 当大小为8的缓存池的数量小于10个，则将其放入缓存池
if (mTwiceBaseCacheSize < CACHE_SIZE) {
array[0] = mTwiceBaseCache; //array[0]指向原来的缓存池
array[1] = hashes;
for (int i=(size<<1)-1; i>=2; i--) {
array[i] = null; //清空其他数据
}
mTwiceBaseCache = array; //mTwiceBaseCache指向新加入缓存池的array
mTwiceBaseCacheSize++;
}
}
} else if (hashes.length == BASE_SIZE) { //当释放的是大小为4的对象，原理同上
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++;
}
}
}
}
- allocArrays
分配内存时，如果所需要分配的大小等于 4 或者 8，且对应的缓冲池不为空，则会从相应的缓存池取出 mHashes 和 mArray。源码如下：
private void allocArrays(final int size) {
if (size == (BASE_SIZE*2)) { //当分配大小为8的对象，先查看缓存池
synchronized (ArrayMap.class) {
if (mTwiceBaseCache != null) { // 当缓存池不为空时
final Object[] array = mTwiceBaseCache;
mArray = array; //从缓存池中取出mArray
mTwiceBaseCache = (Object[])array[0]; //将缓存池指向上一条缓存地址
mHashes = (int[])array[1]; //从缓存中mHashes
array[0] = array[1] = null;
mTwiceBaseCacheSize--; //缓存池大小减1
return;
}
}
} else if (size == BASE_SIZE) { //当分配大小为4的对象，原理同上
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--;
return;
}
}
}
// 分配大小除了4和8之外的情况，则直接创建新的数组
mHashes = new int[size];
mArray = new Object[size<<1];
}
扩容机制
容量扩张
当 size 大于或等于 mHashes 的数组长度时则扩容，完成扩容后需要将老的数组拷贝到新分配的数组，并释放老的内存。
- 当 map 个数满足条件 osize < 4时，则扩容后的大小为 4；
- 当 map 个数满足条件 4<= osize < 8时，则扩容后的大小为8；
- 当 map 个数满足条件 osize >= 8时，则扩容后的大小为原来的1.5倍。
源码如下：
public V put(K key, V value) {
...
final int osize = mSize;
if (osize >= mHashes.length) { //当mSize大于或等于mHashes数组长度时需要扩容
final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))
: (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
allocArrays(n); //分配更大的内存【小节2.2.2】
}
...
}
容量收紧
当数组内存的大小大于8，且已存储数据的个数mSize小于数组空间大小的1/3的情况下，需要收紧数据的内容容量，分配新的数组，老的内存靠虚拟机自动回收。
- 如果mSize<=8，则设置新大小为8；
- 如果mSize> 8，则设置新大小为mSize的1.5倍。即当内存使用量不足 1/3 的情况下，内存数组会收紧 50 %。
源码如下：
public V removeAt(int index) {
final int osize = mSize;
final int nsize;
if (osize > 1) { //当mSize大于1的情况，需要根据情况来决定是否要收紧
nsize = osize - 1;
if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
final int n = osize > (BASE_SIZE*2) ? (osize + (osize>>1)) : (BASE_SIZE*2);
allocArrays(n); // 分配更小的内存
}
}
}
总结
ArrayMap 在内存利用率上比 HashMap 更高，因为不用创建额外的 Node 数据结构，同时具有缓存机制，避免频繁创建对象而分配内存与 GC 操作。此外，在数据条目小于容量 1/3 时会触发内存收缩至原理的 0.5 倍。因此，当数据量不大（小于1000）时更推荐使用 ArrayMap。更详细的对比，可查看SparseArray、ArrayMap、HashMap 之间的比较。
网友评论