SparseArray是android里为<Integer,Object>的HashMap这样的数据类型所写的类，目的是提高效率，其核心算法是折半查找函数。
不同点：
1.SparseArray的key是int型，不是对象。
2.HashMap底层是数组+链表结构，SparseArray是数组+数组结构。因为链表的时间复杂度比较高，所以SparseArray效率更高。
SparseArray源码
/**
* 存储索引集合.
*/
private int[] mKeys;
/**
* 存储对象集合.
*/
private Object[] mValues;
/**
* 存储的键值对总数.
*/
private int mSize;
/**
* 采用默认的构造函数,则初始容量为10.
*/
public SparseArray() {
this(10);
}
/**
* 使用指定的初始容量构造SparseArray.
*
* @param initialCapacity 初始容量
*/
public SparseArray(int initialCapacity) {
if (initialCapacity == 0) {
// Effective Java中第43条:返回零长度的数组或者集合,而不是:null
mKeys = ContainerHelpers.EMPTY_INTS;
mValues = ContainerHelpers.EMPTY_OBJECTS;
} else {
// 构造initialCapacity大小的int数组和object数组
mKeys = new int[initialCapacity];
mValues = new Object[initialCapacity];
}
// 设置SparseArray存储的键值对个数为0.
mSize = 0;
}
重要方法：
put函数的逻辑：
通过二分查找算法,计算key的索引值.
如果索引值大于0,说明有key对应的value存在,直接替换value即可.
如果索引值小于0,对索引值取反,获取key应该插入的坐标i.
判断是否需要扩容:1.需要扩容,则先扩容; 2.不需要扩容,则利用System.arraycopy移动相应的元素,进行(key,value)键值对插入.
get函数就是利用二分查找获取key的下标,然后从object[] value数组中根据下标获取值.
之所以SparseArray号称比HashMap有更好的性能:
SparseArray更加节约内存,一个int[]数组存储所有的key,一个object[] 数组存储所有的value.
HashMap遇到冲突时,时间复杂度为O(n).而SparseArray不会有冲突,采用二分搜索算法,时间复杂度为O(lgn).
ContainerHelpers:采用二分法查找，提高了一定效率。
网友评论