菜鸟看源码之SparseArray

简书同步发布菜鸟看源码之SparseArray SparseArray：翻译为稀疏数组，数组元素之间可以有间隙。

SparseArray 将整数映射到对象。和普通的对象数组不一样，SparseArray的元素之间可以有间隙。和使用HashMap将Integer映射成Object相比，SparseArray 内存使用效率更高，因为SparseArray 避免的键的自动装箱，而且对于每个映射，SparseArray 不依赖额外的entry对象（HashMap 每个节点是一个entry对象）。

注意，SparseArray 内部的数据结构使用数组实现键值的映射，使用二分查找来查找键。SparseArray 不适合用来存储大量的数据。SparseArray通常来说比传统的HashMap速度要慢，因为SparseArray 使用二分查找并且在增删操作的时候要在数组中进行插入和删除元素（要在数组中进行元素的移动）。如果只存储数百个元素，那么SparseArray 和HashMap的性能差异不是很明显，低于50%。

在删除键值对的时候，SparseArray 进行了优化。SparseArray 会把对应的值标记为deleted，而不是立即压缩数组（把删除的元素的后面的所有元素向前移动）。这个键值映射可以被重用，或者在晚一些时候在一个单独的垃圾回收阶段压缩整个数组，统一将标记为deleted的元素删除。在增加数组容量、获取SparseArray的size或者获取一个映射值之前，垃圾回收操作都会被执行。

可以用keyAt(int) 和valueAt(int)来遍历键数组和值数组，在遍历的时候，如果index是递增的，那么keyAt(int)方法返回的key和valueAt(int)返回的value是递增的。这一段翻译的不好，使用白话文来说一下。

private SparseArray<String> sparseArray = new SparseArray<>(); for (int index = 0; index < sparseArray.size(); index++) { //返回的key是递增的 int key = sparseArray.keyAt(index); //返回的value也是递增的 String value = sparseArray.valueAt(index); }

比如上面这个SparseArray，当我们遍历它的时候，index是递增的，那么返回的key是递增的，返回的value也是递增的。

上面的说明 强烈建议看看源代码里面的英文原版。

下面是SparseArray的部分属性和方法

//用作标记某项的状态为删除状态 private static final Object DELETED = new Object(); //是否进行垃圾回收 private boolean mGarbage = false; //存放key的数组 private int[] mKeys; //存放value的数组 private Object[] mValues; //当前的key数组和value数组的大小 private int mSize;

构造函数

public SparseArray() { this(10); } /** * 根据传入的initialCapacity，找出一个最适合增长数组的长度 length，（这个有点不懂，暂时略过） * 初始化一个容量为length的key数组和value数组,比如传入的initialCapacity为10， * 那么最终生成的数组容量是13 */ 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; }

如果传入的初始容量为0，那么就分别创建长度为0的键数组和值数组

public final class EmptyArray { private EmptyArray() {} //... public static final int[] INT = new int[0]; public static final Object[] OBJECT = new Object[0]; }

如果传入的初始容量不为0，就初始化合适长度的数组。

mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity); mKeys = new int[mValues.length];

关于ArrayUtils是个什么东西，暂时还不了解。

public class ArrayUtils { private ArrayUtils() { /* cannot be instantiated */ } public static Object[] newUnpaddedObjectArray(int minLen) { return (Object[])VMRuntime.getRuntime().newUnpaddedArray(Object.class, minLen); } }

SparseArray的put(int key, E value) 方法

/** * 添加一个键值对，如果已经存在相同的键，则修改键对应的value */ public void put(int key, E value) { //查找是否存在相同的键 int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i >= 0) { //如果存在，就更新对应的value mValues[i] = value; } else {//处理i为负数的情况 //如果没找到，比如键值数组为[0,1,2,3,7,8],要找的key为5,找不到对应的key //返回的i为-5 i = ~i;//，-5取反等于4，也就是元素要插入的位置 // 如果i小于mSize，并且i对应的值已经被标记为DELETED，那么就直接更新i位置上的value值 if (i < mSize && mValues[i] == DELETED) { mKeys[i] = key; mValues[i] = value; return; } /** * 因为SparseArray不是线程安全的，如果在这个过程中其他线程删除了元素， * 会导致键数组的长度发生变化，所以我们gc一下然后重新再找一遍。 * 删除操作方法内部会将mGarbage置为true */ if (mGarbage && mSize >= mKeys.length) { gc(); //gc过后再次查找，因为元素的下标可能会改变，注意binarySearch返回值还是负数，因为 //删除操作删除了某些元素，我们第一次没找到，然后再在删除元素后的数组中也是找不到的 i = ~ContainerHelpers.binarySearch(mKeys, mSize, key); } //最后把键和值分别插入到合适的位置 mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key); mValues = GrowingArrayUtils.insert(mValues, mSize, i, value); mSize++; } }

使用到的二分查找算法如下

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; // 找到值 } } return ~lo; // 如果没找到，则对lo取反并返回 }

这里有个疑问，没找到就返回-1呗，返回~lo是什么幺蛾子？

原因：当我们没有找到要查找的元素的时候，lo就表示如果我们要将该元素插入到数组中时，元素所在的位置。我们如果返回lo，就表示我们找到了元素，这是不行的，所以我们将lo取反返回（~lo）。当我们对返回~lo取反的时候，就得到了lo值,就可以将元素直接插入到lo位置上。也是没谁了。

SparseArray的gc()方法

/** * 压缩数组，把所有的元素向前移动，一次性删除所有被标记为deleted的value， * 改变数组的size */ 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; }

GrowingArrayUtils的insert方法

/** * 在指定的位置上向数组中插入一个元素，如果没有更多的空间，就扩展数组的容量。 * * @param array 要添加元素的数组，不能为null。 * @param currentSize 数组中元素的数量。必须小于等于数组的长度。 * @param element 要插入的元素。 * @return 插入了新元素的数组。可能跟指定的数组不是同一个（扩容了）。 * */ 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; } //空间不够了，进行扩容 @SuppressWarnings("unchecked") T[] newArray = ArrayUtils.newUnpaddedArray((Class<T>)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; }

SparseArray的get方法

public E get(int key) { return get(key, null); } /** * 如果存在key对应的value则返回value，否则返回指定的valueIfKeyNotFound，默认是null */ public E get(int key, E valueIfKeyNotFound) { //使用二分查找，找到key在键值数组中的位置 int i = ContainerHelpers.binarySearch(mKeys, mSize, key); //没找到 if (i < 0 || mValues[i] == DELETED) { return valueIfKeyNotFound; } else { ///找到了，转换成对应的类型返回 return (E) mValues[i]; } }

SparseArray的remove(int key)方法

public void remove(int key) { //调用delete方法 delete(key); }

SparseArray的delete(int key)方法

/** * 删除指定的key对应的value，如果存在的话。 * 只是把指定的key对应的value标记为deleted，并没有真正的删除元素， * 数组的size也没有改变。然后把mGarbage置为true */ public void delete(int key) { //使用二分查找，找到key在键值数组中的位置 int i = ContainerHelpers.binarySearch(mKeys, mSize, key); //如果key值存在，并且对应位置上的value没有被标记为DELETED，则标记为DELETED， //并把mGarbage置为true if (i >= 0) { if (mValues[i] != DELETED) { mValues[i] = DELETED; mGarbage = true; } } }

SparseArray的removeAt方法

/** * 把index对应位置上的value标记为deleted，mGarbage置为true， * 并不会真正把index位置上的元素删除，所以数组的size还是不变的 * 这个方法并没有进行边界检查，所以调用的时候要小心，不要数组越界 */ public void removeAt(int index) { if (mValues[index] != DELETED) { mValues[index] = DELETED; mGarbage = true; } }

注意这个方法和delete方法的区别，该方法没有根据key来删除元素。

SparseArray的removeAtRange 方法

/** * 批量删除指定位置上的value，这个方法并没有进行边界检查，所以调用的时候要小心， * 不要数组越界 * * @param index 起始index * @param size 删除value的个数 */ public void removeAtRange(int index, int size) { final int end = Math.min(mSize, index + size); for (int i = index; i < end; i++) { removeAt(i); } }

size方法

/** * 获取键值对的数量，在获取之前先进行gc */ public int size() { if (mGarbage) { gc(); } return mSize; }

clear方法

/** * 删除所有的键值对 */ public void clear() { int n = mSize; Object[] values = mValues; for (int i = 0; i < n; i++) { values[i] = null; } mSize = 0; mGarbage = false; }

keyAt方法

/** *返回指定index位置上对应的key *这个方法并没有检查是否数组越界，调用的时候要小心 */ public int keyAt(int index) { if (mGarbage) { gc(); } return mKeys[index]; }

valueAt方法

/** *返回指定index位置上对应的value *这个方法并没有检查是否数组越界，调用的时候要小心 */ public E valueAt(int index) { if (mGarbage) { gc(); } return (E) mValues[index]; }

append方法

/** * 如果要put的key大于键值数组中所有的key，直接把新的键值对，分别放入key数组末尾 * 和value数组末尾 */ public void append(int key, E value) { if (mSize != 0 && key <= mKeys[mSize - 1]) { put(key, value); return; } if (mGarbage && mSize >= mKeys.length) { gc(); } mKeys = GrowingArrayUtils.append(mKeys, mSize, key); mValues = GrowingArrayUtils.append(mValues, mSize, value); mSize++; }

参考链接：

SparseArray源码分析

SparseArray

EmptyArray类

ArrayUtils

GrowingArrayUtils