/** {@hide} */
public ArrayMap(int capacity, boolean identityHashCode) {
// 是否返回系统唯一 hashcode
mIdentityHashCode = identityHashCode;
// If this is immutable, use the sentinal EMPTY_IMMUTABLE_INTS
// instance instead of the usual EmptyArray.INT. The reference
// is checked later to see if the array is allowed to grow.
if (capacity < 0) {
// 不可变 ArrayMap
mHashes = EMPTY_IMMUTABLE_INTS;
mArray = EmptyArray.OBJECT;
} else if (capacity == 0) {
// 空 ArrayMap
mHashes = EmptyArray.INT;
mArray = EmptyArray.OBJECT;
} else {
allocArrays(capacity);
}
// 容量
mSize = 0;
}
private void allocArrays(final int size) {
if (mHashes == EMPTY_IMMUTABLE_INTS) {
throw new UnsupportedOperationException("ArrayMap is immutable");
}
// 保存 hash 值大小的数组
mHashes = new int[size];
// 保存 key， value 的数据，2倍。
mArray = new Object[size<<1];
}
上面是基本的构造函数，负责给 ArrayMap 的存储结构分配大小，下面看一下具体的 put 和 get 操作。
// 如果 key 存在，则返回 oldValue
@Override
public V put(K key, V value) {
final int osize = mSize;
final int hash;
int index;
if (key == null) {
hash = 0;
// 寻找 null 的下标
index = indexOfNull();
} else {
hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
// 下标，二分查找
index = indexOf(key, hash);
}
// key 存在，找到值并返回
if (index >= 0) {
index = (index<<1) + 1;
final V old = (V)mArray[index];
mArray[index] = value;
return old;
}
// index < 0, 说明是插入操作
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;
// get 操作主要是找到下标
@Override
public V get(Object key) {
final int index = indexOfKey(key);
return index >= 0 ? (V)mArray[(index<<1)+1] : null;
}
下面来看一下 查找下标的操作：
int indexOf(Object key, int hash) {
// 当前数据的大小
final int N = mSize;
// Important fast case: if nothing is in here, nothing to look for.
// 如果大小为0，说明没有数据存在，返回 -1 表示插入
if (N == 0) {
return ~0;
}
// 二分查找到下标
int index = binarySearchHashes(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;
}
// Search for a matching key after the index.
// 遇到冲突，开放地址发解决冲突，从前往后找
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;
}
// Key not found -- return negative value indicating where a
// new entry for this key should go. We use the end of the
// hash chain to reduce the number of array entries that will
// need to be copied when inserting.
// 未找到是取反表示需要插入的位置
return ~end;
}
SparseArray
与上面介绍的一样，也是用来在 key 为 int 类型时代替 HashMap 的，直接看源码吧。采用稀疏数组保存数据。
// 默认容量是 10
public SparseArray(int initialCapacity) {
if (initialCapacity == 0) {
mKeys = EmptyArray.INT;
mValues = EmptyArray.OBJECT;
} else {
// 数组，存储的 value
mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
// key，int 类型
mKeys = new int[mValues.length];
}
mSize = 0;
}
public void put(int key, E value) {
// 二分查到到下标
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
mValues[i] = value;
} else {
i = ~i;
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
if (mGarbage && mSize >= mKeys.length) {
gc();
// Search again because indices may have changed.
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}
SparseArray and ArrayMap
[TOC]
Android 设备为了较少内存的使用和装拆箱损耗的性能，提供一些特有的数据结构代替 java 中原来的数据结构，适当采用这些数据结构可以优化应用的内存。
ArrayMap
用于代替 HashMap 使用，有几个特点：
上面是基本的构造函数，负责给 ArrayMap 的存储结构分配大小，下面看一下具体的 put 和 get 操作。
下面来看一下 查找下标的操作：
SparseArray
与上面介绍的一样，也是用来在 key 为 int 类型时代替 HashMap 的，直接看源码吧。采用稀疏数组保存数据。
get 操作就是一个取下标的过程。
用Bundle而不是用HashMap来进行数据传递
总结
在 Android 系统是可以使用 Arraymap 和 SparseArray 来代替 HashMap 的使用。
其中前者直接用数组存储 key 和 value， 而不是使用 Entry 对象。点那个数组需要增长时，无需重新构建 hash。
而后者主要是解决 hashMap 自动装拆箱过程带来的内存消耗，并且使用稀疏数组存储数据。
两者都是围绕时间换空间的方式来解决移动端内存有限的问题，但是都只适用于数据量比较小的情况，官方推荐不超过 1000。