SparseArray源码分析

SparseArray使用

创建

//未指定容量大小时，默认为10
SparseArray sparseArray = new SparseArray<>();
//指定容量大小
SparseArray sparseArray = new SparseArray<>(16);
//指定value的泛型为String
SparseArray<String> sparseArray = new SparseArray<>();

SparseArray有两个构造方法，一个空构造方法，一个可以传入具体容量。SparseArray只需要指定value的泛型，key的类型在内部已经指定了为int，一会儿分析它的内部源码实现再来查辨。

插入

sparseArray.put(int key, Object value);

可以看到SparseArray的插入数据时，默认key类型的为int。

删除

sparseArray.remove(int key);
sparseArray.delete(int key);

remove方法和delete方法都能删除数据，remove方法内部也是调用delete方法进行删除。

获取

sparseArray.get(int key);
sparseArray.get(int key, E valueIfKeyNotFound);

两个get方法区别是，下面的get方法当key不存在时返回传入的默认值，上面的则返回null。

index

sparseArray.indexOfKey(int key);
sparseArray.indexOfValue(E value);

index方法返回传入key和value对应在SparseArray中的索引，若传入的值不存在，返回的值会小于0，由此根据返回值的正负判断是否命中。

SparseArray源码分析

下面简单分析下SparseArray的源码实现，首先看下类的注释

SparseArrays map integers to Objects. Unlike a normal array of Objects, there can be gaps in the indices. It is intended to be more memory efficient than using a HashMap to map Integers to Objects, both because it avoids auto-boxing keys and its data structure doesn't rely on an extra entry object for each mapping.

上面这段注释基本说明了SparseArray的作用，同样是存取int类型的键值，SparseArray相对于HashMap避免了key值的自动装箱，而且不使用额外的数据结构体来存储数据。

<p>Note that this container keeps its mappings in an array data structure, using a binary search to find keys. The implementation is not intended to be appropriate for data structures that may contain large numbers of items. It is generally slower than a traditional HashMap, since lookups require a binary search and adds and removes require inserting and deleting entries in the array. For containers holding up to hundreds of items, he performance difference is not significant, less than 50%.</p>

上面这段注释则说明了SparseArray的实现原理，SparseArray采用二分查找来查找key索引值，在数据量大的时候查找的性能会比较差，在插入和删除数据时SparseArray需要对数组进行移动、拷贝操作，所以当数据量较大时性能会下降。

<p>To help with performance, the container includes an optimization when removing keys: instead of compacting its array immediately, it leaves the removed entry marked as deleted. The entry can then be re-used for the same key, or compacted later in a single garbage collection step of all removed entries. This garbage collection will need to be performed at any time the array needs to be grown or the the map size or entry values are retrieved.</p>

第三段的注释解释了，SparseArray为提高性能在删除数据时进行了优化，不会立即压缩数组而是为需要删除的条目打上标记，在往后需要数组扩容或者数据检索时进行数据清除和数组压缩，这样可以减少数组操作的频率，同时可以复用key值。

构造方法

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;

    /**
     * Creates a new SparseArray containing no mappings.
     */
    public SparseArray() {
        this(10);
    }

    /**
     * Creates a new SparseArray containing no mappings that will not
     * require any additional memory allocation to store the specified
     * number of mappings.  If you supply an initial capacity of 0, the
     * sparse array will be initialized with a light-weight representation
     * not requiring any additional array allocations.
     */
    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;
    }

    //省略。。。。
}

可以看到SparseArray并没有继承任何集合类或者数据结构，只是实现了Cloneable接口，SparseArray提供了两个构造方法，无参的构造方法最终会创建一个大小为10的数组分别用于存放key和value。数组结构如下图所示

内部存储结构

put方法

/**
 * Adds a mapping from the specified key to the specified value,
 * replacing the previous mapping from the specified key if there
 * was one.
 */
public void put(int key, E value) {
    //通过二分查找数组中是否已经存在该key，返回的i大于等于0表示存在，小于0则表示不存在
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) {
        //数组中存在键值，直接替换成新的value值
        mValues[i] = value;
    } else {
        //重新取反获得正确的索引，因为在前面二分查找过程中，如果数组中不存在该值，会把最后index取反，以区分是否命中
        i = ~i;
        //如果要插入的 key 的索引对应的value值为DELETED直接覆盖
       //DELETED表示该索引上的值可以被回收
        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }
        
       //mGarbage为true表示数组中有数据可以被回收
       //连在一起的判断语句意思是，如果数组长度不够存放需要扩容且数组内有数据可以被回收，则调用gc()方法进行回收数据。
       //注意这里的gc()方法不是虚拟机的gc垃圾回收，而是SparseArray自身内部实现的数据回收方法
        if (mGarbage && mSize >= mKeys.length) {
            gc();

            // Search again because indices may have changed.
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }
        
        //最后这里执行插入数据的操作，前面的类注释提到，SparseArray对数据的删除和增加都涉及了数组的移动和拷贝
        //这里会判断插入的索引如果大于数组的长度则会新建新的数组，涉及将原数组拷贝至新数组的操作
        //如果小于数组的长度直接进行数组内数据的移动即可
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}

二分查找key索引值，需要注意最后一句代码，未找到时将索引值取反，从而可以根据返回值的正负来判断是否命中

class ContainerHelpers {

    // This is Arrays.binarySearch(), but doesn't do any argument validation.
    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
    }

    //省略...
}

最后插入数据到数组

public static <T> T[] insert(T[] array, int currentSize, int index, T element) {
    assert currentSize <= array.length;
    
    //小于数组长度，直接移动数组内数据即可
    if (currentSize + 1 <= array.length) {
        System.arraycopy(array, index, array, index + 1, currentSize - index);
        array[index] = element;
        return array;
    }
    
     //大于现有数组长度，需要新建数组，将原数组数据拷贝至新数组
    T[] newArray = (T[]) Array.newInstance(array.getClass().getComponentType(),
            growSize(currentSize));
    System.arraycopy(array, 0, newArray, 0, index);
    newArray[index] = element;
    System.arraycopy(array, index, newArray, index + 1, array.length - index);
    return newArray;
}

总结一下put()方法的工作流程：
1.通过二分查找判断是否存在该key，所以存放key的数组一定是有序的
2.如果数组中存在该key值，新的value值直接覆盖原value值
3.如果要插入的 key 索引值小于现有数组的大小且key对应的value值为DELETED，直接覆盖（DELETED表示该索引上的值可以被回收，在调用删除数据方法时标注）
4.前几步都没有插入成功的话，判断数组中是否有数据可以被回收且数组不够存放需要扩容，进行gc回收数据
5.最后执行插入数据的操作，如果插入的索引大于数组的长度则会新建新的数组，并将原数组数据拷贝至新的数组，如果小于数组的长度直接进行数组内数据的移动即可

delete方法

分析完SparseArray的插入数据方法后，再来看看它的删除数据的方法

/**
 * Removes the mapping from the specified key, if there was any.
 */
public void delete(int key) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

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

在前面的类注释中已经提到SparseArray删除数据时不会立即删除数据和压缩数组，而是为需要删除的数据打上标记，等到下次调用gc()方法时再进行数据清除。从delete方法中也可以看到，方法体内只是简单的把索引对应的value值设置为DELETED，同时把mGarbage设置为true。

gc方法

gc()是SparseArray清除数据和压缩数组的重要方法，跟虚拟机的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);
}

关于代码的的过程可看下图， o 在value值等于DELETED的时候不会递增，也就是说当i递增的时候，o还停留在值为DELETED的位置，因此i != o触发第二个判断条件，将i位置的元素移动到o处，往后遍历也同理。

gc过程

上文在分析put方法的时候已经知道put方法可能会触发gc()，除了put方法，前文提到index相关的方法也会试图去触发gc()，因为在数组压缩过后可以返回给调用者一个精确的索引值。

get方法

/**
 * Gets the Object mapped from the specified key, or <code>null</code>
 * if no such mapping has been made.
 */
public E get(int key) {
    return get(key, null);
}

/**
 * Gets the Object mapped from the specified key, or the specified Object
 * if no such mapping has been made.
 */
@SuppressWarnings("unchecked")
public E get(int key, E valueIfKeyNotFound) {
    //二分查找索引值
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    
    //索引值不存在或对应的value值为DELETED则返回传入的默认值
    if (i < 0 || mValues[i] == DELETED) {
        return valueIfKeyNotFound;
    } else {
        //命中，返回正确的value值
        return (E) mValues[i];
    }
}

get()方法中的逻辑比较简单，首先通过二分查找获取到key的索引，如果索引值不存在或对应的value值为DELETED则返回传入的默认value值，索引值存在的话则返回对应的value。

SparseArray 系列

除了上文分析的SparseArray，还有其它的一些类似的数据结构，它们都是用于来存取基本数据类型的键值对：
SparseIntArray — int:int
SparseBooleanArray— int:boolean
SparseLongArray— int:long
这里就不一一列举了，感兴趣的同学可以单独去看，实现原理大同小异。

总结

分析完了SparseArray的实现原理，来对比一下它与HashMap之间优劣。

优势：
1.避免了基本数据类型的装箱操作
2.不需要额外的结构体，单个元素的存储成本更低
3.数据量小的情况下，随机访问的效率更高
劣势：
1.插入和删除操作需要操作数组，效率较低
2.数据量巨大时，复制数组成本巨大
3.数据量巨大时，二分查找效率也会明显下降

如果本文中有不正确的结论、说法，请大家提出和我讨论，共同进步，谢谢。

感谢以下文章提供的帮助：https://juejin.im/entry/57c3e8c48ac24700634bd3cf