Start
前言
ArrayMap 是一种通用的键->值映射数据结构，旨在比传统内存效率更高 HashMap。它将其映射保留在数组数据结构中每个项目的哈希码整数数组，以及键/值对的 Object 数组。这样一来，它就不必为放置在 Map 中的每个条目创建一个额外的对象，并且还尝试更积极地控制这些数组的大小增长（因为增长它们仅需要复制数组中的条目，而不是复制数组中的条目重建哈希图）。
请注意，此实现不适用于可能包含大量项目的数据结构。它通常比传统的 HashMap 慢，因为查找需要二进制搜索，添加和删除需要在数组中插入和删除条目。对于容纳多达数百个物品的容器，性能差异并不明显，小于 50％。
因为此容器旨在更好地平衡内存使用，所以与大多数其他标准 Java 容器不同，它会在删除项目时缩小其数组。
1. ArrayMap 的初始化
public ArrayMap() {}
public ArrayMap(int capacity) {}
public ArrayMap(int capacity, boolean identityHashCode) {}
public ArrayMap(ArrayMap<K, V> map) {}
JDK1.8 里面提供了四个构造方法
1.1 默认构造方法
/**
* 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);
}
第一个构造方法创建一个空的ArrayMap，默认容量是0.当有Item被添加进来，会自动扩容。
1.2 指定容量的构造方法
/**
* Create a new ArrayMap with a given initial capacity.
*/
public ArrayMap(int capacity) {
this(capacity, false);
}
创建一个指定容量的ArrayMap
1.3 指定容量和 identityHashCode
public ArrayMap(int capacity, boolean identityHashCode) {
mIdentityHashCode = identityHashCode;
//数量< 0，构建一个不可变的ArrayMap
if (capacity < 0) {
mHashes = EMPTY_IMMUTABLE_INTS;
mArray = EmptyArray.OBJECT;
//数量= 0，构建空的mHashes mArray
} else if (capacity == 0) {
mHashes = EmptyArray.INT;
mArray = EmptyArray.OBJECT;
} else {//数量>0,分配空间初始化数组
allocArrays(capacity);
}
mSize = 0;
}
看一下 扩容的方法 allocArrays ：
private void allocArrays(final int size) {
//数量< 0，构建一个不可变的ArrayMap
if (mHashes == EMPTY_IMMUTABLE_INTS) {
throw new UnsupportedOperationException("ArrayMap is immutable");
}//扩容数量是 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和mArray，mArray是mHashes的两倍。因为它既要存key还要存value。
mHashes = new int[size];
mArray = new Object[size<<1];
}
1.4 利用另一个map构建ArrayMap
/**
* Create a new ArrayMap with the mappings from the given ArrayMap.
*/
public ArrayMap(ArrayMap<K, V> map) {
this();
if (map != null) {
putAll(map);
}
}
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));
}
}
}
//确保空间足够存放 minimumCapacity 个数据
public void ensureCapacity(int minimumCapacity) {
//如果不够扩容
if (mHashes.length < minimumCapacity) {
//暂存当前的hash array。后面复制需要
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
//扩容空间（开头讲过这个函数）
allocArrays(minimumCapacity);
if (mSize > 0) {//如果原集合不为空，复制原数据到新数组中
System.arraycopy(ohashes, 0, mHashes, 0, mSize);
System.arraycopy(oarray, 0, mArray, 0, mSize<<1);
}
//释放回收临时暂存数组空间
freeArrays(ohashes, oarray, mSize);
}
}
//释放回收临时暂存数组空间
private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
//如果容量是8， 则将hashes 和array 缓存起来，以便下次使用
if (hashes.length == (BASE_SIZE*2)) {
synchronized (ArrayMap.class) {
if (mTwiceBaseCacheSize < CACHE_SIZE) {
//0存，前一个缓存的cache
array[0] = mTwiceBaseCache;
//1 存 int[]数组
array[1] = hashes;
//2+ 元素置空 以便GC
for (int i=(size<<1)-1; i>=2; i--) {
array[i] = null;
}
//更新缓存引用为array
mTwiceBaseCache = array;
//增加缓存过的Array的数量
mTwiceBaseCacheSize++;
if (DEBUG) Log.d(TAG, "Storing 2x cache " + array
+ " now have " + mTwiceBaseCacheSize + " entries");
}
}//相同逻辑，只不过缓存的是int[] 容量为4的数组
} 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");
}
}
}
}
2. 插入元素 put()
//如果key存在，则返回oldValue
public V put(K key, V value) {
//key的hash值
final int hash;
//下标
int index;
// 如果key为null，则hash值为0.
if (key == null) {
hash = 0;
//寻找null的下标
index = indexOfNull();
} else {
//根据mIdentityHashCode 取到 hash值
hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
//根据hash值和key 找到合适的index
index = indexOf(key, hash);
}
//如果index>=0,说明是替换（改）操作
if (index >= 0) {
//只需要更新value 不需要更新key。因为key已经存在
index = (index<<1) + 1;
//返回旧值
final V old = (V)mArray[index];
mArray[index] = value;
return old;
}
//index<0,说明是插入操作。 对其取反，得到应该插入的下标
index = ~index;
//如果需要扩容
if (mSize >= mHashes.length) {
//如果容量大于8，则扩容一半。
//否则容量大于4，则扩容到8.
//否则扩容到4
final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
: (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
//临时数组
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
//分配空间完成扩容
allocArrays(n);
//复制临时数组中的数组进新数组
if (mHashes.length > 0) {
if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0");
System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
System.arraycopy(oarray, 0, mArray, 0, oarray.length);
}
//释放临时数组空间
freeArrays(ohashes, oarray, mSize);
}
//如果index在中间，则需要移动数组，腾出中间的位置
if (index < mSize) {
if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index)
+ " to " + (index+1));
System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index);
System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
}
//hash数组，就按照下标存哈希值
mHashes[index] = hash;
//array数组，根据下标，乘以2存key，乘以2+1 存value
mArray[index<<1] = key;
mArray[(index<<1)+1] = value;
mSize++;//修改size
return null;
}
put 方法调用了其他几个内部的方法，其中关于扩容以及如何释放空间，申请新的空间这些，从算法层来讲其实不重要，只要知道一点就是，扩容会发生数据的复制，这个是会影响效率的就可以了。而与算法相关性较大的 indexOfNull() 方法以及 indexOf() 方法的实现。
先来看一下 indexOfNull() 方法：
//返回key为null的 下标index
int indexOfNull() {
//N为当前集合size
final int N = mSize;
//如果当前集合是空的，返回~0
if (N == 0) {//
return ~0;
}
//根据hash值=0，通过二分查找，查找到目标index
int index = ContainerHelpers.binarySearch(mHashes, N, 0);
//如果index《0，则hash值=0之前没有存储过数据
if (index < 0) {
return index;
}
//如果index>=0,说明该hash值，之前存储过数据，找到对应的key，比对key是否等于null。相等的话，返回index。说明要替换。
//关于array中对应数据的位置，是index*2 = key ,index*2+1 = value.
if (null == mArray[index<<1]) {
return index;
}
//以下两个for循环是在出现hash冲突的情况下，找到正确的index的过程：
//从index+1,遍历到数组末尾，找到hash值相等，且key相等的位置，返回
int end;
for (end = index + 1; end < N && mHashes[end] == 0; end++) {
if (null == mArray[end << 1]) return end;
}
//从index-1,遍历到数组头，找到hash值相等，且key相等的位置，返回
for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) {
if (null == mArray[i << 1]) return I;
}
// key没有找到，返回一个负数。代表应该插入的位置
return ~end;
}
看一下 * indexOf()* 方法：
//根据key和key的hash值，返回index
int indexOf(Object key, int hash) {
//N为当前集合size
final int N = mSize;
//如果当前集合是空的，返回~0
if (N == 0) {
return ~0;
}
//根据hash值，通过二分查找，查找到目标index
int index = ContainerHelpers.binarySearch(mHashes, N, hash);
//如果index《0，说明该hash值之前没有存储过数据
if (index < 0) {
return index;
}
//如果index>=0,说明该hash值，之前存储过数据，找到对应的key，比对key是否相等。相等的话，返回index。说明要替换。
if (key.equals(mArray[index<<1])) {
return index;
}
//以下两个for循环是在出现hash冲突的情况下，找到正确的index的过程：
//从index+1,遍历到数组末尾，找到hash值相等，且key相等的位置，返回
int end;
for (end = index + 1; end < N && mHashes[end] == hash; end++) {
if (key.equals(mArray[end << 1])) return end;
}
//从index-1,遍历到数组头，找到hash值相等，且key相等的位置，返回
for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
if (key.equals(mArray[i << 1])) return I;
}
// key没有找到，返回一个负数。代表应该插入的位置
return ~end;
}
上面的结论可能还是让人觉得有点晕，那么再来看看下面的图吧，就一定能明白了。
上面图说， index == 0 时 和 index == 1时的 hash code 是一样的，说明 key1 与 key2 的 hash code 是一样的，也就是存在 hash 冲突了。那么，如上，这里的解决办法就是 hash code 存储了 2 份，而 key-value 分别存储一份。
3. 批量增 putAll(Map）
//批量增，接受更为广泛的Map参数
public void putAll(Map<? extends K, ? extends V> map) {
//确保空间容量足够
ensureCapacity(mSize + map.size());
for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
//分别调用单个增方法 add
put(entry.getKey(), entry.getValue());
}
}
小结：
- 增的流程：
- 先根据key得到hash值
- 根据hash值得到 index
- 根据 index 正负，得知是插入还是替换
- 如果是替换直接替换值即可
- 如果是插入，则先判断是否需要扩容，并进行扩容
- 挪动数组位置，插入元素（类似ArrayList）
- 插入允许 key 为 null，value 为 null。
- 每次插入时，根据 key 的哈希值，利用二分查找，去寻找 key 在 int[] mHashes 数组中的下标位置。
- 如果出现了 hash 冲突，则从需要从目标点向两头遍历，找到正确的 index。
- 如果 index>=0，说明之前已经存在该 key，需要替换（改）。
- 如果 index<0，说明没有找到。（也是二分法特性）对 index 去反，可以得到这个 index 应该插入的位置。
- 根据 key 的 hash 值在 mHashs 中的 index，
如何得到 key、value 在 mArray 中的下标位置呢？
key 的位置是 index2，value 的位置是 index2+1，也就是说 mArray 是利用连续的两位空间去存放 key、value。 - 根据 hash 值的 index 计算，key、value 的 index 也利用了位运算。index<<1 和 (index<<1)+1。
4. 单个删 remove
//如果对应key有元素存在，返回value。否则返回null
public V remove(Object key) {
//根据key，找到下标
final int index = indexOfKey(key);
if (index >= 0) {
//如果index>=0,说明key有对应的元素存在，则去根据下标删除
return removeAt(index);
}
//否则返回null
return null;
}
//根据下标删除元素
public V removeAt(int index) {
//根据index，得到value
final Object old = mArray[(index << 1) + 1];
//如果之前的集合长度小于等于1，则执行过删除操作后，集合现在就是空的了
if (mSize <= 1) {
// Now empty.
if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0");
//释放回收空间
freeArrays(mHashes, mArray, mSize);
//置空
mHashes = EmptyArray.INT;
mArray = EmptyArray.OBJECT;
mSize = 0;
} else {//根据元素数量和集合占用的空间情况，判断是否要执行收缩操作
//如果 mHashes长度大于8，且 集合长度 小于当前空间的 1/3,则执行一个 shrunk，收缩操作，避免空间的浪费
if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
// Shrunk enough to reduce size of arrays. We dont allow it to
// shrink smaller than (BASE_SIZE*2) to avoid flapping between
// that and BASE_SIZE.
//如果当前集合长度大于8，则n为当前集合长度的1.5倍。否则n为8.
//n 为收缩后的 mHashes长度
final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2);
if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n);
//分配新的更小的空间（收缩操作）
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
allocArrays(n);
//删掉一个元素，所以修改集合元素数量
mSize--;
//因为执行了收缩操作，所以要将老数据复制到新数组中。
if (index > 0) {
if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0");
System.arraycopy(ohashes, 0, mHashes, 0, index);
System.arraycopy(oarray, 0, mArray, 0, index << 1);
}
//在复制的过程中，排除不复制当前要删除的元素即可。
if (index < mSize) {
if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + mSize
+ " to " + index);
System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index);
System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1,
(mSize - index) << 1);
}
} else {//不需要收缩
//修改集合长度
mSize--;
//类似ArrayList，用复制操作去覆盖元素达到删除的目的。
if (index < mSize) {
if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + mSize
+ " to " + index);
System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index);
System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1,
(mSize - index) << 1);
}
//记得置空，以防内存泄漏
mArray[mSize << 1] = null;
mArray[(mSize << 1) + 1] = null;
}
}
//返回删除的值
return (V)old;
}
5. 批量删除 removeAll
//从ArrayMap中，删除Collection集合中，所有出现的key。
//返回值代表是否成功删除元素
public boolean removeAll(Collection<?> collection) {
return MapCollections.removeAllHelper(this, collection);
}
//MapCollections.removeAllHelper(this, collection);
//遍历Collection，调用Map.remove(key)去删除元素;
public static <K, V> boolean removeAllHelper(Map<K, V> map, Collection<?> collection) {
int oldSize = map.size();
Iterator<?> it = collection.iterator();
while (it.hasNext()) {
map.remove(it.next());
}
//如果元素不等，说明成功删除元素
return oldSize != map.size();
}
6. get 方法
public V get(Object key) {
//根据key去得到index
final int index = indexOfKey(key);
//根据 index*2+1 得到value
return index >= 0 ? (V)mArray[(index<<1)+1] : null;
}
public int indexOfKey(Object key) {
//判断key是否是null，并去查询key对应的index
return key == null ? indexOfNull()
: indexOf(key, mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());
}
7. 总结
ArrayMap 的实现细节很多地方和 ArrayList 很像，由于我们之前分析过面试必备：ArrayList 源码解析（JDK8）。所以对于用数组复制覆盖去完成删除等操作的细节，就比较容易理解了。
- 每次插入时，根据 key 的哈希值，利用二分查找，去寻找 key 在 int[] mHashes 数组中的下标位置。
- 如果出现了 hash 冲突，则从需要从目标点向两头遍历，找到正确的 index。
- 扩容时，会查看之前是否有缓存的 int[] 数组和 object[] 数组
如果有，复用给 mArray mHashes。 - 扩容规则：如果容量大于 8，则扩容一半。（类似 ArrayList）
根据 key 的 hash 值在 mHashs 中的 index。
如何得到 key、value 在 mArray 中的下标位置呢？
key 的位置是 index2，value 的位置是 index2+1,也就是说 mArray 是利用连续的两位空间去存放 key、value。 - 根据元素数量和集合占用的空间情况，判断是否要执行收缩操作
如果 mHashes 长度大于 8，且 集合长度小于当前空间的 1/3，则执行一个 shrunk，收缩操作，避免空间的浪费。 - 类似 ArrayList，用复制操作去覆盖元素达到删除的目的。
参考文献：
https://blog.csdn.net/zxt0601/article/details/78333328
申明：开始和结束图片来源网络，侵删
End
网友评论