概述

HashMap的查找和插入时间复杂度为O(1)的代价是牺牲大量的内存来实现的，而SparseArray和ArrayMap性能略逊于HashMap，但更节省内存，用时间换取空间。ArrayMap和SparseArray采用的都是两个数组，HashMap采用的是数据+链表+红黑树。数据长度小于千时，建议取代HashMap。

SparseArray（<Integer,Value>），SparseBooleanArray（<Integer,Bool>），SparseIntArray，SparseLongArray（<Integer,Long>），LongSparseArray（<Long,Value>）
ArrayMap、ArraySet
SparseArray使用两个数组，一个保存key，一个保存value。
ArrayMap两个数组, mHashes是一个记录所有key的hashcode值组成的数组，是从小到大的排序方式；
mArray是一个记录着key-value键值对所组成的数组，是mHashes大小的2倍；
二分查找的时间复杂度O(log n)，大数据量的情况下，效率没有HashMap高

SparseArray原理

SparseArray源代码很简单，只有几百行。

private static final Object DELETED = new Object();//要删除的value先设为这个，特定情况下再回收
private boolean mGarbage = false;//标记是否有需要回收的
private int[] mKeys;
private Object[] mValues;
private int mSize;

public void put(int key, E value) {
        // 二分查找,key在mKeys列表中对应的index
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        // 如果找到，则直接赋值
        if (i >= 0) {
            mValues[i] = value;
        } 
        // 找不到
        else {
            // binarySearch方法中，找不到时，i取了其非，这里再次取非，则非非则正
            i = ~i;
            // 如果该位置的数据正好被删除,则赋值
            if (i < mSize && mValues[i] == DELETED) {
                mKeys[i] = key;
                mValues[i] = value;
                return;
            }
            // 如果有数据被删除了，则gc
            if (mGarbage && mSize >= mKeys.length) {
                gc();
                // Search again because indices may have changed.
                i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
            }
            // 插入数据，增长mKeys与mValues列表
            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
            mSize++;
        }
}

// 通过key查找对应的value
public E get(int key) {
        return get(key, null);
}
// 通过key查找对应的value
public E get(int key, E valueIfKeyNotFound) {
        // mKeys数组中采用二分查找，找到key对应的index
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        // 没有找到，则返回空
        if (i < 0 || mValues[i] == DELETED) {
            return valueIfKeyNotFound;
        } else {
        // 找到则返回对应的value
            return (E) mValues[i];
        }
}


// array为有序数组
// size数组中内容长度
// value要查找的值
static int binarySearch(int[] array, int size, int value) {
        int lo = 0;
        int hi = size - 1;
        // 循环查找
        while (lo <= hi) {
            // 取中间位置元素
            final int mid = (lo + hi) >>> 1;
            final int midVal = array[mid];
            // 如果中间元素小于要查找元素，则midIndex赋值给 lo 
            if (midVal < value) {
                lo = mid + 1;
            }
            // 如果中间元素大于要查找元素，则midIndex赋值给 hi  
            else if (midVal > value) {
                hi = mid - 1;
            }
            // 找到则返回 
            else {
                return mid;  // value found
            }
        }
        // 找不到,则lo 取非
        return ~lo;  // value not present
}