SparseArray是Android framework中提供的轻量级的键值对数据结构，我们知道空间和效率从来都是相悖的，SparseArray的实现正是以时间来换取空间效率，适合小规模数据的存储。
下面来了解下SparseArray的特点，使用，并分析部分源码。
一、特点
SparseArray以键值对的形式保存数据，key是int类型，并且是唯一的不允许重复的key，而value可以是任何object。
SparseArray是轻量级的，使用2个数组分别保存key和value，并通过数组下标来对应关联。key数组是保持有序的。
优点
相比HashMap更加节省内存空间，数据存储只依赖key和value2个数组，数组空间是可复用的，数据的存储密度较高。
因为key数组是有序的，通过key获取value相对高效。
缺点：
key数组是保持有序的，在插入和查找时，通过二分法确定位置key的下标，比较耗时；
插入删除等操作可能会移动数组数据。
综合来说，SparseArray适用于小数据量的键值对场景。数据量达到几百时，效率优势和HashMap相比已不明显。
二、使用方式
插入
1. SparseArray初始化时需要指定存储数据的具体类型
2. 使用put方法，插入key和对应的value
SparseArray<String> strArray = new SparseArray<>();
strArray.put(3, "DDDD");
strArray.put(1, "AAAA");
strArray.put(4, "CCCC");
strArray.put(2, "BBBB");
遍历
SparseArray没有实现Iterable，只能通过手动循环遍历：
for(int i = 0;i<strArray.size();i++){
String value = strArray.valueAt(i);
//do sth
}
插入的4条数据，打印是根据key值从小到大的顺序输出的，这也印证了在执行插入之后，key数组是保持有序的：
value at 0:AAAA
value at 1:BBBB
value at 2:DDDD
value at 3:CCCC
删除
删除元素的方法有2个：
1. removeAt，删除指定下标的value。
2. delete通过key删除对应的value。
从以上插入的4个数据中删除其中2个：
strArray.remove(3);//删除key为3的值，即DDDD
strArray.removeAt(0);//删除数组中的第一个值，即AAAA
结果只剩下BBBB和CCCC：
value at 0:BBBB
value at 1:CCCC
通过key获取元素
通过get方法传入key来获取对应的value：
Log.i(TAG, "get 1:" +strArray.get(1));
Log.i(TAG, "get 4:" +strArray.get(4));
输出：
get 1:null //key=1的值为AAAA，已经被删除，因此返回null
get 4:CCCC
查找
指定key或者value来查找其下标值：
1. indexOfKey二分法从mKeys数组中查找key的下标
2. indexOfValue 遍历查找mValues数组中value元素的下标。
Log.i(TAG, "index of key 4:" +strArray.indexOfKey(4));
Log.i(TAG, "index of value BBBB:" +strArray.indexOfValue("BBBB"));
输出：
key=4的值，数组下标为1，
BBBB在value数组中下标为0
index of key 4:1
index of value BBBB:0
三、源码学习
SparseArray采用时间换取空间的方式来提高手机App的运行效率，这也是其与HashMap的区别；HashMap通过空间换取时间，查找迅速；HashMap中当table数组中内容达到总容量0.75时，则扩展为当前容量的两倍。
- SparseArray的key为int，value为Object
- 在Android中，数据长度小于千时，用于替换HashMap
- 相比与HashMap，其采用 时间换空间 的方式，使用更少的内存来提高手机APP的运行效率(HashMap中当table数组中内容达到总容量0.75时，则扩展为当前容量的两倍
下面我们来对其源码进行学习：
构造方法
// 构造方法
public SparseArray() {
this(10);
} // 构造方法
public SparseArray(int initialCapacity) {
if (initialCapacity == 0) {
mKeys = EmptyArray.INT;
mValues = EmptyArray.OBJECT;
} else {
// key value各自为一个数组，默认长度为10
mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
mKeys = new int[mValues.length];
}
mSize = 0;
}
源码说明：
- SparseArray构造方法中，创建了两个数组mKeys、mValues分别存放int与Object，其默认长度为10。
put(int key, E value)
public void put(int key, E value) {
// 二分查找,key在mKeys列表中对应的index
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
// 如果找到，则直接赋值
if (i >= 0) {
mValues[i] = value;
}
// 找不到
else {
// binarySearch方法中，找不到时，i取了其非，这里再次取非，则非非则正
i = ~i;
// 如果该位置的数据正好被删除,则赋值
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
// 如果有数据被删除了，则gc
if (mGarbage && mSize >= mKeys.length) {
gc();
// Search again because indices may have changed.
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
// 插入数据，增长mKeys与mValues列表
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}
源码说明：
- 因为key为int,不存在hash冲突
- mKeys为有序列表，通过二分查找，找到要插入的key对应的index (这里相对于查找hash表应该算是费时间吧，但节省了内存，所以是 时间换取了空间)
- 通过二分查找到的index，将Value插入到mValues数组的对应位置
get(int key)
// 通过key查找对应的value
public E get(int key) {
return get(key, null);
}
// 通过key查找对应的value
public E get(int key, E valueIfKeyNotFound) {
// mKeys数组中采用二分查找，找到key对应的index
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
// 没有找到，则返回空
if (i < 0 || mValues[i] == DELETED) {
return valueIfKeyNotFound;
} else {
// 找到则返回对应的value
return (E) mValues[i];
}
}
源码说明：
- 每次调用get，则需经过一次mKeys数组的二分查找，因此mKeys数组越大则二分查找的时间就越长，因此SparseArray在大量数据，千以上时，会效率较低
ContainerHelpers.binarySearch(mKeys, mSize, key) 二分查找
// array为有序数组
// size数组中内容长度
// 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];
// 如果中间元素小于要查找元素，则midIndex赋值给 lo
if (midVal < value) {
lo = mid + 1;
}
// 如果中间元素大于要查找元素，则midIndex赋值给 hi
else if (midVal > value) {
hi = mid - 1;
}
// 找到则返回
else {
return mid; // value found
}
}
// 找不到,则lo 取非
return ~lo; // value not present
}