共计 3631 个字符，预计需要花费 10 分钟才能阅读完成。
- 什么是 SparseArray？
- 它的外部实现采纳了什么数据结构？
- SparseArray 相比于 HashMap 的优劣势是什么？
什么是 SparseArray？
SparseArray 存储的是键值对，以 int 作为 key，Object 作为 value。Sparse 有稠密、短少的意思。SparseArray 利用场景是绝对稀少的数据，个别是几百以内。
SparseArray 采纳的数据结构？
SparseArray 并不像 HashMap 采纳一维数组 + 单链表和二叉树构造，而是采纳两个一维数组，一个是存储 key(int 类型), 一个是存 value object。
private int[] mKeys; // 存储 key
private Object[] mValues; // 存储 value 对象
private int mSize; // 记录存储键值对的数量 mKeys 和 mValues 读写时采纳的下标是一一对应的。
SparseArray 默认容量多大？
SparseArray 在默认构造函数中指定其默认容量大小。默认为 10
初始化后 mSize = 0，实例化 mKeys 和 mValues。
SparseArray get 办法的流程剖析
输出一个 int 型的 key，通过二分法查找匹配的下标。若没找到对应的下标，则返回 null 或用户指定的默认对象。
key 是递增寄存的。二分法查找下标时，可能会返回一个负值，此时示意在 mKeys 中没找到对应的键。
public E get(int key) {return get(key, null);
}
/**
* 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) {int i = ContainerHelpers.binarySearch(mKeys, mSize, key); // 二分法查找下标
if (i < 0 || mValues[i] == DELETED) {
// 找到的下标为负或以后地位元素以被删除，表明没找到
return valueIfKeyNotFound;
} else {return (E) mValues[i]; // 找到指定元素
}
}SparseArray put 办法的流程剖析
public void put(int key, E value) {
// 二分法找到 key 的下标
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
// 代表以后曾经存在 key 及其对应的值，间接替换 value
mValues[i] = value;
} else {
// 示意以后并不存在 key，则应增加新的键值对
// i 取反，失去要增加的数组地位下标。二叉查找返回的是 key 的“该当”寄存的地位下标。i = ~i;
if (i < mSize && mValues[i] == DELETED) {
// 原来地位上的元素曾经被删掉了，间接赋值替换
mKeys[i] = key;
mValues[i] = value;
return;
}
if (mGarbage && mSize >= mKeys.length) {
// 容量有余，进行回收操作
gc();
// 从新查找指标下标
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
// 指标下标为 i，将 key 增加进 mKeys 数组中
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
// 指标下标为 i，将 value 插入 mValues 数组中
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
// 已存储的数据个数加 1
mSize++;
}
}
// GrowingArrayUtils.java
public static <T> T[] insert(T[] array, int currentSize, int index, T element) {
assert currentSize <= array.length;
if (currentSize + 1 <= array.length) {
// 以后数组容量短缺，index 开始的元素后移 1 位
System.arraycopy(array, index, array, index + 1, currentSize - index);
array[index] = element;
return array;
}
// 容量有余，先扩容生成新的数组 newArray
@SuppressWarnings("unchecked")
T[] newArray = ArrayUtils.newUnpaddedArray((Class<T>)array.getClass().getComponentType(),
growSize(currentSize));
// 将原来数组 index 之前的局部复制到新数组对象中
System.arraycopy(array, 0, newArray, 0, index);
newArray[index] = element; // 插入元素
// 将原数组 index+ 1 之后的元素拷贝到新数组中
System.arraycopy(array, index, newArray, index + 1, array.length - index);
return newArray;
}
// 扩容计算规定，以后容量小于等于 4 则返回 8；否则返回 2 倍的容量
// 扩容后最小容量是 8
public static int growSize(int currentSize) {return currentSize <= 4 ? 8 : currentSize * 2;}key 下标的二叉查找办法剖析
二叉查找办法 ContainerHelpers.binarySearch(int[] array, int size, int value)
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
}如果没有找到输出 value 对应的下标，则会返回一个按位取反后的值（个别是个负值）。
例如输出 array 是 [1,2,4,5]，size 是 4，value 是 3；那么会失去 2 的取反值。而 2 就是 value 的指标地位下标。
SparseArray 最大容量？每次扩容多少？
SparseArray 并不像 HashMap 一样定义有最大容量是多少，最大能够达到 Integer.MAX_VALUE，可能会报 oom。每次扩容时如果以后容量小于 5 则扩容是 8，否则扩容为原容量的 2 倍。
public static int growSize(int currentSize) {return currentSize <= 4 ? 8 : currentSize * 2;}SparseArray 与 HashMap 的比拟，利用场景是？
- SparseArray 采纳的不是哈希算法，HashMap 采纳的是哈希算法。
- SparseArray 采纳的是两个一维数组别离用于存储键和值，HashMap 采纳的是一维数组 + 单向链表或二叉树。
- SparseArray key 只能是 int 类型，而 HashMap 的 key 是 Object。
- SparseArray key 是有序存储（升序），而 HashMap 不是。
- SparseArray 默认容量是 10，而 HashMap 默认容量是 16。
- SparseArray 默认每次扩容是 2 倍于原来的容量，而 HashMap 默认每次扩容时是原容量 *0.75 倍
- SparseArray value 的存储被不像 HashMap 一样须要额定的须要一个实体类（Node）进行包装
- SparseArray 查找元素总体而言比 HashMap 要逊色，因为 SparseArray 查找是须要通过二分法的过程，而 HashMap 不存在抵触的状况其技术处的 hash 对应的下标间接就能够取到值。
针对下面与 HashMap 的比拟，采纳 SparseArray 还是 HashMap，倡议依据如下需要选取：
- 如果对内存要求比拟高，而对查问效率没什么大的要求，能够是应用 SparseArray
- 数量在百级别的 SparseArray 比 HashMap 有更好的劣势
- 要求 key 是 int 类型的，因为 HashMap 会对 int 自定装箱变成 Integer 类型
- 要求 key 是有序的且是升序
【Android 零根底入门教程视频参考】