SparseArray是谷歌推出的一个数据容器，推荐在Android平台上替代key为int类型的HashMap。官方文档中给出的理由是相比HashMap更节省内存：1、避免了自动装箱的过程；2、数据结构不依赖于外部对象映射。因为对于移动端来说，内存的资源更加珍贵。

源码解析

以android.util.SparseArray为例，SDK=28

成员变量

private static final Object DELETED = new Object();     //标记value是否被删除
private boolean mGarbage = false;   //标记当前是否进行了垃圾回收

private int[] mKeys;    //存储key的数组，升序排列
private Object[] mValues;   //存储value的数组
private int mSize;   //当前实际的元素个数
复制代码

初始化

SparseArray默认的无参构造方法的初始容量为10，但是经过内部处理后变为11。初始化后mKeys和mValues都是长度为11的未赋值数组

public SparseArray(int initialCapacity) {
    if (initialCapacity == 0) {
        mKeys = EmptyArray.INT;
        mValues = EmptyArray.OBJECT;
    } else {
        mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
        mKeys = new int[mValues.length];
    }
    mSize = 0;
}
复制代码

put

最重要的方法，key和value存储的过程

public void put(int key, E value) {
    //传进来的key会先进行一次二分查找，因此mkeys要保证是有序的
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    //如果找到了，说明原先对应该key的value已经存在，直接更新即可
    if (i >= 0) {
        mValues[i] = value;
    } else {
        //没有找到，对i进行一次取反操作，得到要插入的下标
        i = ~i;
        //如果要插入的下标正好值是DELETED，直接更新即可
        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }

        
        if (mGarbage && mSize >= mKeys.length) {
            //容量不足，并且需要垃圾回收，就先进行回收操作
            gc();
    
            //空间压缩后数组元素变化，需要重新计算插入的位置
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }
        //插入元素
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}
复制代码

二分查找和插入元素共同保证了mKeys的有序，确定了key对应在数组中的位置后，也就确定了value在数组中的位置。如果key已经存在或者命中了DELETED，那么直接更新，数组元素数量不变，开始时mKeys.length=11,mSize=0,当mSize增加到>=mKeys.length的时候，如果数组中存在被删除的元素，则会先进行一次gc，提高了空间利用率，避免了数组的扩容。

binarySearch

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];

        if (midVal < value) {
            lo = mid + 1;
        } else if (midVal > value) {
            hi = mid - 1;
        } else {
            return mid;  // value found
        }
    }
    return ~lo;  // value not present
}
复制代码

二分查找的过程，不同于Arrays#binarySearch，如果没有查找到key，返回的是下边界的取反值。取反后返回负数，put方法继续向下执行，再次取反后就得到了要插入的位置，整个效率还是比较高的。比如：

mKeys={3,4,6,7,8},要插入的key为5,
开始二分查找lo=0,hi=4,经过两轮查找后lo=2,hi=1,那么最后lo=2就是5在mKeys中要插入的下标位置
复制代码

delete

public void delete(int key) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) {
        if (mValues[i] != DELETED) {
            mValues[i] = DELETED;
            mGarbage = true;
        }
    }
}
复制代码

delete方法比较简单，如果key已经存在，并且对应的value值没有被标记过删除，就将value值标记为删除，并且将mGarbage置为true。标记的方法就是将value指向一个静态常量Object，remove(int key)也是用delete实现的。这样在put的时候如果该下标的值已被标记删除，直接更新，省去了删除元素和插入元素的过程，还是比较巧妙的。而在gc方法中SparseArray才真正进行了对mKeys和mValues的处理

gc

private void gc() {

    int n = mSize;  //压缩前的元素个数
    int o = 0;      //压缩后的元素个数
    int[] keys = mKeys;
    Object[] values = mValues;

    for (int i = 0; i < n; i++) {
        Object val = values[i];

        if (val != DELETED) {   //如果该位置的value没有被标记删除
            if (i != o) {   
                keys[o] = keys[i];      //将i处的元素向前移动到o处，使的所有非DELETED的元素都连续排列在数组前面
                values[o] = val;
                values[i] = null;   //释放空间
            }

            o++;    //只有没标记过删除o才会加一，当出现i>o的情况就说明前面已经有元素被标记了删除
        }
    }

    mGarbage = false;   //压缩（垃圾回收）结束
    mSize = o;      //更新压缩后的元素个数
}
复制代码

通过一个很精干的算法回收了value数组中为DELETED的节点并且更新了数组有效元素个数。再回过头看put中的操作,假设这时的mKeys={0,3,4,5,6,7,8,9,10,11,12},mValues={"a","b","c","d","e","f","g","h","i","j","k"}

spA.remove(4)； //spA代表该SparseArray对象
mValues={"a","b",*,"d","e","f","g","h","i","j","k"}    //*代表DELETED标记。

spA.put(15,"s")
i=~ContainerHelpers.binarySearch(mKeys, mSize, key)=12
这时候mSize=11并且mGarbage=true，命中条件，调用gc方法进行数组的压缩

//gc过后
mKeys={0,3,5,6,7,8,9,10,11,12,12}
mValues={"a","b","d","e","f","g","h","i","j","k",null}
mSize=10
i=~ContainerHelpers.binarySearch(mKeys, mSize, key)=11

//插入过后
mKeys={0,3,5,6,7,8,9,10,11,12,15}
mValues={"a","b","d","e","f","g","h","i","j","k","s"}
mSize=11
复制代码

由于gc后mKeys发生了变化，需要重新索引，如上i在gc前计算等于12，gc后最终的索引是11。这里需要注意，由于gc过程mKeys向前补位后并没有像mValues一样释放空间，比如上述remove(4)后紧接着remove(6)，再次gc过后会出现mKeys={0,3,5,7,8,9,10,11,12,11,12}这样的情况，但是这并不违反mKeys是有序的规则，因为i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);入参是mSize,每次二分查找的过程lo=0,hi=size-1,hi位是按有效元素个数计数的，像上面最后两位的11和12不是有效key值，所以二分查找仍然有效。

get

public E get(int key, E valueIfKeyNotFound) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    //逻辑很简单，通过二分查找确定key在mKeys数组中的位置，找到了直接返回对应的value，否则返回默认值
    if (i < 0 || mValues[i] == DELETED) {
        return valueIfKeyNotFound;
    } else {
        return (E) mValues[i];
    }
}
复制代码

indexOfValue、indexOfValueByValue

获取key和value的index，都是判断如果之前有元素被标记删除过，则先gc再查找。不同的是key是二分查找，而value因为是无序的，采用的是遍历数组的做法，没找到返回-1。这里面有个坑是indexOfValue内部是用==，比较的是地址，indexOfValueByValue才是用equals比较两个对象，该方法被标记为私有API。如果确实要通过value确定下标，可以用遍历SparseArray和valueAt的方法获取。

append

public void append(int key, E value) {
    if (mSize != 0 && key <= mKeys[mSize - 1]) {
        put(key, value);
        return;
    }

    if (mGarbage && mSize >= mKeys.length) {
        gc();
    }

    mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
    mValues = GrowingArrayUtils.append(mValues, mSize, value);
    mSize++;
}
复制代码

两种情况：1、数组为空 2、key大于当前mKeys中的所有元素，这个时候就省去了查找的过程，如果不需要扩容直接将value追加到尾部，需要的话也只要一次拷贝，这就是append针对存储的特殊情况作出的优化。

GrowingArrayUtils

不管是insert还是append，都会先计算是否需要扩容，不同的是insert可能需要两次拷贝，最终调用的都是System#arraycopy。

扩展的其他容器

SparseIntArray、SparseBooleanArray、SparseLongArray都是用来存储特定value的数据容器，没有泛型没有gc，数组类型都是基本数据类型，避免了对这几种value类型的装箱，进一步优化。LongSparseArray是确保key为long类型时使用的，能存储的key数据范围更大。

性能分析

内存比较

和HashMap比较，先看一下两者的内存占用情况的比较，工具是AndroidStudio自带的Profiler，测试代码是循环生成100000个HashMap/SparseArray对象，查看生成前和生成后Java Heap大小的差异

private HashMap<Integer, String> mMap = new HashMap<>();
private SparseArray<String> mSpa = new SparseArray<>();
    
public void test(){
    for (int i = 0; i < 100000; i++) {
        mMap.put(i, String.valueOf(i));
        //mSpa.put(i, String.valueOf(i));
    }
}
复制代码

下图是使用HashMap创建数据前内存使用情况（SparseArray和这个差不多）：

使用HashMap创建数据后内存使用情况：

使用SparseArray创建数据后内存使用情况：

上面算出来SparseArray相比HashMap能减少12%的内存，实际测试多次下来的结果差不多在10%-15%之间

速度比较

总结

1. 和HashMap相比，少了自动装箱的过程（int->Integer），因为HashMap的key存储的是包装类型
2. 和HashMap相比，更节约内存，结构更简单。因为HashMap采用数组+链表存储数据，<K,V>结构有一个额外的Entry用来存储hash、key、value和下一个Entry节点（不考虑树化），而SparseArray内部只维护了两个数组用来存储
3. SparseArray的核心是二分查找，时间复杂度是O(logN)，如果没有查找到，那么取反返回左边界，再次取反后，即为应该插入的数组下标；
4. 如名字一样，稀疏数组的概念，在这里被用来实现delete，并不是真正的删除，而是做一个标记，如果再次插入元素的时候刚好在该位置上则实现了重用，否则在空间不足的情况下再进行一次压缩，效率和空间都得到了优化。
5. SparseArray不是被设计做大数据量存储的，当有很多数据存储时其效率低于HashMap