ArrayMap源码分析
2019-09-26 本文已影响0人
魔焰之
| 存储结构 |默认大小 | 线程安全 | 扩容机制 | 删除策略 |
|--|--|--|--|--|--|--|--|
| 双数组 |0 |否|n<4:4; n<8:8;n>=8:1.5n;|直接删除，并带有部分内存收缩操作|||||||
成员变量
static Object[] mBaseCache;//缓存的长度为4的key和value的内存，其结构下文会详细说明
static int mBaseCacheSize;//缓存的个数，大小在10个以内
static Object[] mTwiceBaseCache;//缓存的长度为8的key和value的内存
static int mTwiceBaseCacheSize;//缓存的个数，大小在10个以内
final boolean mIdentityHashCode;//生成hashcode的方法，mIdentityHashCode ? System.identityHashCode(key) : key.hashCode()System.identityHashCode
int[] mHashes;//存储key的hash值，升序
Object[] mArray;//存储key和value的值，key的下一个数据项就是该key对应的value
int mSize;//当前集合存储的数据个数
创建集合
public ArrayMap(int capacity) {
this(capacity, false);
}
/** {@hide} */
public ArrayMap(int capacity, boolean identityHashCode) {
mIdentityHashCode = identityHashCode;
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设置小于0的容量时，并不会直接报错，然后大于0时主要使用allocArrays去初始化集合
private void allocArrays(final int size) {
if (mHashes == EMPTY_IMMUTABLE_INTS) {
throw new UnsupportedOperationException("ArrayMap is immutable");
}
if (size == (BASE_SIZE*2)) {
synchronized (ArrayMap.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 (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;
}
}
}
mHashes = new int[size];
mArray = new Object[size<<1];
}
allocArrays方法主要分为3步：
- 如果之前设置了容量小于0，则不允许申请内存
- 如果当前申请的size为4或者8，而且当前对应缓存存在可用，则使用缓存
- 否则直接初始化新的数组，mHashes长度为size，mArray长度为2倍mHashes，其原因是因为mArray中存储的是key和value，而mHasher中存储的仅为key的hash值
关于缓存结构
缓存结构
在缓存结构上，mBaseCache和mTwiceBaseCache是一致的，只是在存在的数据的长度上不一样，如上图，长度为2的数int类型的数组，对应于mHashes，长度为4的是Object类型的数组，对应于mArray。可以看出Object数组中的第一项指向下一个缓存，第二项为当前缓存的存储hash值的int缓存数组
插入数据
@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);
}
if (index >= 0) {
index = (index<<1) + 1;
final V old = (V)mArray[index];
mArray[index] = value;
return old;
}
index = ~index;
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);
}
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;
}
插入操作分为如下步骤：
- 通过key和hash定位到该key在mHashes和mArray当中的下标。因为mHashes中到hash值是升序存储，这里采用了二分法查找，因为存在hash冲突，所以还得比较key是否相等，可以参照ArrayMap结构图。
- 如果找到下标（index>=0）,则覆盖原来到value，并返回该值
- 如果没找到（index<0），则～index为插入到期望下标，此时如果mHashes已满，则申请扩容，并释放或者缓存原来的内存。如果mHashes未满，则使用System的arraycopy方法移动数据，以为即将插入的数据腾出空间。
-
对应index上插入key和value，并更新size
ArrayMap结构图
这里关注下扩容细节，主要三个方面，扩容大小的计算、扩容内存申请和老数据迁移，老内存的处理；
final int n = osize >= (BASE_SIZE2) ? (osize+(osize>>1))
: (osize >= BASE_SIZE ? (BASE_SIZE2) : BASE_SIZE);
扩容大小的计算根据当前不同的size处理不一样：
- 如果osize>=8:则新的size为osize的3/2
- 如果osize<8 && osize >= 4：则新size为8
- 如果osize<4:则新size为4
扩若内存的申请使用allocArrays方法，该方法我们分析过，会优先尝试使用缓存，不存在缓存才申请对应内存，需要注意的是该方法会给mHashes和mArray重新赋值，而老数据的迁移则使用了System.arraycopy进行数据的拷贝。
而老内存的释放，则调用了freeArrays方法：
private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
if (hashes.length == (BASE_SIZE*2)) {
synchronized (ArrayMap.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++;
if (DEBUG) Log.d(TAG, "Storing 2x cache " + array
+ " now have " + mTwiceBaseCacheSize + " entries");
}
}
} else if (hashes.length == BASE_SIZE) {
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++;
if (DEBUG) Log.d(TAG, "Storing 1x cache " + array
+ " now have " + mBaseCacheSize + " entries");
}
}
}
}
freeArrays方法是主要做的事情就是回收老内存，当老数据的长度满足缓存的条件（长度为4或者8）时，且当前缓存个数还未满（10），则将老数组中元素置为空，并将老数组缓存到对应的缓存中，注意这里是头部插入，也就是最后插入的缓存，会最先被使用。
删除元素
删除元素最后会调用到remove方法：
public V removeAt(int index) {
final Object old = mArray[(index << 1) + 1];
final int osize = mSize;
final int nsize;
if (osize <= 1) {
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) {
// Shrunk enough to reduce size of arrays. We don't allow it to
// shrink smaller than (BASE_SIZE*2) to avoid flapping between
// that and BASE_SIZE.
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);
}
mArray[nsize << 1] = null;
mArray[(nsize << 1) + 1] = null;
}
}
if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
throw new ConcurrentModificationException();
}
mSize = nsize;
return (V)old;
}
删除操作接收一个index，表示对应hash在mHashes数组中的下标，在remove方法中，首先通过(index << 1) + 1定位到对应的object数组下标，找到对应的value。接着判断是否只有一个元素，是则直接给mHashes和mArray赋值为EmptyArray，并释放内存。如果不是只有一个元素，则进行下列操作：
- 若当前容量大于8，且当前元素个数小于容量的三分之一，则触发内存收缩操作。收缩后的容量计算方式为：
final int n = osize > (BASE_SIZE2) ? (osize + (osize>>1)) : (BASE_SIZE2);
- 若不满足内存收缩条件，则直接调用System.arraycopy拷贝原数组中元素，覆盖index对应的值，并置空nsize对应的值，更新mSize；
