SparseArray家族

SparseArray基于键值对存储数据，key为int，value为object，简单使用如下：

        //声明
        SparseArray<String> sparseArray= new SparseArray<>();
        //增加元素，append方式
        sparseArray.append(0, "myValue");
        //增加元素，put方式
        sparseArray.put(1, "myValue");
        //删除元素，二者等同
        sparseArray.remove(1);
        sparseArray.delete(1);
        //修改元素，put或者append相同的key值即可
        sparseArray.put(1,"newValue");
        sparseArray.append(1,"newValue");
        //查找，遍历方式1
        for(int i=0;i<sparseArray.size();i++){
            Log.d(TAG,sparseArray.valueAt(i));
        }
        //查找，遍历方式2
        for(int i=0;i<sparseArray.size();i++){
            int key = sparseArray.keyAt(i);
            Log.d(TAG,sparseArray.get(key));
        }

LongSparseArray 和SparseArray 相比，唯一的不同就是key值为long，所以LongSparseArray可以存储的数据元素就比SparseArray多，int的范围是-2^31 到 2^{31-1，而long是-2}63 到 2^63-1。

SparseBooleanArray，SparseIntArray，SparseLongArray，这三个数据结构的key值的类型也是int，value值的类型也固定，SparseBooleanArray的value固定为boolean类型，SparseIntArray的value固定为int类型，SparseLongArray的value固定为long类型。

总结一下这四种数据结构的key，value类型：

SparseArray          <int, Object>
LongSparseArray      <long, Object>
SparseBooleanArray   <int, boolean>
SparseIntArray       <int, int>
SparseLongArray      <int, long>

上述四种数据结构的key类型都是int，而不是Integer，相较于使用HashMap的话，省去了装箱拆箱过程，查询、存储等操作效率更高，而且int的存储开销也远小于Integer。

SparseArray实现原理

SparseArray内部的重要属性：

public class SparseArray<E> implements Cloneable {
    private static final Object DELETED = new Object();
    private boolean mGarbage = false;
    private int[] mKeys;
    private Object[] mValues;
    private int mSize;
}

DELETED

static final 的一个静态Object实例，当一个键值对被remove后，会在对应key的value下放置该对象，标记该元素已经被删除，只是标记删除，没有真正的删除。

mGarbage

当值为true，标志数据结构中有元素被删除，可以触发gc对无效数据进行回收，真正删除。

mKeys

用于存放Key的数组，通过int[] 进行存储，与HashMap相比减少了装箱拆箱的操作，同时一个int只占4字节；一个重要特点，mKeys的元素是升序排列的，也是基于此，我们才能使用二分查找。

mValues

用于存放与Key对应的Value，通过数组的position 进行映射；如果存放的是int型等，可以用SparseIntArray ，存放的Values也是int数组，性能更高。

mSize

mSize的大小等于数组中mValues的值等于非DELETED的元素个数。

remove方法源码：

    public void delete(int key) {
        //查找对应key在数组中的下标，如果存在，返回下标，不存在，返回下标的取反；
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        //key存在于mKeys数组中，将元素删除，用DELETED替换原value，起标记作用；
        if (i >= 0) {
            if (mValues[i] != DELETED) {
                mValues[i] = DELETED;
                mGarbage = true;
            }
        }
    }
     
    /**
     * @hide
     * Removes the mapping from the specified key, if there was any, returning the old value.
     */
    public E removeReturnOld(int key) {
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
     
        if (i >= 0) {
            if (mValues[i] != DELETED) {
                final E old = (E) mValues[i];
                mValues[i] = DELETED;
                mGarbage = true;
                return old;
            }
        }
        return null;
    }
     
    /**
     * Alias for {@link #delete(int)}.
     */
    public void remove(int key) {
        delete(key);
    }

二分查找：

class ContainerHelpers {

    // This is Arrays.binarySearch(), but doesn't do any argument validation.
    //第一个参数array为keys的数组，第二个为数组中元素个数（与keys的length不一定相等），第三个value为目标的key
    static int binarySearch(int[] array, int size, int value) {
        //lo为二分查找的左边界
        int lo = 0;
        //hi为二分查找的右边界
        int hi = size - 1;
        //还没找到，继续查找
        while (lo <= hi) {
            //左边界+右边界处以2，获取到mid 的index
            final int mid = (lo + hi) >>> 1;
            //获取中间元素
            final int midVal = array[mid];
            // 目标key在右部分  。。。。感觉这部分太简单了
            if (midVal < value) {
                lo = mid + 1;
            } else if (midVal > value) {
                hi = mid - 1;
            } else {
                //相等，找到了，返回key对应在array的下标；
                return mid;  //