什么是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.javapublic static 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 )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倍的容量// 扩容后最小容量是8public 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是有序的且是升序