一、前言

1. 源码位置在这里搜素。
2. 本文只阐述SparseArry的数据结构，并简单分析代码实现

二、源码分析

1. 看线SparseArray的几个成员变量

    private static final Object DELETED = new Object();
    private boolean mGarbage = false;

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

几个成员变量非常简单

• DELETED 标实该位置的val是否被删除
• mGarbage 是否需要垃圾回收
• mKeys key的数组
• mValues val的数组
• mSize 存储的k-v对个数

2. 分析下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++;
        }
    }

这个函数通过binarySearch，使得mKeys是个递增的数组。我们用图模拟下put的过程。

1.png

上面图没涉及到gc和扩容过程，实际上扩容和GC过程无非就是一些元素的位移操作，这里不在画出来了。

3. remove操作
   remove操作和我们常规理解的remove稍微有些不同

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

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

我们看到，remove只是标记了某个元素被删除了，但是并没有真的删除这个元素，这个元素要到下次gc的时候删除，也有可能不被删除，而是直接被覆盖。

4. SparseArray的优点
   通过源代码可知，SparseArray只是减少了内存占用，因为不用像HashMap那样new Node节点对象出来。其性能是不如HashMap的。