SparseArray

见名知意

SparseArray "稀疏数组", 是数组，key是整数，但key不是连续的。如下图，key并不是4到10连续的，它只是零星地存储了几个自己想要的数据。跟HashMap理解一样。
SparseArray内部维持着2个数组keys,values。通过找到key在数组中的索引index,从而找到key对应的数据values[index]。

SparseArray内部数据结构

基本操作

1. 创建实例： 可以指定初始的容量(keys和values数组)大小，也可以不传，如果不传入的话，默认大小为10。

val sparseArray = SparseArray<String>(5)  

2. 增加数据 : put和append都可以。注意append并不像我们平常接触的那样是在末尾追加，它最终还是调用put，还是保持key从小到大的顺序。

sparseArray.apply {
    put(7, "seven")
    put(10, "ten")
    append(4, "four") //尽管是append的，数据还是在最前面
}

3. 数据迭代: keyAt(), get(key), 按照key的从小到大的顺序显示

Log.d(TAG,"==> iterator before remove.")
for (i in 0 until sparseArray.size()) {
    val key = sparseArray.keyAt(i)
    val value = sparseArray.get(key)
    Log.d(TAG,"key = $key,value = $value")
}
// key = 4,value = four 
// key = 7,value = seven
// key = 10,value = ten

4. 删除数据: remove(key)或者delete(key)。 remove(key)代码实现还是调用delete(key)

sparseArray.remove(7)
sparseArray.remove(8)
Log.d(TAG,"==> iterator after remove.")
for (i in 0 until sparseArray.size()) {
    val key = sparseArray.keyAt(i)
    val value = sparseArray[key]
    Log.d(TAG,"key = $key,value = $value")
}
// key = 4,value = four
// key = 10,value = ten

与HashMap区别

看这用法，跟HashMap没啥区别，难道HashMap不香嘛？
我们知道当HashMap中的key是普通的数字类型的话，我们key是要经过装箱过程的，如int到Integer, long 到 Long。这个装箱的过程存在一定的性能消耗。而且，HashMap存储value的时候需要依赖额外的Entry类型，这也带来一定的开销。
所以当我们需要一个简单的key为int这种原始数字类型时，可以使用SparseArray, 而key为long时，可使用LongSparseArray。
但是，为维持key的有序性，增删的过程需要使用二分搜索key数组，查的过程也需要通过二分搜索找到key的索引，当数据量过大的时候，二分搜索带来的开销会比装箱、类型创建带来的开销要大。
因此使用SparseArray要求：

1. 数据的key为int或者long
2. 数据量小

源码分析

主要分析put和delete的过程，这2过程直接奠定了其他算法的实现。

1. 增加的过程 put(key1,value)。

1. 通过二分搜索key, 判断是否已经有历史数据
2. 有历史数据直接覆盖，没有的话， 垃圾回收清除删除的数据，扩容数组，再插入到指定索引位置

public void put(int key, E value) {
    // 1. 二分搜索找到key在keys数组中的位置
    // 如果key在keys中找到，那么返回对应索引位置
    //如果没有找到的话，返回插入位置的取反 ~insertIndex 为负值
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) {
        mValues[i] = value;
    } else {
        i = ~i;
        
        // 2. 1如果找到了，但是数据时处于删除的状态(删除key,不会直接从keys中删除key, 而是把其值负值为DELETED的内部常量，见delete过程)，直接覆盖
        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }
        
      // 2.2 垃圾回收(有删除了的值)，并且数据满员了，进行垃圾回收见gc(), 并重新获得插入的位置
      // 如果垃圾数清除的话，那么清除了，后续就不需要再进行扩容数组操作了
        if (mGarbage && mSize >= mKeys.length) {
            gc();

            // Search again because indices may have changed.
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }
        
        // 2.2 插入数据，扩容数组或者直接插入数据，见insert()
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}

private 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;
    }
    
    //扩容数组 * 2
    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;
}

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

// 垃圾回收，清除多余的值，快慢指针，覆盖清除DELETED
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;
}

2. 删除过程 delete(key1)
   删除的过程中，并没有直接通过删除key的方式来缩短key数组，而是将其值标记为删除状态，赋值为DELETED。这样避免不必要的删除和插入操作，当重新增加数据时，可以直接将值更新为最新的值。
   例如： remove(7); put(7,"Seven") 这两个连续操作的过程就不需要先删除7，然后key数组和value数组7之后的元素整体往前移动，而后插入过程也不用整体向后移动。
   不过也正是因为删除过程不进行实际删除，当我们需要获得真实的内部数据(如size)的时候，如果mGarbage为true,即有垃圾数据的时候，我们每次都需要先进行垃圾回收删除数据，再返回真实的数据。

public void delete(int key) {
    // 一样是二分搜索
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    if (i >= 0) { 
        if (mValues[i] != DELETED) {
            mValues[i] = DELETED; //标记为DELETED
            mGarbage = true;
        }
    }
}