SparseArray原理分析

本文主要是介绍SparseArray原理分析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

概述

Google推荐新的数据结构SparseArray。

SparseArray类上有一段注释：

• SparseArrays map integers to Objects. Unlike a normal array of Objects,
• there can be gaps in the indices. It is intended to be more memory efficient
• than using a HashMap to map Integers to Objects, both because it avoids
• auto-boxing keys and its data structure doesn’t rely on an extra entry object
• for each mapping.

这段注释的意思是：使用int[]数组存放key，避免了HashMap中基本数据类型需要装箱的步骤，其次不使用额外的结构体（Entry)，单个元素的存储成本下降。

构造方法

    private int[] mKeys;private Object[] mValues;private int mSize;/*** Creates a new SparseArray containing no mappings.*/public SparseArray() {this(10);}/*** Creates a new SparseArray containing no mappings that will not* require any additional memory allocation to store the specified* number of mappings.  If you supply an initial capacity of 0, the* sparse array will be initialized with a light-weight representation* not requiring any additional array allocations.*/public SparseArray(int initialCapacity) {if (initialCapacity == 0) {mKeys = EmptyArray.INT;mValues = EmptyArray.OBJECT;} else {mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);mKeys = new int[mValues.length];}mSize = 0;}

初始化SparseArray只是简单地创建了两个数组，一个用来保存键，一个用来保存值。

put()

    /*** Adds a mapping from the specified key to the specified value,* replacing the previous mapping from the specified key if there* was one.*/public void put(int key, E value) {// 首先通过二分查找去key数组中查找要插入的key，返回索引int i = ContainerHelpers.binarySearch(mKeys, mSize, key);if (i >= 0) {// 如果i>=0说明数组中已经有了该key，则直接覆盖原来的值mValues[i] = value;} else {// 取反，这里得到的i应该是key应该插入的位置i = ~i;if (i < mSize && mValues[i] == DELETED) {// 如果索引小于当前已经存放的长度，并且这个位置上的值为DELETED(即被标记为删除的值)mKeys[i] = key;mValues[i] = value;return;}// 到这一步说明直接赋值失败，检查当前是否被标记待回收且当前存放的长度已经大于或等于了数组长度if (mGarbage && mSize >= mKeys.length) {// 回收数组中应该被干掉的值gc();// Search again because indices may have changed.// 重新再获取一下索引，因为数组发生了变化i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);}// 最终在i位置上插入键与值，并且size ＋1mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);mSize++;}}

get()

    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];}}

get()中的代码就比较简单了，通过二分查找获取到key的索引，通过该索引来获取到value。

remove()

    public void remove(int key) {delete(key);}public void delete(int key) {// 找到该key的索引int i = ContainerHelpers.binarySearch(mKeys, mSize, key);// 如果存在，将该索引上的value赋值为DELETEDif (i >= 0) {if (mValues[i] != DELETED) {mValues[i] = DELETED;// 标记当前状态为待回收mGarbage = true;}}}

总结

优点：

• 避免了基本数据类型的装箱操作
• 不需要额外的结构体，单个元素的存储成本更低
• 数据量小的情况下，随机访问的效率更高

缺点：

• 插入操作需要复制数组，增删效率降低
• 数据量巨大时，复制数组成本巨大，gc()成本也巨大
• 数据量巨大时，查询效率也会明显下降

Google还提供了其他类似的数据结构，SparseIntArray，SparseBooleanArray，SparseLongArray，ArrayMap等。

参考：SparseArray的使用及实现原理

这篇关于SparseArray原理分析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---