SparseArray 源码解析

是什么东西？

sparse 是稀疏的意思，顾名思义，是一个稀疏数组，但实际上，他是一个key 只能为 int 的key-value 的数据结构，类似于HashMap
Android Developer 中对它的解释

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.
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, the performance difference is not significant, less than 50%.
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.
It is possible to iterate over the items in this container using keyAt(int) and valueAt(int). Iterating over the keys using keyAt(int) with ascending values of the index will return the keys in ascending order, or the values corresponding to the keys in ascending order in the case of valueAt(int).

为什么要使用它？

一句话：内存效率更高。他避免了Integer 的自动拆装箱，会自动压缩数组或者扩容，没有使用 entry 的数据结构

性能呢？

通常来说，要比 HashMap 慢，但数据量小于100时，性能下降少于50%，为什么慢这么多？因为二分搜索，其次，插入删除，数组需要压缩或者扩容，导致比较慢。对此，有一个删除时的优化，删除时不立即压缩数组，而是需要在需要增长数组或检索映射大小或条目值的任何时候执行此垃圾收集

怎么设计的？

其实，首页说的基本原理很清楚，它将映射关系保留在数组数据结构中，使用二分搜索来查找键，

适合什么场景？

key 为 int 的HashMap场景

源码分析

属性

// 删除后将value[index] = DELETED；等待 gc
private static final Object DELETED = new Object();
// 标记是否需要 gc (不是jvm的gc，而是数组内部自定义的gc，压缩数组)
private boolean mGarbage = false;
// 存放 key 集合
private int[] mKeys;
// 存放value 集合
private Object[] mValues;
// 集合中存在的未被删除元素的个数
private int mSize;

方法

获取值get 使用二分搜索找到mValues 中的位置， 如果搜索不到则返回空

/**
 * 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) {
    // 使用二分搜索找到mValues 中的位置  
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i < 0 || mValues[i] == DELETED) {
        return valueIfKeyNotFound;
    } else {
        return (E) mValues[i];
    }
}

二分搜索的实现，使用位运算提高效率，无符号右移（注意>> 和 >>> 的区别）

// 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
        }
    }
    // 巧妙的返回找不到的位置，去反一般小于0,
    return ~lo;  // value not present
}

什么地方进行 gc？

get remove 操作不进行gc
put size() keyAt valueAt 会检查 mGarbage 的标志进行 gc

gc 传说中的gc函数

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

    int n = mSize;
    int o = 0;
    int[] keys = mKeys;
    Object[] values = mValues;
    // 遍历将值为DELETED的位置删除  
    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++;
        }
    }
    // 更改 size 的大小，但keys 的大小没有变    
    mGarbage = false;
    mSize = o;

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

put 函数，优先在 DELETE 位置插入，插入后在检查是否需要 GC

/**                                                                   
 * 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) {                                   
    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;                                                   
        }                                                             
        // 是否需要 gc                                                              
        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++;                                                      
    }                                                                 
}

GrowingArrayUtils.insert 插入以及扩容

/**
 * Primitive boolean version of {@link #insert(Object[], int, int, Object)}.
 */
public static boolean[] insert(boolean[] array, int currentSize, int index, boolean element) {
    assert currentSize <= array.length;
    
    // 普通情况
    if (currentSize + 1 <= array.length) {
        System.arraycopy(array, index, array, index + 1, currentSize - index);
        array[index] = element;
        return array;
    }
    // currentSize = array.length 的情况，进行扩容
    boolean[] newArray = ArrayUtils.newUnpaddedBooleanArray(growSize(currentSize));
    // 数组的复制都使用 System.arraycopy，效率高
    System.arraycopy(array, 0, newArray, 0, index);
    newArray[index] = element;
    System.arraycopy(array, index, newArray, index + 1, array.length - index);
    return newArray;
}

growSize增长函数，小于 4 时直接增到 8， 之后以2的位数增长，这与很多增长函数差不多，只不过在这没有用位运算有点遗憾

/**
 * Given the current size of an array, returns an ideal size to which the array should grow.
 * This is typically double the given size, but should not be relied upon to do so in the
 * future.
 */
public static int growSize(int currentSize) {
    // 增长函数
    return currentSize <= 4 ? 8 : currentSize * 2;
}

以上这几个都是很经典的函数以及实现，需要掌握！

总结

Android 源码中对 SparseArray 应用还是比较多的，可能是想解决由于早期 Android 内存小的问题，但在日益低廉的内存面前，是否还有必要使用，提高内存效率还是得打一个问号。

欢迎讨论～