[Android][Performance]SparseArray和HashMap

缘起： 在做Android开发时，如果在代码中使用了

HashMap<Integer, Object> map = new HashMap<Integer, Object>();

用Lint工具来检查时，Lint便会报出一个警告，要我们采用SparseArray来代替HashMap用来提高性能。这个警告会在HashMap的Key是Integer类型时出现。相比HashMap，采用SparseArray可以从两个方面来提高程序的性能。第一，HashMap的键采用的是Integer类型，而SparseArray的键采用的是int 类型，不需要Auto Boxing。第二，SparseArray中存储元素是采用两个数组，一个用来存Key，另一个用来存Value。而HashMap中采用的是了一个Entry来存储。在存储时，会先根据元素的hash值来得到其存放的位置下标。因此HashMap中分配的空间肯定比HashMap中实际元素所需要的空间多。从这一点来看，SparseArray比HashMap更少空间。

读了一下SparseArray的源代码，其实现也非常的简洁。在使用时，通常就直接new一个SparseArray。默认会分配10个元素的空间。如下：

    public SparseArray() {
        this(10);
    }
    public SparseArray(int initialCapacity) {
        if (initialCapacity == 0) {
            mKeys = ContainerHelpers.EMPTY_INTS;
            mValues = ContainerHelpers.EMPTY_OBJECTS;
        } else {
            initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity);
            mKeys = new int[initialCapacity];
            mValues = new Object[initialCapacity];
        }
        mSize = 0;
    }

采用put(int key, E value)方法向里面添加新的键值对。如果键值已经存在，那么该键值对应的value将会被新的value所替换。我们来分析一下SparseArray中的put(int key, E value)方法的代码：


    public void put(int key, E value) {
        //二分法查找当前key是否存在。
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        //如果当前key已经存在，那就替换当前key所对应的value.
        if (i >= 0) {
            mValues[i] = value;
        } else {
            i = ~i;
            //如果是新添加的元素，并且下标 i 所对应 value类型是DELETED(该处元素应该已删除)
            if (i < mSize && mValues[i] == DELETED) {
                mKeys[i] = key;
                mValues[i] = value;
                return;
            }
           //如果先前有delete操作，并且没有执行gc()，则调用gc()
            if (mGarbage && mSize >= mKeys.length) {
                gc();

                // Search again because indices may have changed.
                i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
            }
            // 对数组进行扩容
            if (mSize >= mKeys.length) {
                int n = ArrayUtils.idealIntArraySize(mSize + 1);

                int[] nkeys = new int[n];
                Object[] nvalues = new Object[n];

                // Log.e("SparseArray", "grow " + mKeys.length + " to " + n);
                System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
                System.arraycopy(mValues, 0, nvalues, 0, mValues.length);

                mKeys = nkeys;
                mValues = nvalues;
            }

            if (mSize - i != 0) {
                // Log.e("SparseArray", "move " + (mSize - i));
                System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
                System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
            }

            mKeys[i] = key;
            mValues[i] = value;
            mSize++;
        }
    }

SparseArray中值得注意一点的是它的gc()方法。对于已经标记为DELETE的元素，gc()在运行时，便会释放它所占据的空间

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

在SparseArray的很多方法中都会有调gc()方法的。如：

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

        return mSize;
    }

    public int keyAt(int index) {
        if (mGarbage) {
            gc();
        }

        return mKeys[index];
    }

在调用gc()之前会先判断mGarbage是否为true, 如果mGarbage为true,gc()方法将会被调用。mGarbage的值设置为true发生在delete(int key) 和removeAt(int index)方法中。如下：

    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 void removeAt(int index) {
        if (mValues[index] != DELETED) {
            mValues[index] = DELETED;
            mGarbage = true;
        }
    }

SparseArray针对的是键为int, 值是object这种类型的数据结构。此外，还有SparseBooleanArray, LongSparseArray分别针对键为boolean,long，值为object的数据结构。
由于SparseArray是的底层是采用数组实现的，所以数组的一些缺点(You Know)，它也无法避免。
关于HashMap的源码解析，我觉得可以参看csdn上的这篇文章

fred-ye / summary

[Android][Performance]SparseArray和HashMap #23