买一送一：SparseArray & ArrayMap
现在在用Android Studio时， 使用HashMap的时候，都会提示hint说可以用SparseArray替代了
什么是SparseArray？反正我搜了一下国内的blog，基本没有把它说清楚的，更有甚者竟然和稀疏矩阵关联起来了，简直不知所云
个么只有自己来倒腾一下了：
1 public class SparseArray<E> implements Cloneable {
2 private static final Object DELETED = new Object();
3 private boolean mGarbage = false;
4
5 private int[] mKeys;
6 private Object[] mValues;
7 private int mSize;
8
9 /**
10 * Creates a new SparseArray containing no mappings.
11 */
12 public SparseArray() {
13 this(10);
14 }
15
16 /**
17 * Creates a new SparseArray containing no mappings that will not
18 * require any additional memory allocation to store the specified
19 * number of mappings. If you supply an initial capacity of 0, the
20 * sparse array will be initialized with a light-weight representation
21 * not requiring any additional array allocations.
22 */
23 public SparseArray(int initialCapacity) {
24 if (initialCapacity == 0) {
25 mKeys = EmptyArray.INT;
26 mValues = EmptyArray.OBJECT;
27 } else {
28 mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
29 mKeys = new int[mValues.length];
30 }
31 mSize = 0;
32 }
33
34 // blahblah.......
35 }稍微解释一下一些关键的成员变量：
-
DELETED 一个删除标记
-
mGarbage 是否需要gc
-
mKeys 存放key的int数组
-
mValues 存放具体value的数组
-
mSize 记录当前存了多少内容
这么看来， 这个SparseArray只不过是两个数组分别用来存key和value嘛， 继续看put：
1 public void put(int key, E value) {
2
3 // 将在mKeys的 0 到 mSize 的区间内查找 key 的下标, 也就是key所在的index
4 int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
5
6 // mKeys中0-mSize中存在这个key， 说明之前已经存过， 直接更改mValues对应下标的内容，
7 // 这样看来， mValues和mKeys是一一对应的
8 if (i >= 0) {
9 mValues[i] = value;
10 } else { // 二分找不到， 就会返回一个负的下标， 代表比要找的数小的第一个数的index*-1
11 i = ~i; // 取反就是正的index了
12
13 // 如果这个index中的值失效则把这个index换成当前要存的内容(both key and value)
14 if (i < mSize && mValues[i] == DELETED) {
15 mKeys[i] = key;
16 mValues[i] = value;
17 return;
18 }
19 // 如果需要gc，并且数组的容量已经无法放下一个新的值
20 if (mGarbage && mSize >= mKeys.length) {
21 // gc主要就是调整两个数组，将被删除的元素清空，使得数组内容是紧凑的
22 gc();
23
24 // Search again because indices may have changed. 再找一遍
25 i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
26 }
27
28 mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key); // 插入！
29 mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
30 mSize++;
31 }
32 }顺带提一下mGarbage， 当做remove或者是clear等操作时， 这个boolean会设成true， 说明有元素被标记为DELETED了， 这时就需要重新调整结构
想必过程已经很清楚了吧，我还不会画图，就先看注释理解好了
再来看get()就很轻松了：
1 public E get(int key, E valueIfKeyNotFound) {
2
3 // 还是找key的index
4 int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
5 // 如果没有或者被删了
6 if (i < 0 || mValues[i] == DELETED) {
7 return valueIfKeyNotFound;
8 } else { // 返回mValues中index对应的值
9 return (E) mValues[i];
10 }
11 }这下全清楚了，所以为什叫SparseArray， 因为key的值是离散的，但是key的index要是连续的
ArrayMap
SparseArray的key只能是int，但是这个局限性太大了，因此有了ArrayMap，这个就复杂多了，大致讲一下框架吧：
1 public final class ArrayMap<K, V> implements Map<K, V> {
2 private static final boolean DEBUG = false;
3 private static final String TAG = "ArrayMap";
4
5 /**
6 * The minimum amount by which the capacity of a ArrayMap will increase.
7 * This is tuned to be relatively space-efficient.
8 */
9 private static final int BASE_SIZE = 4;
10
11 /**
12 * Maximum number of entries to have in array caches.
13 */
14 private static final int CACHE_SIZE = 10;
15
16 /**
17 * @hide Special immutable empty ArrayMap.
18 */
19 public static final ArrayMap EMPTY = new ArrayMap(true);
20
21 /**
22 * Caches of small array objects to avoid spamming garbage. The cache
23 * Object[] variable is a pointer to a linked list of array objects.
24 * The first entry in the array is a pointer to the next array in the
25 * list; the second entry is a pointer to the int[] hash code array for it.
26 */
27 static Object[] mBaseCache;
28 static int mBaseCacheSize;
29 static Object[] mTwiceBaseCache;
30 static int mTwiceBaseCacheSize;
31
32 /**
33 * Special hash array value that indicates the container is immutable.
34 */
35 static final int[] EMPTY_IMMUTABLE_INTS = new int[0];
36
37 int[] mHashes;
38 Object[] mArray;
39 int mSize;
40 // blahblah...
41 }不管上面的一陀， 先抓住重点， 数据结构就是倒数这几行
是不是有点熟悉， 是不是跟SparseArray有几分相似？
照例， put():
1 @Override
2 public V put(K key, V value) {
3 final int hash;
4 int index;
5 if (key == null) { // key可以为null，先不管了
6 hash = 0;
7 index = indexOfNull();
8 } else {
9 hash = key.hashCode(); // 得到key的hash值
10 index = indexOf(key, hash); // 还是一样，找index
11 }
12 if (index >= 0) { // 说明之前存过啦
13 index = (index<<1) + 1; // 注意这里要将index*2+1
14 final V old = (V)mArray[index]; // 更新value
15 mArray[index] = value;
16 return old;
17 }
18
19 index = ~index; // 找不到咯，那就取反咯
20 if (mSize >= mHashes.length) { // 不够用了
21 final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
22 : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
23
24 if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n);
25
26 final int[] ohashes = mHashes;
27 final Object[] oarray = mArray;
28 allocArrays(n); // 先缓存再堆分配
29
30 if (mHashes.length > 0) {
31 if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0");
32 // 直接拷贝
33 System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
34 System.arraycopy(oarray, 0, mArray, 0, oarray.length);
35 }
36
37 freeArrays(ohashes, oarray, mSize);
38 }
39
40 if (index < mSize) {
41 if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index)
42 + " to " + (index+1));
43 // 将index以后的数据往后移动一格
44 System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index);
45 System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
46 }
47
48 // mHashes中放key的hash值
49 mHashes[index] = hash;
50 // mArray[index*2]放key， 再下一位放value
51 mArray[index<<1] = key;
52 mArray[(index<<1)+1] = value;
53 mSize++;
54 return null;
55 }大致框架还是很清楚的，逻辑跟SparseArray还是很相似的，区别在于mHashes里面存的是key的hash值(hash值有可能冲突，put里面看不清楚到底什么逻辑), 对应mArray里连续两位分别放真正的key和value
看完ge我们就知道它到底怎么处理冲突的了：
1 @Override
2 public V get(Object key) {
3 final int index = indexOfKey(key);
4 return index >= 0 ? (V)mArray[(index<<1)+1] : null;
5 }
6
7 public int indexOfKey(Object key) {
8 return key == null ? indexOfNull() : indexOf(key, key.hashCode());
9 }
10
11 int indexOf(Object key, int hash) {
12 final int N = mSize;
13
14 // Important fast case: if nothing is in here, nothing to look for.
15 if (N == 0) {
16 return ~0;
17 }
18
19 int index = ContainerHelpers.binarySearch(mHashes, N, hash);
20
21 // If the hash code wasn't found, then we have no entry for this key.
22 if (index < 0) {
23 return index;
24 }
25
26 // If the key at the returned index matches, that's what we want.
27 if (key.equals(mArray[index<<1])) {
28 return index;
29 }
30
31 // Search for a matching key after the index.
32 int end;
33 for (end = index + 1; end < N && mHashes[end] == hash; end++) {
34 if (key.equals(mArray[end << 1])) return end;
35 }
36
37 // Search for a matching key before the index.
38 for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
39 if (key.equals(mArray[i << 1])) return i;
40 }
41
42 // Key not found -- return negative value indicating where a
43 // new entry for this key should go. We use the end of the
44 // hash chain to reduce the number of array entries that will
45 // need to be copied when inserting.
46 return ~end;
47 }get方法很简单， 关键是如何找到index
注释写的很清楚，根据indexOf()的逻辑, 先通过hash值找到mHashes里的index， 但是hash值是有可能冲突的，因此两个for循环，分别去对应mArray中往前往后一一去通过key.equals()匹配，这样去解决hash冲突的
总结
其实仔细一想， 无论是SparseArray或者是ArrayMap，在执行效率上，无论是从查找、解决冲突、扩展容量来看，都并不优于HashMap
那为什么要极力推荐前两者呢？
因为在Android，主要矛盾还是内存的占用，HashMap内部维护的链表占用的内存开销更大，而前两者只用数组就解决了空间问题， 当然了，SparseArray还没有自动装箱拆箱的损耗， 因此，以后在Android中用到map， 我会尽量使用这样的数据结构而避免使用HashMap了