Android 中的SparseArray

文章出处：http://blog.csdn.net/shift_wwx

请转载的朋友标明出处~~

前言：关于SparseArray 或者相关的如SparseIntArray 网上相关的例子还是很多的，个人还是习惯性根据source code 总结一下。

总结版本基于4.4

一、SparseArray与HashMap

SparseArray是专门为Android提供了一种更加适合Android开发的数据结构，与HashMap比较效率会更高。初看之下，好像是一种数组，其实不然。数组的index是连续的。而SparseArray可以不连续，所以导致SparseArray就具有HashMap的一些特性，但是比HashMap的性能要好。

既然性能要好很多，那是不是所有可以用HashMap的地方都可以用SparseArray代替呢？也不尽然。SparseArray的value可以是任意类型，但它的key只能是Integer类型。如果key是Integer的话，用SparseArray还是很方便的，但是如果是string，那只能用HashMap了。

SparseArray 相关的还有SparseIntArray、SparseBooleanArray、LongSparseArray。下面都会做一下说明。

二、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. * * <p>Note that this container keeps its mappings in an array data structure, * using a binary search to find keys.  The implementation is not intended to be appropriate for * data structures * that may contain large numbers of items.  It is generally slower than a traditional * HashMap, since lookups require a binary search and adds and removes require inserting * and deleting entries in the array.  For containers holding up to hundreds of items, * the performance difference is not significant, less than 50%.</p> * * <p>To help with performance, the container includes an optimization when removing * keys: instead of compacting its array immediately, it leaves the removed entry marked * as deleted.  The entry can then be re-used for the same key, or compacted later in * a single garbage collection step of all removed entries.  This garbage collection will * need to be performed at any time the array needs to be grown or the the map size or * entry values are retrieved.</p> * * <p>It is possible to iterate over the items in this container using * {@link #keyAt(int)} and {@link #valueAt(int)}. Iterating over the keys using * <code>keyAt(int)</code> with ascending values of the index will return the * keys in ascending order, or the values corresponding to the keys in ascending * order in the case of <code>valueAt(int)</code>.</p> */public class SparseArray<E> implements Cloneable {    private static final Object DELETED = new Object();    private boolean mGarbage = false;    private int[] mKeys;    private Object[] mValues;    private int mSize;    /**     * Creates a new SparseArray containing no mappings.     */    public SparseArray() {        this(10);    }

从字面的意思来看SparseArray指的是稀疏数组。从注释来看，用SparseArray 来替代java中的HashMap在性能上有更好的提高，定义的空间在delete的时候并没有释放，而是做了标记保留了下来，方便后来重复使用，直到特殊调用时候gc出来。另外就是查找的方式用的是binary search(折半查找)，这也是SparseArray 特殊之处，可以提高效率。

构造函数：

 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个，当然里面都是空的。也可以指定数组的最小个数。

查找：

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

不指定默认返回值的时候，返回的是null。

删除：

    public void delete(int key) {        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);        if (i >= 0) {            if (mValues[i] != DELETED) {                mValues[i] = DELETED;                mGarbage = true;            }        }    }    public void remove(int key) {        delete(key);    }    public void removeAt(int index) {        if (mValues[index] != DELETED) {            mValues[index] = DELETED;            mGarbage = true;        }    }    public void removeAtRange(int index, int size) {        final int end = Math.min(mSize, index + size);        for (int i = index; i < end; i++) {            removeAt(i);        }    }

删除方法提供了四个：

remove、delete是一个效果，参数都是key；

removeAt提供的却是value 的index；

removeAtRange删除的是一个范围，参数是value的index 和偏移size；

注意：remove之后mGarbage都会被置为true，在适当的时候用于gc，gc完才能重置为false。

修改：

    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 setValueAt(int index, E value) {        if (mGarbage) {            gc();        }        mValues[index] = value;    }        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++;    }

修改提供了三个函数：

1）put 分为三种情况，一是数组已经有了，那就直接替换；二是数组中 value 之前被delete了，那就直接赋值；三是数组压根没出现过，用的是insert方式。

虽然这里insert可能影响到了效率，但是相对于binary search还是可以忽略的。

2）setValueAt 参数是values的index 和 value，个人感觉这里存在个漏洞，需要判断index 的存在性的。

3）append 参数换成了key 和 value，如果key 小于mKeys 最大的值，采用的是insert 方式，否则就用append在最后添加了。

SparseArray差不多的接口已经说的差不多了，来看一下几个核心的接口：

1、int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    static int binarySearch(int[] array, int size, int value) {        int lo = 0;        int hi = size - 1;        while (lo <= hi) {            final int mid = (lo + hi) >>> 1;//除以2，无符号右移1位            final int midVal = array[mid];            if (midVal < value) {                lo = mid + 1;            } else if (midVal > value) {                hi = mid - 1;            } else {                return mid;  // value found            }        }        return ~lo;  // value not present    }

在找不到的时候，返回的却是 ~lo，不是0也不是-1。

2、mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);

    public static <T> T[] insert(T[] array, int currentSize, int index, T element) {        assert currentSize <= array.length;        if (currentSize + 1 <= array.length) {            System.arraycopy(array, index, array, index + 1, currentSize - index);            array[index] = element;            return array;        }        @SuppressWarnings("unchecked")        T[] newArray = ArrayUtils.newUnpaddedArray((Class<T>)array.getClass().getComponentType(),                growSize(currentSize));        System.arraycopy(array, 0, newArray, 0, index);        newArray[index] = element;        System.arraycopy(array, index, newArray, index + 1, array.length - index);        return newArray;    }

用的是System.arraycopy这里就不多解释了。

三、SparseIntArray

与SparseArray差不多，几个接口有点诧异。

1、构造函数

    public SparseIntArray(int initialCapacity) {        if (initialCapacity == 0) {            mKeys = EmptyArray.INT;            mValues = EmptyArray.INT;        } else {            mKeys = ArrayUtils.newUnpaddedIntArray(initialCapacity);            mValues = new int[mKeys.length];        }        mSize = 0;    }

SparseArray 是new 的mValues：

mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);mKeys = new int[mValues.length];

2、delete

    public void delete(int key) {        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);        if (i >= 0) {            removeAt(i);        }    }    public void removeAt(int index) {        System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1));        System.arraycopy(mValues, index + 1, mValues, index, mSize - (index + 1));        mSize--;    }

直接删掉了，没有保留一说

3、没有了remove、removeAtRange、setValueAt等接口

四、SparseBooleanArray

与前面两个差不多，value是boolean 型

1、构造函数

    public SparseBooleanArray(int initialCapacity) {        if (initialCapacity == 0) {            mKeys = EmptyArray.INT;            mValues = EmptyArray.BOOLEAN;        } else {            mKeys = ArrayUtils.newUnpaddedIntArray(initialCapacity);            mValues = new boolean[mKeys.length];        }        mSize = 0;    }

2、delete

    public void delete(int key) {        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);        if (i >= 0) {            System.arraycopy(mKeys, i + 1, mKeys, i, mSize - (i + 1));            System.arraycopy(mValues, i + 1, mValues, i, mSize - (i + 1));            mSize--;        }    }    /** @hide */    public void removeAt(int index) {        System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1));        System.arraycopy(mValues, index + 1, mValues, index, mSize - (index + 1));        mSize--;    }

其实完全可以跟SparseIntArray 一样，直接调用removeAt。

3、没有了remove、removeAtRange等接口，与SparseIntArray 比较多了setValueAt借口

五、LongSparseArray

public class LongSparseArray<E> implements Cloneable {

个人感觉这个就是从SparseArray copy过来的接口，这里为什么要需要E？

更多相关文章

随机推荐