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