Android中的ArrayMap源码解析
一、概述
ArrayMap
实现Map<K,V>
接口,所以它也是一个关联数组和哈希表。存储是key-value
结构形式的数据。所以它也是线程不安全,可以允许key,value都为null.
二、特点
ArrayMap
相比HashMap
,空间效率更高内部实现同样基于两个数组,一个
int[]
数组用于保存每个Item的hashCode
,一个Object[]
数组,用于存储key/value键值对。容量是上一个数组的两倍它可以避免在将数据插入Map中时额外的空间消耗(对比HashMap)。
而且它扩容的更合适,扩容时只需要数组拷贝工作,不需要重建哈希表。
和HashMap相比,它不仅有扩容功能,在删除时,如果集合剩余元素少于一定阈值,还有收缩(shrunk)功能。减少空间占用。
对于哈希冲突的解决,查看源码可以得知采用的是开放地址法。
不适合大容量的数据存储。存储大量数据时,它的性能将退化至少50%。
比传统的HashMap时间效率低。因为其会对key从小到大排序,使用二分法查询key对应在数组中的下标。在添加、删除、查找数据的时候都是先使用二分查找法得到相应的index,然后通过index来进行添加、查找、删除等操作。所以其是按照key的大小排序存储的。
三、适用场景
数据量不大
空间比时间重要
需要使用
Map
在Android平台上,相对来说内存空间更宝贵。所以当使用的key是Object类型的
Map
时,考虑使用ArrayMap
替代HashMap
Map<String, String> map = new ArrayMap<>();
map.put("1", "1")
map.put("2", "2")
map.put(null, "3")
map.put("4", null)
Log.d("TAG", "onCreate() called with: map = [" + map + "]");
输出:
onCreate() called with: map = [{1=1, 2=2, null=3, 4=null}]
四、构造器函数
private static final int BASE_SIZE = 4;//扩容默认大小
static final int[] EMPTY_IMMUTABLE_INTS = new int[0];//表示集合不可变
public static final ArrayMap EMPTY = new ArrayMap<>(-1);
static Object[] mBaseCache;
static int mBaseCacheSize;
static Object[] mTwiceBaseCache;
static int mTwiceBaseCacheSize;
final boolean mIdentityHashCode;//是否利用System.identityHashCode(key) 获取唯一HashCode模式。
int[] mHashes;//保存hash值的数组
Object[] mArray;//保存key/value的数组
int mSize;//集合大小
public ArrayMap() {//默认构造器,创建一个空的ArrayMap,默认容量是0.当有Item被添加进来,会自动扩容
this(0, false);
}
public ArrayMap(int capacity) {//指定容量构造器
this(capacity, false);
}
public ArrayMap(int capacity, boolean identityHashCode) {
mIdentityHashCode = identityHashCode;
//容量小于0的时候,创建一个不可变的ArrayMap
if (capacity < 0) {
mHashes = EMPTY_IMMUTABLE_INTS;
mArray = EmptyArray.OBJECT;
} else if (capacity == 0) {//构建空的mHashs、mArray两个数组
mHashes = EmptyArray.INT;
mArray = EmptyArray.OBJECT;
} else {//数量>0,分配空间初始化数组
allocArrays(capacity);
}
mSize = 0;
}
public ArrayMap(ArrayMap<K, V> map) {//指定一个ArrayMap为参数
this();
if (map != null) {
putAll(map);//把传入map全部加入到map中
}
}
//ArrayMap#allocArrays
private void allocArrays(final int size) {
if (mHashes == EMPTY_IMMUTABLE_INTS) {
throw new UnsupportedOperationException("ArrayMap is immutable");
}
//如果初始空间是BASE_SIZE的两倍,也就是扩容容量是8
if (size == (BASE_SIZE*2)) {
synchronized (ArrayMap.class) {
//查看之前是否有缓存的 容量为8的int[]数组和容量为16的object[]数组
//如果有,复用给mArray mHashes
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) {//扩容数量是4
synchronized (ArrayMap.class) {
//查看之前是否有缓存的 容量为4的int[]数组和容量为8的object[]数组
//如果有,复用给mArray mHashes
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];//创建mHashes数组
mArray = new Object[size<<1];//创建mArray,mArray是mHashes的长度两倍,因为既需要存储key也要存储value
}
//ArrayMap#putAll 批量put方法
public void putAll(ArrayMap<? extends K, ? extends V> array) {
final int N = array.mSize;
//确认当前空间是否足够
ensureCapacity(mSize + N);
//如果当前集合为空
if (mSize == 0) {
if (N > 0) {//直接覆盖数组内容
System.arraycopy(array.mHashes, 0, mHashes, 0, N);
System.arraycopy(array.mArray, 0, mArray, 0, N<<1);
mSize = N;
}
} else {//不为空需要一个一个执行插入put操作
for (int i=0; i<N; i++) {
put(array.keyAt(i), array.valueAt(i));
}
}
}
//ArrayMap#ensureCapacity 确保空间足够存放 minimumCapacity 个数据
public void ensureCapacity(int minimumCapacity) {
final int osize = mSize;
//如果不够扩容
if (mHashes.length < minimumCapacity) {
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
//执行扩容
allocArrays(minimumCapacity);
if (mSize > 0) {
//如果原集合不为空,就把原集合数组数据复制过来
System.arraycopy(ohashes, 0, mHashes, 0, osize);
System.arraycopy(oarray, 0, mArray, 0, osize<<1);
}
//释放回收暂存的数组空间
freeArrays(ohashes, oarray, osize);
}
if (CONCURRENT_MODIFICATION_EXCEPTIONS && mSize != osize) {
throw new ConcurrentModificationException();
}
}
五、增、删、改、查
待定
六、总结
ArrayMap的实现细节很多地方都和ArrayList类似,有关ArrayMap几点总结如下:
1、每次插入时,根据key的哈希值,利用二分查找,去寻找key在
int[]mHashes
数组中的下标位置2、如果出现hash冲突,就需要从目标点向两头遍历,找到正确的index
3、扩容时,会查看之前是否存在缓存的
int[]
数组和Object[]
数组4、如果有,复用给mHashes和mArray
5、扩容规则: 如果容量大于8(两倍),则扩容一半
6、根据
key
的hash
值在mHashs
中的index
,如何得到key、value
在mArray
中的下标位置呢?key
的位置是index*2
,value
的位置是index*2+1
,也就是说mArray
是利用连续的两位空间去存放key、value
。7、根据元素数量和集合占用的空间情况,判断是否要执行收缩操作
8、如果 mHashes长度大于8,且 集合长度 小于当前空间的 1/3,则执行一个 shrunk,收缩操作,避免空间的浪费
9、类似ArrayList,用复制操作去覆盖元素达到删除的目的。