SparseArray 稀疏数组解析

前言

安卓提供了一个名为SparseArray的数据结构，用来替代小型的以int为key的HashMap，SparseArray牺牲了一些运行性能，用以换取内存节省。本文将针对SparseArray源码进行相关剖析。

底层实现

SparseArray的底层实现为数组，在SparseArray中定义了下面两个数据结构，分别用来记录Key和Value，可以发现由于这个数据结构要求键必须是int，因此稀疏数组内部实现没有使用包装类，从而避免了拆装箱的成本。

    private int[] mKeys;
    private Object[] mValues;

查询操作

SparseArray的查询操作是最基础的操作，代码如下所示。从代码中可以看出，SparseArray的内部数组大小远小于Integer范围，因此采用了二分查找的映射方式。

如果二分查找结果<0，或者目标点被标记为DELETED，则代表KEY无效。

public E get(int key, E valueIfKeyNotFound) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i < 0 || mValues[i] == DELETED) {
        return valueIfKeyNotFound;
    } else {
        return (E) mValues[i];
    }
}

SparseArray的具体映射方式如下所示，可以发现数组索引是连续的，但是KEY不是连续的，如果要查询5，通过二分查找算法，算出下标为1，因此直接访问下标为1的Value即可。

索引	KEY
0	1
1	5
2	10
3	null

增加/修改操作

增加操作第一步是通过二分查找找出元素应该存放的位置，如果当前KEY已存在，则直接覆盖，因此修改操作的时间复杂度是O(log(n))。

如果当前KEY不存在，则证明要新插入一个KEY。插入新的KEY分为以下四种情况：

1. 如果KEY对应的位置被标记删除，则可以直接覆盖。（对应第一个if）
2. 如果KEY对应的位置已经被某个元素占据，需要移动这个元素以后的所有元素，把位置空出来，然后放置KEY。
3. 如果KEY对应的位置已经被某个元素占据，并且此时没办法向后移动元素，因为所有的位置都已经被占据，则需要执行GC操作，GC操作删除一些被DELETE标记的元素，从而使得整个数组尾部有空闲位置，可以向后移动元素。（对应第二个if）
4. 如果KEY对应的位置已经被某个元素占据，并且通过GC操作依然没办法向后移动元素。此时代表数组容量确实不足，需要数组扩容。GrowingArrayUtils.insert函数当插入的下标大于数组长度时会自动扩容。

对于上述四种情况，除了第一种情况的时间复杂度为O(1)之外，其他的时间复杂度为O(n)。

    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++;
        }
    }

删除操作

SparseArray采用了标记删除算法，通过GC操作进行真正回收，从而可以减少数组移动次数。由于是标记删除，因此删除操作的时间复杂度为O(1)。

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

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

GC操作

GC操作算法中维护了一个整数o，代表剩余的元素数量，对于未标记为DELETE的元素，将下标o对应位置的Key和Object进行赋值，然后o++即可。

private void gc() {
    // Log.e("SparseArray", "gc start with " + mSize);

    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;

    // Log.e("SparseArray", "gc end with " + mSize);
}

时间复杂度

操作名称	时间复杂度
查询	O(log(n))
增加	O(n)
删除	O(1)
修改	O(log(n))

总结

通过上述分析，可以发现SparseArray是一个适用于Key为Int，且数据量较小情况下，为了优化内存占用，从而替代HashMap的工具。

根据官方文档的描述，在数据量较大的情况下，SparseArray比HashMap性能要差，在数百条数据的情况下，两个数据结构的差异并不是很明显，性能差异小于50%。

SparseArray通过数组实现，避免了K,V结构体，从而减少了内存占用。另一方面，避免装箱和拆箱操作对于内存和速度都有轻微的优化效果。标记删除使得数据结构的删除复杂度为O(1)。

但是，由于底层基于数组拷贝实现插入操作，因此对于数据量较大的情况，SparseArray性能较差。另外，对于高并发情况，SparseArray不是线程安全的，需要特别注意。