SparseArray源码分析与性能优化

SparseArray是Android提供的数据结构，在某些场景下可以替代HashMap实现更好的性能。SparseArray在Android Java Framework源码中有大量使用。

SparseArray系列主要有：

• SparseBooleanArray
• SparseIntArray
• SparseLongArray
• SparseArray
• LongSparseArray

SparseBooleanArray，SparseIntArray，SparseLongArray

这三者的代码几乎相同，都是int型的key，区别在于value分别是boolean、int、long型。

关键源码

以SparseIntArray为例分析，关键代码如下。

public class SparseIntArray {
    private int[] mKeys;
    private int[] mValues;
    private int mSize;

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

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

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

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

        if (i < 0) {
            return valueIfKeyNotFound;
        } else {
            return mValues[i];
        }
    }

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

        if (i >= 0) {
            removeAt(i);
        }
    }

    public void removeAt(int index) {
        System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1));
        System.arraycopy(mValues, index + 1, mValues, index, mSize - (index + 1));
        mSize--;
    }

    public int size() {
        return mSize;
    }
}

class ContainerHelpers {
    static int binarySearch(int[] array, int size, int value) {
        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
            }
        }
        return ~lo;  // value not present
    }
}

final class GrowingArrayUtils {
    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 = new int[growSize(currentSize)];
        System.arraycopy(array, 0, newArray, 0, index);
        newArray[index] = element;
        System.arraycopy(array, index, newArray, index + 1, array.length - index);
        return newArray;
    }

    public static int growSize(int currentSize) {
        return currentSize <= 4 ? 8 : currentSize * 2;
    }
}

分析

SparseIntArray中有两个数组mKeys和mValues，分别保存对应的key和value，mSize用于保存数量。

二分法

Key在数组中按顺序插入，put、get、delete，都调用ContainerHelpers.binarySearch，使用二分法查找Key所在的Index。

• 如果找到了Key，则返回index，index的值大于等于0。
• 如果没找到，则返回lo按位取反后的结果，返回值是小于0的。对于put方法，此时的lo刚好是Key应该插入的位置。

get方法

• 找到了Key则直接返回对应Value，没找到则返回valueIfKeyNotFound。

put方法

• 找到了Key则直接覆盖对应的value，没找到则将binarySearch返回的值取反得到lo的原始值，再调用GrowingArrayUtils.insert，将后面的数据往后移动一位，给新数据腾出位置，并在lo的位置插入新的数据。如果容量不够，则会重新分配内存扩大容量。

delete方法

• 找到了Key，则直接调用System.arraycopy将后面的数据往前移动一位。

SparseArray，LongSparseArray与性能优化

前面三种API保存的都是boolean、int、long基本类型，而SparseArray和LongSparseArray都支持泛型，返回任意类型的数据，并且在SparseIntArray的基础上做了性能优化。

关键源码

SparseArray的Key是int型，而LongSparseArray的Key是long型。这里以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;

    @SuppressWarnings("unchecked")
    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];
        }
    }

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

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

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

    public int size() {
        if (mGarbage) {
            gc();
        }

        return mSize;
    }

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

分析

还是mKey和mValues数组保存Key和Value，还是实用二分法查找Key的位置。但是多了一个优化逻辑。

在SparseArray中：

• Value数组中保存的可能是有效数据，也可能是固定的DELETED对象，下面简称为无效数据。

• mSize并不是有效数据的数量，而是有效数据+无效数据的总数量。

• mGarbage标志位，表示Value数组中是否包含了无效数据（准确来说是Value数组中0 ~ mSize-1的区间）。

delete方法

• 在SparseIntArray中，删除元素操作会立即删除元素，将后面的数据往前挪，并改变mSize。
• 在SparseArray中，删除数据并不会立即删除，而是将数据标记为已删除。具体的做法是将Value设置为固定的DELETED对象，同时还会设置标志位mGarbage（这个标记删除的思路，有点像文件系统中删除文件的操作）。

get方法

• 如果二分法找到了Key，同时对应的Value为有效数据，则返回Value。

put方法

• 如果二分法找到了Key，无论Value是否为有效数据，都直接覆盖掉。
• 如果没找到Key，则获取插入位置。如果碰巧这个位置保存的是无效数据，则直接覆盖Key和Value为新数据即可。
• 如果已经获取插入位置，该位置已经被有效数据占据，Value数组中包含了无效数据（mGarbage==true），且已经存不下新数据了（mSize >= mKeys.length），则调用gc方法，将无效数据从数组中清理掉，然后重新搜索应该插入的位置。
• 最后，和SparseIntArray的逻辑一样，移动后面的数据，给新数据腾出位置并插入。

size方法

• SparseArray中的mSize保存的是有效数据+无效数据总数量，而不是有效数据的数量，因此在调用size方法时，也会触发gc，清理无效数据，并得到真实的Size。

gc方法

gc方法的实现比较简单，使用双指针的思路：

• 指针i在数组中遍历一遍，指针o每次遇到有效数据就自增，并将Key和Value从位置i复制到位置o。
• 为了防止内存泄露，还有一句values[i] = null，将原始位置的重复引用清除掉。
• 移动完成后，清除mGarbage标志，并修改mSize的值，因为此时已经没有无效数据了，mSize的值就等于有效数据的数量。

进一步优化点

在put方法触发gc的分支中，需要经过四步操作：

• 二分搜索
• gc
• 重新二分搜索
• 给新数据腾出空间并插入

实际上可以对这个分支进行优化，将后面的三步合并，只需要遍历一遍就可以同时实现gc和插入操作。

SparseArray性能分析

这里主要是对比HashMap和SparseArray / LongSparseArray，在处理int/long --> Object这种映射时的性能。

SparseArray的优势

• 避免了HashMap中对于一些基本类型的装箱拆箱操作，对CPU和内存性能都会有提高。
• 保存Value只需要数组，存储单个元素的成本更低。而HashMap比较复杂，需要用到Node，Node中包含了额外变量。
• 对于Key的数量可以提前明确的情况，SparseArray可以设置刚好合适的容量，节省内存。而HashMap很难保证Key的哈希值刚好均匀分布，因此通常需要让容量比Key的数量更多，才能保持较好的时间性能。
• SparseArray数据遍历速度比HashMap快，因为是直接数组操作，而HashMap是数组+链表，逻辑比较复杂。
• HashMap在容量不足、Key发生哈希冲突的情况下，需要遍历链表逐个对比Key，就没有SparseArray的二分法速度快了。

SparseArray的缺点

• 如果Key较多并且不能提前确定或变动频繁，SparseArray的数组就会很庞大，而插入、删除时又很容易触发移动、扩容操作，性能就会非常差。
• HashMap在Key发生哈希冲突很少的情况下，计算hashCode比SparseArray的二分法性能更好。

使用SparseArray的建议

在SparseArray的JavaDoc中已经说明了，SparseArray并不是设计用来保存大量数据的，更适合数据较少的情况，能节省内存。

SparseArray首次插入某个Key时，如果按照Key从小到大插入，性能会很好，每次都会在数组尾部插入新数据。但是反过来性能就会很差，因为需要频繁移动已有数据。因此如果Key的取值很不稳定，忽大忽小，使用SparseArray效果可能就比较差了。

如果Key是提前明确的，建议使用SparseArray。初始化时可以指定SparseArray的容量，还可以提前按照Key从小到大的顺序，调用SparseArray.append方法预先存放到SparseArray中，之后使用时就不会触发移动、扩容操作了。

举例：

• RecyclerView中按照ViewType缓存ViewHolder，使用了SparseArray。一般来说ViewType不会很多。

• 用后台返回的id作为Key，保存较多Object。因为id的取值范围很大，其值的大小也不确定，因此SparseArray的性能不佳。

• 使用RecyclerView的position为Key，给每个Item缓存数据（例如从本地或者网络加载数据）。这种场景适合SparseArray，一般来说，首次插入某个Key时，刚好是接近从小到大的顺序获取到数据的。