SimpleArrayMap
SimpleArrayMap 是 Andorid V4 包提供的一种用来代替 HashMap 的数据结构，由于 HashMap 在数据容量过大时时间复杂度会越来与趋近于 O(N) , 故而效率不高。SimpleArrayMap 的实现方式和工作过程使其内存占用更小，在数据量不大时效率更高，所以在 Android 开发中我们可以择机选择适合的方式来实现 Map
下面我们就来一步步分析，为什么 SimpleArrayMap 可以实现更小的内存占用和更加高效查找
一、成员变量
/** * ArrayMap 扩容的最小数量 */private static final int BASE_SIZE = 4;/** * 缓存数组的最大数量，使用小的缓存数组可以避免垃圾回收 */private static final int CACHE_SIZE = 10;// 缓存所用的数组，以及已经换的数量static Object[] mBaseCache;static int mBaseCacheSize;static Object[] mTwiceBaseCache;static int mTwiceBaseCacheSize;/** * 存放 key 的 hash 值的数组 */int[] mHashes;/** * 存放 key 和 value 的数组 */Object[] mArray;/** * 已存键值对的数量 */int mSize;
二、构造方法
/**
* 创建容量为空的 mHashes 和 mArray 数组
*/public SimpleArrayMap() {
mHashes = ContainerHelpers.EMPTY_INTS;
mArray = ContainerHelpers.EMPTY_OBJECTS;
mSize = 0;
}/**
* 根据给定的初始容量创建 mHashes 和 mArray 数组
*/public SimpleArrayMap(int capacity) { if (capacity == 0) {
mHashes = ContainerHelpers.EMPTY_INTS;
mArray = ContainerHelpers.EMPTY_OBJECTS;
} else {
allocArrays(capacity);
}
mSize = 0;
}/**
* 根据给定的 ArrayMap 初始化
*/public SimpleArrayMap(SimpleArrayMap map) { this(); // 调用无参数构造函数
if (map != null) { // 将给定的 ArrayMap 添加
putAll(map);
}
}/**
* 将给定的 ArrayMap 添加本身
*/public void putAll(SimpleArrayMap<? extends K, ? extends V> array) {
final int N = array.mSize;
// 确认容量支持添加给定的 ArrayMap
ensureCapacity(mSize + N); if (mSize == 0) { // 如果原数组容量为 0，则将给定数组添加进新创建的数组中
if (N > 0) {
System.arraycopy(array.mHashes, 0, mHashes, 0, N);
System.arraycopy(array.mArray, 0, mArray, 0, N<<1);
mSize = N;
}
} else { // 如果原数组容量不为 0，则遍历给定数组，将给定数组的值添加到原数组中
for (int i=0; i<N; i++) {
put(array.keyAt(i), array.valueAt(i));
}
}
}/**
* 确认容量支持指定的最小数量，如果当前容量小于指定的数量，则以给定数量创建新的数组
*/public void ensureCapacity(int minimumCapacity) { if (mHashes.length < minimumCapacity) {
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);
}
// 缓存旧的 hash 数组
freeArrays(ohashes, oarray, mSize);
}
}SimpleArrayMap 有三个重载的构造方法，其中给定容量和给定 ArrayMap 的构造方法中涉及到的方法我们下面回一一解析
三、插入方法 put()
public V put(K key, V value) { final int hash; int index; if (key == null) {
hash = 0;
// 查找对应 key 在 hash 值数组中的位置
index = indexOfNull();
} else {
hash = key.hashCode();
// 查找对应 key 在 hash 值数组中的位置
index = indexOf(key, hash);
}
if (index >= 0) { // 存在，直接替换 array 数组中对应位置的 value 值，并将旧值返回
index = (index<<1) + 1; final V old = (V)mArray[index];
mArray[index] = value; return old;
}
index = ~index; // 未找到情况，需要执行插入操作
if (mSize >= mHashes.length) { // 为新插入数组需要扩容旧数组
final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1)) // 当前键值对数量大于等于最小扩容数量的 2 倍时，n 等于 mSeze 的 1.5 倍
: (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE); // 当前键值对数量大于等于最小扩容数量时，n 等于最小扩容量的 2 倍，否则就等于最小扩容量
// 保存旧的 hash 数组
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
// 以最新的容量创建 hash 和 mArray 数组
allocArrays(n);
if (mHashes.length > 0) { // 大于 0 的情况是创建新数组时使用了缓存
// 将旧数组中的数据复制到新数组中
System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
System.arraycopy(oarray, 0, mArray, 0, oarray.length);
} // 将旧数组添加到缓存
freeArrays(ohashes, oarray, mSize);
} if (index < mSize) { // 需要插入到旧数组中间
// 将需要插入位置之后的数据右移一位
System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index);
System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
} // 在 hash 和 array 数组的对应位置插入新值
mHashes[index] = hash;
mArray[index<<1] = key;
mArray[(index<<1)+1] = value;
mSize++; // 键值对数量加 1
return null;
}/**
* 计算 key 为 null 的时候应该插入的位置
*/int indexOfNull() { final int N = mSize; // 键值对为 0 ，直接返回 0
if (N == 0) { return ~0;
}
// 二分法找到对应 0 值在 mHashes 数组中的位置
int index = ContainerHelpers.binarySearch(mHashes, N, 0); // index 小于 0 说明 mHashes 数组中不存存在 0，则直接返回
if (index < 0) { return index;
} // mHashes 中有对应值时，mArray 数组中对应位置为 null，新值可以直接插入，此时直接返回 0 在 mHashes 中的位置
if (null == mArray[index<<1]) { return index;
} // mArray 数组中对应位置不为 null，此时向后寻找 hash 为 0 但 mArray 对应位置为 null 的索引
int end; for (end = index + 1; end < N && mHashes[end] == 0; end++) { if (null == mArray[end << 1]) return end;
} // mArray 数组中对应位置不为 null，此时向前寻找 hash 为 0 但 mArray 对应位置为 null 的索引
for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) { if (null == mArray[i << 1]) return i;
} // 如果未找到 mHashes 中值为 0 且 mArray 数组中对应位置为 null 的索引，则返回当前 hash 数组的长度值加 1 的值取反作为新插入的位置，表明需要插入新的位置
return ~end;
}/**
* 计算 key 应该插入的位置
*/int indexOf(Object key, int hash) { final int N = mSize; // Important fast case: if nothing is in here, nothing to look for.
if (N == 0) { return ~0;
} int index = ContainerHelpers.binarySearch(mHashes, N, hash); // If the hash code wasn't found, then we have no entry for this key.
if (index < 0) { return index;
} // If the key at the returned index matches, that's what we want.
if (key.equals(mArray[index<<1])) { return index;
} // 这里与 indexOfNull() 方法中类似，只不过将 mArray 数组中对应位置的是否为 null 改为了判断 mHashes 数组中的 key 是否相同，如果匹配成功则返回对应位置
int end; for (end = index + 1; end < N && mHashes[end] == hash; end++) { if (key.equals(mArray[end << 1])) return end;
} // Search for a matching key before the index.
for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) { if (key.equals(mArray[i << 1])) return i;
} // 未匹配成功则返回需要插入的位置取反后的值，表明需要插入新的位置
return ~end;
}/**
* 缓存数据 由代码分析可以看到最终添加到缓存的只是 mHashes 数组
* hashes 的长度为最小扩容量或者为最小扩容量的两倍，并且缓存的数量小于最大缓存容量时，才执行缓存操作
*/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[0] 的位置
array[1] = hashes; // 将新的需要缓存的 hash 数组放入 array[1] 的位置
// 通过遍历 array 数组，将其他位置置空
for (int i=(size<<1)-1; i>=2; i--) {
array[i] = null;
} // 将缓存索引重新指向最新的缓存数组
mTwiceBaseCache = array;
// 缓存数量加 1
mTwiceBaseCacheSize++;
}
}
} 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++;·
}
}
}
}/**
* 有缓存时使用缓存创建 hash 数组
*/private void allocArrays(final int size) { 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]; // 使用缓存的 hash 数组
array[0] = array[1] = null; // 缓存数量减 1
mTwiceBaseCacheSize--; if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes
+ " now have " + mTwiceBaseCacheSize + " entries"); 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--; if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes
+ " now have " + mBaseCacheSize + " entries"); return;
}
}
} // 没有缓存或者与缓存长度不匹配时，则直接创建对应长度的 mHashes 数组和 mArray 数组
mHashes = new int[size];
mArray = new Object[size<<1];
}从构造函数和 put 方法来看，SimpleArrayMap 的实现方式为，由一个存储 int 类型 key 的 hash 值的数组 mHashes 和一个同时存储 key 和 value 的 Object 类型的 mArray 数组构成，mArray 会依次按照 key-value 的顺序存储数据
四、查找方法 get()
/**
* 根据 key 获取 value 值
*/public V get(Object key) { // 找到 key 的 hash 值在 mHashes 数组中的索引
final int index = indexOfKey(key);
// 返回 mArray 数组中对应的 value 值
return index >= 0 ? (V)mArray[(index<<1)+1] : null;
}/**
* 找到 key 的 hash 值在 mHashes 数组中的索引
*/public int indexOfKey(Object key) { // indexOfNull 时当 key 为 null 时查找，indexOf 为 key 不为 null 时的查找，上面分析 put() 方法时已经解析过了
return key == null ? indexOfNull() : indexOf(key, key.hashCode());
}/**
* 根据 value 获取 value 对应 key 在 mHashes 数组中的索引，区分 null 可非 null 情况
*/int indexOfValue(Object value) { final int N = mSize*2; final Object[] array = mArray; if (value == null) { for (int i=1; i<N; i+=2) { if (array[i] == null) { return i>>1;
}
}
} else { for (int i=1; i<N; i+=2) { if (value.equals(array[i])) { return i>>1;
}
}
} return -1;
}/**
* 判断 Map 中是否有指定 key
*/public boolean containsKey(Object key) { return indexOfKey(key) >= 0;
}五、移除方法
/**
* 移除指定 key 的键值对
*/public V remove(Object key) { final int index = indexOfKey(key); if (index >= 0) { return removeAt(index);
} return null;
}/**
* 移除指定 hash 数组中位置对应的键值对
*/public V removeAt(int index) { final Object old = mArray[(index << 1) + 1]; if (mSize <= 1) { // 如果键值对数量为小于等于 1，添加缓存后直接清空数组
// Now empty.
freeArrays(mHashes, mArray, mSize);
mHashes = ContainerHelpers.EMPTY_INTS;
mArray = ContainerHelpers.EMPTY_OBJECTS;
mSize = 0;
} else { // 如果数组长度过大，并且数组重的键值对太小，则需要缩小足够的容量以降低数组的大小，但是不会缩小到 BASE_SIZE*2 的值，避免数组容量的摇摆
if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
// 计算压缩后的容量大小
final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2); final int[] ohashes = mHashes; final Object[] oarray = mArray;
// 根据给定容量创建数组
allocArrays(n);
mSize--; if (index > 0) { // index 大于 0，则将旧数组中索引在 0-index 的 hash 对应内容复制到新的数组，不包含 index 位置
System.arraycopy(ohashes, 0, mHashes, 0, index);
System.arraycopy(oarray, 0, mArray, 0, index << 1);
}
// index 小于 mSize 说明，移除的 index 位置的值不是在数组中的最后，此时需要将 index 以后的值同样添加到新的数组中
if (index < mSize) {
System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index);
System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1,
(mSize - index) << 1);
}
} else { // 不需要压缩时，直接将 index 以后的内容全部左移一个单位，再将最后一个键值对置空即可
mSize--; if (index < mSize) {
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;
}
}
// 返回移除的 value 值
return (V)old;
}移除对应位置键值对的过程中还对数组做了缩容处理，可以节省内存，并提升执行查询功能速度
六、其他方法
/**
* 清空 Map
*/public void clear() { if (mSize != 0) {
freeArrays(mHashes, mArray, mSize);
mHashes = ContainerHelpers.EMPTY_INTS;
mArray = ContainerHelpers.EMPTY_OBJECTS;
mSize = 0;
}
}/**
* 获取指定 hash 数组中位置对应的键
*/public K keyAt(int index) { return (K)mArray[index << 1];
}/**
* 获取指定 hash 数组中位置对应的值
*/public V valueAt(int index) { return (V)mArray[(index << 1) + 1];
}/**
* 设置 hash 数组中位置对应的值为指定的 value
*/public V setValueAt(int index, V value) {
index = (index << 1) + 1;
V old = (V)mArray[index];
mArray[index] = value; return old;
}/**
* 判断 Map 是否为空
*/public boolean isEmpty() { return mSize <= 0;
}/**
* 获取键值对数量
*/public int size() { return mSize;
}/**
* equals 方法
* 如果要对比的 object 不是一个 Map 或者不是一个 SimpleArrayMap 则直接返回 false ，键值对数量不想同时也直接返回 false
* 如果以上对比通过，则会对比每一个键值对都会对比，如果键值对都相同则返回 true，否则返回 false
*/public boolean equals(Object object) { if (this == object) { return true;
} if (object instanceof SimpleArrayMap) {
SimpleArrayMap<?, ?> map = (SimpleArrayMap<?, ?>) object; if (size() != map.size()) { return false;
} try { // 遍历当前数组，对比每一个键值对
for (int i=0; i<mSize; i++) {
K key = keyAt(i);
V mine = valueAt(i);
Object theirs = map.get(key); if (mine == null) { if (theirs != null || !map.containsKey(key)) { return false;
}
} else if (!mine.equals(theirs)) { return false;
}
}
} catch (NullPointerException ignored) { return false;
} catch (ClassCastException ignored) { return false;
} return true;
} else if (object instanceof Map) {
Map<?, ?> map = (Map<?, ?>) object; if (size() != map.size()) { return false;
} try { // 遍历当前数组，对比每一个键值对
for (int i=0; i<mSize; i++) {
K key = keyAt(i);
V mine = valueAt(i);
Object theirs = map.get(key); if (mine == null) { if (theirs != null || !map.containsKey(key)) { return false;
}
} else if (!mine.equals(theirs)) { return false;
}
}
} catch (NullPointerException ignored) { return false;
} catch (ClassCastException ignored) { return false;
} return true;
} return false;
}public int hashCode() {
final int[] hashes = mHashes;
final Object[] array = mArray; int result = 0; for (int i = 0, v = 1, s = mSize; i < s; i++, v+=2) {
Object value = array[v];
result += hashes[i] ^ (value == null ? 0 : value.hashCode());
} return result;
}/**
* 打印所有键值对
*/public String toString() { if (isEmpty()) { return "{}";
}
StringBuilder buffer = new StringBuilder(mSize * 28);
buffer.append('{'); for (int i=0; i<mSize; i++) {
if (i > 0) {
buffer.append(", ");
}
Object key = keyAt(i); if (key != this) {
buffer.append(key);
} else {
buffer.append("(this Map)");
}
buffer.append('=');
Object value = valueAt(i); if (value != this) {
buffer.append(value);
} else {
buffer.append("(this Map)");
}
}
buffer.append('}'); return buffer.toString();
}七、总结
到这里整个 SimpleArrayMap 的源码就分析完了，重点要掌握的是由两个数组实现 SimpleArrayMap 的这种数据结构，相比较 HashMap ，SimpleArrayMap 避免了每个键值对都使用 Entry 来包装，并且在查询时如果数据量不大时使用二分法速度更快。并且 SimpleArrayMap 每次 remove 操作时都会做缩容操作，这样可以降低内存使用，并且进一步提升查找时的时间消耗。所以在 Android 开发中，如果键值对的数量级较小情况下使用 SimpleArrayMap 亏更加高效！
作者：renxuelong
链接：https://www.jianshu.com/p/84b0fa3850d9