SparseArray 解析

2018-03-20  本文已影响0人  那时青菜

   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:采用二分法查找,提高了一定效率。

上一篇 下一篇

猜你喜欢

热点阅读