/**
* 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);
简单解释一下为什么需要 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++;
}
}
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可以得到这个位置下标，然后执行更新或插入即可。
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
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对应位置的 value 指向 DELETED，并将 mGarbage设为 true，意味着有必要进行「垃圾回收」了，当下次垃圾回收时，再进行元素的搬移操作。