Android里的SparseArray

除了我们常用JDK提供的容器以外，Android还提供的自己的容器类，如SparseArray就是其中比较常见的一个类。

特点

SparseArray是一个整形到对象的映射；
在整形到对象的映射这方面，它比HashMap在内存上更有效率；

因为它避免了自动装箱的key，它的数据结构不依赖一个额外的Entry对象
它把映射关系存储在两个数组中，用二分查找算法查找元素；

这种实现不宜用在含有大量数据项的数据结构中，当数据量为1K以下的时候，性能差异不是那么明显，保持在50%以下。
对于已知的性能问题，这个容器进行了优化：在remove的时候并不立即执行变更，而是将元素标记为删除，让在适合的时机进行重用，或者在gc（容器内的gc方法）的时候进行全部移除。这个gc操作，会在容器容量增加的时候执行。

只看这些特点也没啥用，顺便分析一下源码，加深下印象吧：

    private int[] mKeys;    private Object[] mValues;    private int mSize;

看一下这三个重要的属性，用于存储key值的整形数组，用于存储value的对象数组，和数组的大小。

再来看看构造函数：

 public SparseArray() {        this(10);    }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;    }

一个无参构造函数，会初始化一个初始大小为10的容量，一个是有参构造函数，如果传入初始容量为0，则创建两个空数组，否则创建指定大小。这里的容量指的是数组的大小，但是这个容器的大小依然是0.

看一看存取操作吧：

public E get(int key) {        return get(key, null);    }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];        }    }

可以看到，取得操作是先经过二分查找到对应的位置，然后取值，没什么好说的，存的操作也是一样。

public void put(int key, E value) {        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);        if (i >= 0) {            mValues[i] = value;        } else {            i = ~i;            if (i < mSize && mValues[i] == 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);            }            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);            mSize++;        }    }public void append(int key, E value) {        if (mSize != 0 && key <= mKeys[mSize - 1]) {            put(key, value);            return;        }        if (mGarbage && mSize >= mKeys.length) {            gc();        }        mKeys = GrowingArrayUtils.append(mKeys, mSize, key);        mValues = GrowingArrayUtils.append(mValues, mSize, value);        mSize++;    }

其中put添加键值对，如果已经存在，则进行替换；
append优化了key比原来map中所有的key都要大的情况。

特点

更多相关文章

随机推荐