SparseArray源码解析

在Android中，现在很多时候都会用SparseArray来代替HashMap存放数据，但是有些情况是HashMap效率更高，至于两者之间有什么区别，而又是什么导致了两者的差异，可以跟着文章继续看代码实现。

1. 初始化

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

构造方法可以传入一个int作为初始容量，代码也只是简单的根据传入容量去初始化mKeys和mValues两个数组

2. put和remove操作

先来看put相关的代码

public void put(int key, E value) {
//首先通过传入的key然后调用ContainerHelpers.binarySearch方法去找到对应key的下标
//binarySearch实际上是一个二分查找，在其他集合类里也有出现过比如ArrayMap
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

        if (i >= 0) {
        // 已经存在就直接更新值
            mValues[i] = value;
        } else {
            // binarySearch方法如果没有匹配到key会返回-1，
            // 在这里做运算之后把i变成0
            i = ~i;
            // mSize标记了操作次数，第一次put的时候mSize还会是0
            // 如果不是不是第一次操作并且mValues[i]是被标记为DELETED
            // 就直接更新值，这里的DELETED状态也是SparseArray一种优化方式
            if (i < mSize && mValues[i] == DELETED) {
                mKeys[i] = key;
                mValues[i] = value;
                return;
            }
            
            // 如果有移除过元素，会把mGarbage设成true
            // 这里是为了检查是否需要优化一下数组的个数，把一些无用的元素移除掉
            if (mGarbage && mSize >= mKeys.length) {
                gc();

                // Search again because indices may have changed.
                i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
            }
            // 把对应的key和value分别插入到数组中
            // 如果需要扩容，小于4的size会拓展成8,其余时候扩容成原本的两倍
            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
            mSize++;
        }
    }

上面提到了优化数组空间的时候，调用到了一个gc的方法，就是用来移出一些已经标记为DELETED的元素并且把元素排到合适的位置

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

        int n = mSize;
        int o = 0;
        int[] keys = mKeys;
        Object[] values = mValues;
        // 把标记为DELETED的元素设为null，并且把后面的元素往前面排
        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++;
            }
        }

        // 把标记设为false，并且更新mSize的值
        mGarbage = false;
        mSize = o;

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

要移除元素SparseArray提供了以下几个方法

public void remove(int key) {
        delete(key);
}

public void delete(int key) {
    // 二分查找找出下标
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    // 把对应的元素下标标记为DELETED,然后把mGarbage设为true，这样下次放元素的时候能触发gc
    if (i >= 0) {
        if (mValues[i] != DELETED) {
            mValues[i] = DELETED;
            mGarbage = true;
        }
    }
}


public void removeAt(int index) {
    // 判断一下下标合法性
    if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) {
        // The array might be slightly bigger than mSize, in which case, indexing won't fail.
        // Check if exception should be thrown outside of the critical path.
        throw new ArrayIndexOutOfBoundsException(index);
    }
    // 同样是把对应元素设为DELETED
    if (mValues[index] != DELETED) {
        mValues[index] = DELETED;
        mGarbage = true;
    }
}

// 移除多个元素
public void removeAtRange(int index, int size) {
    final int end = Math.min(mSize, index + size);
    for (int i = index; i < end; i++) {
        removeAt(i);
    }
}

关于移除元素的方法里，SparseArray做了一些延迟移除元素的处理，每次调用移除元素的方法时，不会立马把对应元素删除而是标记成DELETED,然后在后续重新put元素的时候再去把这些DELETED给清除掉然后减少数组占用，再去通过一次二分查找找出对应位置添加进去。这样可以避免在多次移除的时候每次都移动了数组内元素。

3. GrowingArrayUtils.insert

上面在put的时候还提到了一个insert元素的方法，这个方法作用是把元素放到数组中的特定下标上，并且空间不足的时候会自动扩容

public static <T> T[] insert(T[] array, int currentSize, int index, T element) {
    assert currentSize <= array.length;
    // 先判断当前数组长度是否足够
    if (currentSize + 1 <= array.length) {
        // 把原数组和下标等数据传进去copy一份
        System.arraycopy(array, index, array, index + 1, currentSize - index);
        // 更新对应下标的值，完成插入
        array[index] = element;
        return array;
    }

    T[] newArray = (T[])
    // 新建一个扩容的数组，growSize方法去计算扩容后的长度
    Array.newInstance(array.getClass().getComponentType(),
            growSize(currentSize));
    // 把index前的元素放到新的数组，然后再把要insert的元素放到index位置上
    System.arraycopy(array, 0, newArray, 0, index);
    newArray[index] = element;
    // 最后再把剩下的数据也就是index后的元素放到新数组后面
    System.arraycopy(array, index, newArray, index + 1, array.length - index);
    return newArray;
}

// 根据当前size计算出扩容后的size
public static int growSize(int currentSize) {
    return currentSize <= 4 ? 8 : currentSize * 2;
}

至于其他的像valueAt keyAt等等这种查找的方法，也会去判断是否需要gc，因为方法逻辑比较简单就不再列出。

总结

• 把key value分别放到两个数组中保存，存放int类型避免装箱操作加快效率
• 二分查找去找到对应元素应该插入的下标，自动扩容
• 移出元素的时候会先标记为DELETED,等到添加元素或者clear的时候再去清理这些元素腾出空间，可以提高效率避免多次remove的时候操作数组
• 和HashMap相比由于是用二分查找的方法去找到下标，所以时间会比HashMap 稍慢，但是内存空间占用上来讲要比HashMap更好
• 请注意，Key是按升序排列的，而不是按其添加的顺序排列。因为在查找下表的时候用的是二分查找去找到对应位置
• 根据网上测试，大于1000个元素的时候,SparseArray的速度就会变得比较慢，所以一般适用于数据量不大，key是整数类型的场合