封面图 by Thomas Rohlfs on Unsplash

简介

SparseArray（稀疏数组）是 Android 框架提供的工具类，位于 android.util 包下，用于建立整数和对象之间的映射，效果相当于 HashMap<Integer,Object>，不过它比 HashMap<Integer,Object> 更适合移动应用开发。

SparseArray 相比 HashMap<Integer,Object> 主要做了两点优化：一是避免了自动装箱过程，二是去掉了额外的 Entry 包装对象。

SpareArray 内部采用了两个数组来分别存储 key 和 value，寻找 key 时使用了二分查找。不过，也是由于这个原因，查找效率无法和 HashMap 相比，适用于少量数据的情况。

SparseArray 源码一共才400多行，比较容易懂，这里只分析几个主要方法的源码。

属性

public class SparseArray<E> implements Cloneable {
    //所有被删除的元素都会先指向这个对象
    private static final Object DELETED = new Object();
    //是否需要进行空间回收
    private boolean mGarbage = false;
    //存放key的数组
    private int[] mKeys;
    //存放value的数组
    private Object[] mValues;
    //当前元素数量
    private int mSize;

    //.. 
}

SparseArray 采用了两个数组 mKeys 和 mValues 分别存储键和值，其中存储 key 的数组为 int[] 类型，避免了 HashMap 的自动装箱过程。

mGarbage 表示是否有必要进行「垃圾回收」，当然这里的垃圾回收与 JVM 的垃圾回收不是一个过程，只是进行数组元素的搬移，移除不再需要的元素。

DELETED 是一个静态常量，所有被删除的元素会先指向这个对象，可以把它当做一个标记。

构造方法

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

public SparseArray() {
    //默认容量是10
    this(10);
}

SparseArray 提供了两个构造方法，带参数的构造方法可以指定初始容量，如果使用无参的构造方法，则 SparseArray 默认初始容量是10。

当初始容量为 0 时，代码将 mkeys 和 mValues 初始化为 EmptyArray 的常量，避免重复创建对象。

public static final int[] INT = new int[0];
public static final Object[] OBJECT = new Object[0];

在初始化 mValues 数组时使用了 ArrayUtils 的 newUnpaddedObjectArray 方法，该方法源码如下：

import dalvik.system.VMRuntime;

public static Object[] newUnpaddedObjectArray(int minLen) {
    return (Object[])VMRuntime.getRuntime().newUnpaddedArray(Object.class, minLen);
}

VMRuntime 的 newUnpaddedArray 是一个 native 方法：

/** 
* Returns an array of at least minLength, but potentially larger. The increased size comes from 
* avoiding any padding after the array. The amount of padding varies depending on the 
* componentType and the memory allocator implementation.
*/
@libcore.api.CorePlatformApi
@FastNative
public native Object newUnpaddedArray(Class<?> componentType, int minLength);

这里就不关注具体实现了，不过通过注释可以看出，实际返回的数组大小有可能比 minLength大，也就是说，如果 minLength 是15，那么实际返回的数组大小可能是 16。

增加的大小来源于申请内存时增加的 padding 空间，而 padding 空间一般就是仅做填充用，不过这里的处理是把 padding 空间也算到了数组的长度里，增加了内存空间的利用率（这也就是unpadded 的语义，并不是说申请内存时没有 padding，而是把 padding 算在了数组长度里）。

简单解释一下为什么需要 padding。为了提高 CPU 访问内存的效率，数据的内存地址最好是数据大小的倍数（自然对齐），例如对于一个 32 位的 CPU 来说，如果有一个数据占用连续的 4 个字节，并且第一个字节位于某 4 个字节的边界处，那么就可以把它进行自然对齐。而为了保证可以进行自然对齐，就需要对不满足条件的数据插入 padding，例如对一个32位的 CPU 来说，如果有一个16位的数据，那么在申请内存时就可以在它后面插入 16 位的 padding 空间。

更多详情可以查看维基百科-数据结构对齐。

通过这个方法也可以看到，为了充分利用移动设备上的内存，Android 也是做了很多优化。

put

put 方法用于放入一个整数到对象的映射，源码如下：

public void put(int key, E value) {
    //通过二分查找来确定 key 的位置，有效长度为mSize
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    //给key已经存在元素，直接替换
    if (i >= 0) {
        mValues[i] = value;
    } else {
        // i 指向大于 key 的第一个位置
        i = ~i;
        //此位置之前有过元素不过已经删除了，直接覆盖
        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }

        if (mGarbage && mSize >= mKeys.length) {
            //先进行一次gc
            gc();

            // Search again because indices may have changed. 
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }
        //将新的key插入到数组对应位置
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}

主要逻辑如下：

通过二分查找在 mKeys 数组的 mSize 长度中（因为只有这一段是有效的）查看 key 是否已经存在，如果存在，则直接更新 mValues 数组中对应位置的值
key 不存在，那么将二分查找的返回值取反，得到 key 要插入的位置，检查该位置的 value 是否标记为已删除，如果是，直接在该位置更新 key 和 value。
如果有必要，进行一次「垃圾回收」，并更新即将插入的位置（垃圾回收过程数组元素发生了移动，所以插入位置可能会变动）
在 mKeys 和 mValues 数组中的对应位置分别插入 key 和 value，size 加 1。

那为什么将二分查找的返回值按位取反就能得到新元素的位置呢，这就要看看二分查找在失败时的返回值是什么。

二分查找通过 ContainerHelpers 的 binarySearch 方法实现，源码如下：

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
}

在上面代码中，未找到时，返回值是对 lo 按位取反，而此时 lo 即为第一个大于 key 的位置。

举个简单的例子，如果数组元素为 [-1,0,1,3,6]，在使用二分查找法查找元素 5 时，lo 最后的值是4，也就是元素 5 应该在数组中下标为 4 的位置。在经过按位取反后，binarySearch 的返回值就是个负数。而在 put 方法中，通过 i = ~i 可以得到这个位置下标，然后执行更新或插入即可。

我不知道有多少人跟我一样，写二分查找时如果未找到就直接返回-1，却忽略了这么一条很重要的特性。借助这个特性，我们在维护一个有序数组时，使用一次二分查找既可以检查数组中是否已经包含待添加的元素，又可以知道它应该存在的位置。

insert 方法逻辑比较简单，就是在数组的指定位置插入元素，如果当数组空间不足时进行扩容。

public static <T> T[] insert(T[] array, int currentSize, int index, T element) {
    assert currentSize <= array.length;
    //如果数组空间足够，直接把index后面的元素后移，然后更新index位置的值
    if (currentSize + 1 <= array.length) {
        System.arraycopy(array, index, array, index + 1, currentSize - index);
        array[index] = element;
        return array;
     }
    //数组空间不足时，先申请一个新的数组（大小为原数组的2倍）
    @SuppressWarnings("unchecked")
    T[] newArray = ArrayUtils.newUnpaddedArray((Class<T>)array.getClass().getComponentType(),
            growSize(currentSize));
    //复制 index 之前的元素
    System.arraycopy(array, 0, newArray, 0, index);
    //新元素插入到 index 位置
    newArray[index] = element;
    //复制原数组index之后的元素
    System.arraycopy(array, index, newArray, index + 1, array.length - index);
    return newArray;
}

扩容后的大小使用 growSize() 方法计算，源码如下:

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

可以看到扩容后的容量为数组当前容量的二倍。

至此，SparseArray 源码中的最精华的部分已经分析完了。

get

get 方法就比较简单了，直接通过二分查找法来查找 key 是否在 mKeys 数组中，如果有则返回mValues 数组中相同位置的值，如果没有或者 mValues 中对应位置的元素被标记为已删除，就返回默认值（如果没有设置就会返回null）。

public E get(int key) {
    return get(key, null);
}
public E get(int key, E valueIfKeyNotFound) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    //如果没有找到key或者key对应的元素被标记为删除
    if (i < 0 || mValues[i] == DELETED) {
         return valueIfKeyNotFound;
    } else {
         return (E) mValues[i];
    }
}

remove

remove 用于移除一个映射，源码如下：

public void remove(int key) {
    delete(key);
}

移除元素调用了 delete 方法，源码如下：

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

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

出于性能方面的考虑，delete 方法在删除元素后并未立即搬移数据，而只是把mValues对应位置的元素指向 DELETED，并将 mGarbage设为 true，意味着有必要进行「垃圾回收」了，当下次垃圾回收时，再统一进行元素的搬移操作。

size

size 方法返回当前 SparseArray 中的映射的数量，不过在返回之前，如果 mGarbage 为 true，则需要先调用 gc 方法进行一次「垃圾回收」，因为在移除元素时并没有更新mSize的值，此时 mSize 和真实的映射对的数量可能是不一致的。

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

gc

进行「垃圾回收」的代码如下：

private void gc() {
    //只处理下标在 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;
}

代码也很好理解，思路就是把所有不是 DELETED 的元素都替换到数组的前半部分中是 DELETED 的元素，同时也更新 mKeys 中的对应的 key，然后把后半部分的元素都赋值为null并把 mGarbage 设为 false，最后更新 mSize 的值。

这里用到了典型的双指针法，在 LeetCode 的算法题删除排序数组中的重复项中，移动重复元素时也可以采用相同的逻辑。

clone

SparseArray 实现了 Cloneable 接口， clone 方法同样值得关注下，因为这里涉及深拷贝和浅拷贝的问题。

public SparseArray<E> clone() {
    SparseArray<E> clone = null;
    try {
        clone = (SparseArray<E>) super.clone();
        clone.mKeys = mKeys.clone();
        clone.mValues = mValues.clone();
    } catch (CloneNotSupportedException cnse) {
        /* ignore */
    }
    return clone;
}

通过代码可以看到对 mKeys 和 mValues 直接调用了数组的 clone 方法，那对数组调用 clone 是深拷贝还是浅拷贝呢？

是浅拷贝，也就是重新创建了数组，但两个数组中的元素是一致的。关于这一点可以写几行代码验证下，这里就不过多赘述了。

SparseArray 还提供了一些其他方法，比如 append、clear、valueAt 等，逻辑都比较简单，没有特别大的研究价值，所以就不浪费篇幅展示了。

总结

SparseArray 用于建立整数到对象的映射，针对移动开发进行了优化，主要是想解决 HashMap 存在的自动装箱以及内存占用的问题，但并不适用于数据量较大的情况。

SparseArray 内部通过两个数组 mKeys 和 mValues 来分别存储 key 和 value，其中 mKeys 是一个有序整数数组，在查找 key 时使用了二分查找。

在添加元素时，借助二分查找在未找到元素时 lo 指针指向第一个大于该元素的下标的特性，直接将元素直接插入到对应位置，保证了 mKeys 的有序性。

在删除元素时，只是将 mValues 数组中对应位置的元素指向 DELETED 常量标记为已删除，在需要时（插入元素或调用size）通过 gc 方法来移除被删除元素。

SparseArray 代码虽然不多，但还是有很多值得研究的地方，比如申请数组空间时对内存的利用、维护有序数组时对二分查找的巧妙利用、删除元素时先标记再统一移除的方式等，甚至移除已删除元素的过程还可以直接指导我们做算法题，真的可以说是短小精悍啊。

读源码 | SparseArray 源码解析

简介

属性

构造方法

put

get

remove

size

gc

clone

总结