ArrayMap vs HashMap
问：ArrayMap vs HashMap，要怎么选？
答：当size小于等于8的时候，选择ArrayMap，其他情况下选择hashmap
ArrayMap的优势：更节约内存
- 内存增长慢：arraymap内存增加是每次增加1.5倍，而hashmap是每次增加2倍内存
- 数组内存在部分场景下会全局复用
- 当内容减少的时候，数组会缩小，降低内存
- 每次保存的时候，不需要建新的对象，而hashmap每次保存都要新建Node对象
ArrayMap的劣势：性能，还是性能
- 每次检索是二分查找，时间复杂度O(logn),而hashmap大多数下仅仅是O(1)
- 会存在大量需要复制数组的场景，复制数组也是一个颇重的操作
个人认为，arraymap优化的内存，一般都不到几kb，基本可以忽略，相对来说，性能才是我们更看重的，所以建议统一选择hashmap，如果是很在乎内存的场景，可以在数量不超过8的时候，选择ArrayMap，数量不大的时候，两者的性能基本可以忽略；
上一篇已经分析过hashmap了，下面继续用自问自答的方式了解下arraymap
存储载体是什么
存储的载体，才是了解一个map的本质，ArrayMap的载体是两个数组，一个是存储Key的hash值，一个是存储key跟value
int[] mHashes; //key
Object[] mArray; //key和value
它们的关系，可以用这个图来形象的说明
保存hash的数组跟保存key value数组的position要一一对应，这样在知道hash的位置，就可以知道对应的key value的位置，所以mArray的长度永远是mHashes长度的两倍
数组的长度规律
既然是数组，就一定有长度，mHashes的长度是增长规律是这样
默认长度是0
public SimpleArrayMap() {
//数组默认长度是0
mHashes = ContainerHelpers.EMPTY_INTS;
mArray = ContainerHelpers.EMPTY_OBJECTS;
mSize = 0;
}
接着在保存第一条数据后，长度变成了4，超过4条后，变成了8，然后再是12，再就一直1.5倍往上的增加
private static final int BASE_SIZE = 4;
final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))
: (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
至于数组长度的扩大方法，也很简单，直接new一个新的数组
mHashes = new int[size];
mArray = new Object[size<<1];
size<<1，就相当于size*2，这里是位运算，效率更高，不过这是没有命中缓存的情况，arraymap还有个很特殊的地方，就是有个全局的静态缓存数组
全局静态缓存池
private static final int CACHE_SIZE = 10;
static @Nullable Object[] mBaseCache;
static int mBaseCacheSize;
static @Nullable Object[] mTwiceBaseCache;
static int mTwiceBaseCacheSize;
上面可以看到，缓存的数组都是static的，说明是全局静态变量，不管new多少个arraymap，都是用这个同一个缓存池，看下存入缓存的代码
存入的时机，是在数组扩容后，旧的数组就会存入缓存池
private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
if (hashes.length == (BASE_SIZE*2)) {
//数组长度是8
synchronized (SimpleArrayMap.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++;
}
} else if (hashes.length == BASE_SIZE) {
//数组长度是4
synchronized (SimpleArrayMap.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++;
}
}
}
}
只有长度是4跟8的数组，才会参与全局缓存，缓存的方式也很有新意，直接用数组的第一个值引用整个value数组，第二个值引用hash数组，其他值置空，最多缓存10组数组
然后在使用的时候，如果长度是4跟8，就会先从缓存里面取
if (size == (BASE_SIZE*2)) {
synchronized (SimpleArrayMap.class) {
if (mTwiceBaseCache != null) {
final Object[] array = mTwiceBaseCache;
mArray = array;
mTwiceBaseCache = (Object[])array[0];
mHashes = (int[])array[1];
array[0] = array[1] = null;
mTwiceBaseCacheSize--;
return;
}
}
} else if (size == BASE_SIZE) {
synchronized (SimpleArrayMap.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;
}
}
}
直接把array的引用设置给mArray，然后mBaseCache再引用下一个缓存的array，直接用数组本身实现了数组的缓存读取
数组长度可以缩小
这个是arraymap特有的逻辑，当存储的内容变少，数组会缩小，减少内存占用，而HashMap，只会增加，不会减少
if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
//当内容的长度，只有数组长度的三分之一，并且数组长度大于8，触发缩小
final int n = osize > (BASE_SIZE*2) ? (osize + (osize>>1)) : (BASE_SIZE*2);
//新的长度是当前内容长度是1.5倍
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);
}
}
当内容的长度，只有当前数组的三分之一，就触发数组缩放，缩放后的数组长度是内容长度的1.5倍，最小长度到8
定位位置
arraymap也是用hash来定位位置，二分法查找的方式，算法复杂度是O(logn)，而hashmap的复杂度，大多数没有hash冲突的情况下，都是O(1)，可以看下代码
看下二分法查找的代码
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
}
get方法还是put方法，都是需要二分法查找位置，由于需要满足二分法，mHashes跟mArray需要按照从小到大排序，当插入一个值的时候，就需要频繁的挪到整个数组
System.arraycopy(mHashes, index, mHashes, index + 1, osize - index);
System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
而arraycopy其实是一个蛮重的方法，需要一个个挪动数组里面的数值，而且每次还需要挪动两个数组
总结
建议统一使用hashmap，或者在数组长度小于等于8的时候，使用arraymap，另外，arraymap存在两个版本，一个是AndroidX，一个是系统framework
//framework自带的arraymap
android.util.ArrayMap
//Androidx的arraymap
androidx.collection.ArrayMap
使用的时候，切记使用Androidx的arraymap，以保证在所有版本的系统上，表现一致
腾讯云开发者
