SparseArray原理：
SparseArray采用兩個(gè)數(shù)組,用來(lái)存放key以及value值的，核心思想是通過(guò)二分查找來(lái)找到key對(duì)應(yīng)的位置，然后取出值，或者插入值！

SparseArray源碼分析：

private static final Object DELETED = new Object();//標(biāo)記某個(gè)位置的value是否刪除
private boolean mGarbage = false;//標(biāo)記是否有刪除的元素

private int[] mKeys;//用來(lái)保存key的數(shù)組 并且mKeys里邊的元素都是從小到大有序排列的 保證二分查找沒(méi)有問(wèn)題
private Object[] mValues;//用來(lái)保存value的數(shù)組
private int mSize;//用來(lái)記錄元素的size


/**
 * Adds a mapping from the specified key to the specified value,
 * replacing the previous mapping from the specified key if there
 * was one.
 */
public void put(int key, E value) {
    //使用二分法找到元素插入的位置
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) {
        //如果找到，說(shuō)明這個(gè)key是存在的，替換就行了。
        mValues[i] = value;
    } else {
        //如果沒(méi)找到就取反，binarySearch方法沒(méi)找到返回的是大于key所在下標(biāo)的取反，在這里再取反
        //返回的正好是大于key所在下標(biāo)的值
        i = ~i;
        //首先說(shuō)明一點(diǎn)，是有的key值存放的時(shí)候都是排序好的，如果當(dāng)前存放的key大于數(shù)組中最大的key
        //那么這時(shí)的i肯定是大于mSize的，在這里i小于mSize說(shuō)明這里的key是小于mKeys[]中的最大值的，
        //如果mValue[i]被刪除了，就把當(dāng)前的key和value放入其中，在這里舉個(gè)例子，比如下面的數(shù)組
        //{1,3,7,9,13,16,22}如果key為7通過(guò)二分法查找得到的i為2，如果key為8則得到的i為-4，通過(guò)取反
        //為3，在下標(biāo)為3的位置如果被刪除了就用當(dāng)前的值替換掉
        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }
        //如果當(dāng)前下標(biāo)為i的沒(méi)有被刪除，就會(huì)執(zhí)行下面的代碼。是mGarbage如果對(duì)數(shù)據(jù)進(jìn)行了操作，就為true，
        //并且當(dāng)前的數(shù)據(jù)已經(jīng)滿(mǎn)了就調(diào)用gc()，然后再重新查找，因?yàn)間c之后數(shù)據(jù)的位置可能會(huì)有變化，所以要
        //必須重新查找
        if (mGarbage && mSize >= mKeys.length) {
            gc();

            // Search again because indices may have changed.
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }
        //擴(kuò)容數(shù)組順序插入，保證數(shù)組里面的值是有序的
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}



// This is Arrays.binarySearch(), but doesn't do any argument validation.
static int binarySearch(int[] array, int size, int value) {
    //對(duì)mKeys中的值進(jìn)行二分查找確定元素在mKeys的下標(biāo)位置（前提是數(shù)組必須是排序好的并且是升序排列，
    // 原理就是通過(guò)循環(huán)用當(dāng)前的value和數(shù)組中間的值進(jìn)行比較，如果小于就在前半部分查找，
    // 如果大于就在后半部分查找。最后如果找到就返回所在的下標(biāo)，如果沒(méi)有就返回一個(gè)負(fù)數(shù)）
    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 如果找到就返回所在的下標(biāo)
        }
    }
    return ~lo;  // value not present 如果沒(méi)有就返回一個(gè)負(fù)數(shù)
}

SparseArray的核心就是保證mKeys插入的數(shù)據(jù)順序排列，最后通過(guò)二分查找確定插入的下標(biāo),查詢(xún)刪除也是如此