SparseArray是Android官方推荐的一种高效率的Map类工具，如果key值是int值，最好使用SparseArray而不是HashMap
SparseArray内部是使用基本类型int型数组来存放key值，这就意味着其内部省去了hash操作，只要比较int值是否相同即可判断是否是同一个对象，而HashMap虽然也可以用int类型来当key值，但是首先就会有一个自动装箱的过程，将int类型装箱成为Integer，先不论内部实现的效率，单就装箱这一点，其效率必然就会降低很多，再加上其内部会有hash等操作，效率上自然比不上SparseArray， 不过虽然SparseArray效率要高，但是SparseArray只能用于key是int的情形
下面就来看一下SparseArray的具体实现
成员变量
public class SparseArray<E> implements Cloneable {
private static final Object DELETED = new Object();
private boolean mGarbage = false;
private int[] mKeys;
private Object[] mValues;
private int mSize;
...
}
- 可以看到
SparseArray内部是用两个数组分别存放key和value，其中存放key的数组是int数组，这也省去了装箱操作，提升了效率 -
DELETED对象，从名字就可以看出其作用，它是占位对象，表示某索引位置的对象已被删除，用DELETED来占位, 方便后续的gc操作
构造函数
public SparseArray() {
this(10);
}
public SparseArray(int initialCapacity) {
if (initialCapacity == 0) {
//new int[0]
mKeys = EmptyArray.INT;
//new Object[0]
mValues = EmptyArray.OBJECT;
} else {
mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
mKeys = new int[mValues.length];
}
mSize = 0;
}
构造函数比较简单，主要就是根据初始容量初始化两个数组
方法
1. put
public void put(int key, E value) {
//通过二分搜索获取索引， i>=0代表key值已存在， i<0代表key值不存在，i取反下一个元素的插入位置, 【1.1】
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
//直接放入value
mValues[i] = value;
} else {
//取反，获得对应的正数
i = ~i;
if (i < mSize && mValues[i] == DELETED) {
//如果索引处的value是DELETED, 直接替换为新的value即可
mKeys[i] = key;
mValues[i] = value;
return;
}
if (mGarbage && mSize >= mKeys.length) {
//如果容量不足，且有元素被删除, 进行gc操作
//此时数组中可能会有不连续的DELETED值存在，这种值是无效的，还占据空间，gc()的意义在于将所有
//有效的值按顺序连接在一起，替换所有DELETED值，节省空间, 【1.2】
gc();
//重新取得索引值
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
//如果容量够，直接插入，如果容量不够，先扩容，再插入, 【1.3】
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}
- 首先通过二分搜索获取索引值, 返回的i如果是正数，代表key值已经存在， 如果是负数，代表key值不存在，对i取反后，就是即将要插入的索引位置
- 如果key值已经存在，直接覆盖旧的value
- 如果不存在，对i取反，获得正数的索引位置，如果索引处的值是被删除过的即
values[i] = DELETED，直接替换为新的value后返回; 如果有元素被删除过mGarbage = true，且keys数组容量不足，进行gc操作，如果values数组中有DELETED元素存在，将有效地值前移替换这些废弃的值，从而节省空间, 进行完gc后，重新获取索引值 - 进行插入操作，如果容量够，直接插入，如果容量不够，先扩容，再插入
从使用二分搜索法，我们其实就可以知道，
SparseArray存放的数据是按照key值得大小有序排列(升序or降序)，查看过ContainerHelpers.binarySearch后就可以知道，是按升序进行排列
1.1 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;//无符号右移一位，等价于除以2
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
}
>>>1无符号右移一位等价于除以2但又比除法操作更高效，如果要查找的值已经存在，则返回相应的索引值，如果不存在，则返回一个负数，这个负数取反后，就是被查找的元素将要被插入的位置
1.2 gc
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;
}
gc函数的主要功能就是遍历values数组，用有效的value前移替换DELETED无效的值，从而使有效的值连续排列在一起，节省空间
1.3 GrowingArrayUtils.insert
public static int[] insert(int[] array, int currentSize, int index, int element) {
assert currentSize <= array.length;
//容量够，直接插入
if (currentSize + 1 <= array.length) {
System.arraycopy(array, index, array, index + 1, currentSize - index);
array[index] = element;
return array;
}
//容量不够的话，先扩容，如果currentSize <= 4, 扩容成8, 如果 > 4，则扩容至原先容量的2倍
int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize));
System.arraycopy(array, 0, newArray, 0, index);
newArray[index] = element;
System.arraycopy(array, index, newArray, index + 1, array.length - index);
return newArray;
}
- 如果容量够，则直接插入
- 容量不够的话，先扩容，扩容的size是由
growSize函数决定，其原理是如果当前size小于等于4,则固定扩容后的容量是8,如果大于4,则扩容原先容量的两倍，之后拷贝原有数据至新的数组中，最后再根据索引值插入数据
2. get
public E get(int key) {
return get(key, null);
}
public E get(int key, E valueIfKeyNotFound) {
//根据key获得索引值
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
//i<0代表没找到， value = DELETED代表这个值已作废，也表明没找到
if (i < 0 || mValues[i] == DELETED) {
return valueIfKeyNotFound;
} else {
return (E) mValues[i];
}
}
可以看到，get操作非常简单，首先获得索引值，之后直接从values数组中获取相应的值，不论是获取索引值还是获取value, 都是直接操作数组，所以效率非常高
3. delete
public void delete(int key) {
//获取索引值
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
//将对应索引位置的value设为DELETED
if (i >= 0) {
if (mValues[i] != DELETED) {
mValues[i] = DELETED;
mGarbage = true;
}
}
}
和get的操作类似，只不过是获取索引值后，将values数组中对应处的值覆盖为DELETED
性能分析
SparseArray内部使用了二分搜索法，如果在数据量比较小的情况下，其查询效率应该是比较高的，但是随着数据量的增大，二分搜索的效率也会呈现性下降，而HashMap内部在获取对应的索引值时，使用的是先计算hash值再通过hash & (length - 1)的形式获取索引值，当数据量较大时这种方式就比较具有优势，加上HashMap内部对hash算法进行了优化，尽可能的减少了hash碰撞，所以如果数据量很大时，HashMap的查询效率并不会比SparseArray差，甚至可能会优于SparseArray, 但是HashMap如果键值是整型时，不可避免的会进行装箱操作，这一点上SparseArray肯定优于HashMap, 综合来看，在一般的使用场景中，很少会用到非常大的数据量，如果键值是整型数据，应当首选SparseArray
