SparseArray原理分析

SparseArray 和其他的Android容器类一样，都是为了更加有效地利用内存，说直白点，就是为了节省内存。 SparseArray 和 ArrayMap 一样，都是为了更高效的保存int值到非原始类型的映射，用了同样的数据结构，但是为了提高效率， SparseArray 也做了自己的优化。接下来就分析一下 SparseArray 的存储，添加和删除元素。

继承结构

上图表明，```SparseArray```并没有像```ArrayMap```一样实现```Map```接口，仅仅实现了```Cloneable```接口。 ## **存储结构**

存储结构和```ArraySet```以及```ArrayMap```一脉相承，都使用int数组存储key值，使用Object数组存储对象。不同点在于```mKeys```数组中存储的是添加元素的key值本身，没有进行hash值得计算。

put

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

    if (i >= 0) {
        mValues[i] = value;
    } else {
        i = ~i;

        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }

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

            // Search again because indices may have changed.
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }

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

put 方法首先使用二分查找在 mKeys 中查找 key ，如果找到，则直接更新对应下标的 value 。如果未找到， binarySearch 方法返回待插入的下标的取反，故 i = ~i 。如果待插入的位置的元素已经被标记为 DELETED ，则直接更新并返回。如果需要执行 gc 函数，且需要扩大数组的容量（ mSize >= mKeys.lengt ），则先执行 gc 函数。由于执行 gc 函数之后元素会发生移动，故重新计算待插入位置，最后执行元素的插入。插入函数分为插入 key 和插入 value 。 GrowingArrayUtils.insert 的源码如下：

public static int[] insert(int[] array, int currentSize, int index, int element) {
    assert currentSize <= array.length;

    if (currentSize + 1 <= array.length) {
        System.arraycopy(array, index, array, index + 1, currentSize - index);
        array[index] = element;
        return array;
    }

    int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize));
    System.arraycopy(array, 0, newArray, 0, index);
    newArray[index] = element;
    System.arraycopy(array, index, newArray, index + 1, array.length - index);
    return newArray;
}
复制代码

函数的逻辑很简单，首先断言了 currentSize <= array.length ；如果 array 在不需要扩大容量的情况下可以添加一个元素，则先将待插入位置 index 开始的元素整体后移一位，然后插入元素，否则先扩容，然后将元素拷贝到新的数组中。

删除

为什么删除的时候我没有使用一个具体的函数呢，是因为 SparseArray 的删除有两种：根据key删除对象，删除指定位置的对象。

根据key删除对象

public void delete(int key) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    if (i >= 0) {
        if (mValues[i] != DELETED) {
            mValues[i] = DELETED;
            mGarbage = true;
        }
    }
}
复制代码

ContainerHelpers.binarySearch 函数在 ArraySet 和 ArrayMap 的元素查找中都出现过，作用是使用二分查找，在 mKeys 中找到 key 的位置，如果 key 存在，则返回 key 在 mKeys 中的下标，否则返回试图将 key 插入到 mKeys 中的位置的取反。找到待删除元素的下标后， SparseArray 并没有像 ArraySet 和 ArrayMap 一样去删除元素，只是将待删除元素标记为 DELETED ，然后将 mGarbage 设置为 true 。 DELETED 实际上就是一个对象，具体申明为： Object DELETED = new Object() ， SparseArray 有 gc 的过程，后面会分析这个 gc 的过程。

删除执行位置的对象

public void removeAt(int index) {
    if (mValues[index] != DELETED) {
        mValues[index] = DELETED;
        mGarbage = true;
    }
}
复制代码

删除指定位置元素的逻辑比较简单，判断待删除位置的元素是否已经被标记为 DELETED ，如果没有被标记，则标记指定位置的元素，并将 mGarbage 设置为 true 。

元素在被删除之后，都会将标志 mGarbage 设置为 true ，这是执行 gc 的必要条件。

gc

说到gc，给我的第一感觉应该是什么高深的c/c++源码，其实不是，贴上 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) {
            if (i != o) {
                keys[o] = keys[i];
                values[o] = val;
                values[i] = null;
            }
            o++;
        }
    }

    mGarbage = false;
    mSize = o;
}
复制代码

好吧，开始被自己给吓着了， gc 函数没有那么复杂。 gc 函数实际上就是将 mValues 数组中还未标记为 DELETED 的元素以及对应下标的 mKeys 数组中的元素移动到数组的前面，保证数组在0到 mSize 之间的元素都是未被标记为 DELETED ，经过 gc 之后，数据的位置可能会发生移动。

在元素被删除后，标志 mGarbage 设置为 true ，表示可以执行 gc 函数了。那么 gc 函数会在什么位置执行呢？ 分析 SparseArray 源码可以发现，如果 mGarbage 设置为 true ，在以下函数调用中 gc 函数会执行：

put , append , size , keyAt , valueAt , setValueAt , indexOfKey , indexOfValue , indexOfValueByValue

将以上函数总结一下可以归纳为三类：

• 向SparseArray添加元素
• 修改SparseArray的mValues数组
• 获取SparseArray的属性

通过执行 gc 将未被标记为 DELETED 的元素前移，在进行元素查找时可以减少需要查找的元素的数量，减少查找的时间，在添加元素的时候也可以更加快速的找到待插入点。

总结

SparseArray 主要是为了优化 int 值到 Object 映射的存储，提高内存的使用效率。相较于 HashMap ，在存储上的优化如下：

• 使用int和Object类型的数组分别存储key和value，相较于 HashMap 使用Node， SparseArray 在存储单个key-value时更节省内存
• SparseArray 使用int数组存储int类型的key，避免了int到Integer的自动装箱机制

虽然在存储int到Object映射时的内存使用效率更高，由于使用数组存储数组，在添加或者删除元素时需要进行二分查找，元素较多（超过1000）时效率较低，谷歌给出的建议是数据量不要超过1000，这种情况下，相较于 HashMap ,效率降低不会超过50%。