SparseArray家族

SparseArray基于键值对存储数据,key为int,value为object,简单使用如下:

        //声明        SparseArray sparseArray= new SparseArray();        //增加元素,append方式        sparseArray.append(0, "myValue");        //增加元素,put方式        sparseArray.put(1, "myValue");        //删除元素,二者等同        sparseArray.remove(1);        sparseArray.delete(1);        //修改元素,put或者append相同的key值即可        sparseArray.put(1,"newValue");        sparseArray.append(1,"newValue");        //查找,遍历方式1        for(int i=0;i<sparseArray.size();i++){            Log.d(TAG,sparseArray.valueAt(i));        }        //查找,遍历方式2        for(int i=0;i<sparseArray.size();i++){            int key = sparseArray.keyAt(i);            Log.d(TAG,sparseArray.get(key));        }

LongSparseArray 和SparseArray 相比,唯一的不同就是key值为long,所以LongSparseArray可以存储的数据元素就比SparseArray多,int的范围是-2^31 到 231-1,而long是-263 到 2^63-1。

SparseBooleanArray,SparseIntArray,SparseLongArray,这三个数据结构的key值的类型也是int,value值的类型也固定,SparseBooleanArray的value固定为boolean类型,SparseIntArray的value固定为int类型,SparseLongArray的value固定为long类型。

总结一下这四种数据结构的key,value类型:

SparseArray          LongSparseArray      SparseBooleanArray   SparseIntArray       SparseLongArray      

上述四种数据结构的key类型都是int,而不是Integer,相较于使用HashMap的话,省去了装箱拆箱过程,查询、存储等操作效率更高,而且int的存储开销也远小于Integer。

SparseArray实现原理

SparseArray内部的重要属性:

public class SparseArray implements Cloneable {    private static final Object DELETED = new Object();    private boolean mGarbage = false;    private int[] mKeys;    private Object[] mValues;    private int mSize;}

DELETED

static final 的一个静态Object实例,当一个键值对被remove后,会在对应key的value下放置该对象,标记该元素已经被删除,只是标记删除,没有真正的删除。

mGarbage

当值为true,标志数据结构中有元素被删除,可以触发gc对无效数据进行回收,真正删除。

mKeys

用于存放Key的数组,通过int[] 进行存储,与HashMap相比减少了装箱拆箱的操作,同时一个int只占4字节;一个重要特点,mKeys的元素是升序排列的,也是基于此,我们才能使用二分查找。

mValues

用于存放与Key对应的Value,通过数组的position 进行映射;如果存放的是int型等,可以用SparseIntArray ,存放的Values也是int数组,性能更高。

mSize

mSize的大小等于数组中mValues的值等于非DELETED的元素个数。

remove方法源码:

    public void delete(int key) {        //查找对应key在数组中的下标,如果存在,返回下标,不存在,返回下标的取反;        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);        //key存在于mKeys数组中,将元素删除,用DELETED替换原value,起标记作用;        if (i >= 0) {            if (mValues[i] != DELETED) {                mValues[i] = DELETED;                mGarbage = true;            }        }    }         /**     * @hide     * Removes the mapping from the specified key, if there was any, returning the old value.     */    public E removeReturnOld(int key) {        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);             if (i >= 0) {            if (mValues[i] != DELETED) {                final E old = (E) mValues[i];                mValues[i] = DELETED;                mGarbage = true;                return old;            }        }        return null;    }         /**     * Alias for {@link #delete(int)}.     */    public void remove(int key) {        delete(key);    }

二分查找:

class ContainerHelpers {    // This is Arrays.binarySearch(), but doesn't do any argument validation.    //第一个参数array为keys的数组,第二个为数组中元素个数(与keys的length不一定相等),第三个value为目标的key    static int binarySearch(int[] array, int size, int value) {        //lo为二分查找的左边界        int lo = 0;        //hi为二分查找的右边界        int hi = size - 1;        //还没找到,继续查找        while (lo >> 1;            //获取中间元素            final int midVal = array[mid];            // 目标key在右部分  。。。。感觉这部分太简单了            if (midVal  value) {                hi = mid - 1;            } else {                //相等,找到了,返回key对应在array的下标;                return mid;  // value found            }        }        //没有找到该元素,对lo取反!!!!!很重要        return ~lo;  // value not present    }

该方法是通过二分查找返回了当前key的对应于mKeys数组的下标,如果没有找到,就返回一个特殊的负数。二分法返回的数值如果非负数,我们则对其所对应的value进行替换成DELETED,用于标记该key已经被删除,但是key仍然存在于mKeys数组,因此删除是一个伪删除同时,我们将garbage赋值true,代表数组中可能存在垃圾。

put方法源码:

    public void put(int key, E value) {        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);        //原来已经有key,可能是remove后,value存放着DELETED,也可能是存放旧值,那么就替换        if (i >= 0) {            mValues[i] = value;        } else {            //没有找到,对i取反,得到i= lo(ContainerHelpers.binarySearch)            i = ~i;            //如果i小于数组长度,且mValues==DELETED(i对应的Key被延迟删除了)            if (i = mKeys.length) {                //真实删除,将所有延迟删除的元素从数组中清除;                gc();                //清除后重新确定当前key在数组中的目标位置;                // Search again because indices may have changed.                i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);            }            //不存在垃圾或者当前数组仍然可以继续添加元素,不需要扩容,则将i之后的元素全部后移,数组中仍然存在被DELETED的垃圾key;            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);            //新元素添加成功,潜在可用元素数量+1            mSize++;        }    }

put方法也调用了ContainerHelpers.binarySearch方法先进行查找,查找到大于0,则在数组中找到了对应的key,此时,直接将value进行替换即可;如果没有找到,返回的是~lo,将i取反后,此时i就是我们需要插入的位置。

此刻,我们找到了i,就是目标位置,如果没有设置延迟删除(DELETED),那么由于数组的特点,我们需要将i序号之后的数组后移,这样就会产生一个较大的性能损耗;,但是如果我们设置了延迟删除且mValue[i]上当前的元素恰巧为DELETED,那么此时我们可以用当前的key替换原来mKeys的key,且用当前value替换DELETED;这样就成功避免了一次数组的迁移操作。

但是事情不可能永远凑巧,如果,i上的元素并非恰好被删除呢?那么此时我们会判断mGarbage,如果为true那么我们执行一次gc,将无效数据移除,再进行一次二分查找,然后将i之后的数据全部后移,将当前key插入;如果mGarbage为false,那么证明其中的数据全部存在,因此不需要gc,直接进行元素插入并将数组后移。

Get方法源码:

    public E get(int key) {        return get(key, null);    }         /**     * Gets the Object mapped from the specified key, or the specified Object     * if no such mapping has been made.     */    @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];        }    }

与HashMap做比较

1、key类型都是int,而不是Integer,相较于使用HashMap的话,省去了装箱拆箱过程,查询、存储等操作效率更高,而且int的存储开销也远小于Integer

2、使用二分查找法判断元素的位置,所以,在获取数据的时候非常快,时间复杂度为O(lgN),比HashMap快的多,因为HashMap获取数据是通过遍历Entry[]数组来得到对应的元素。

3、使用场景

虽说SparseArray性能比较好,但是由于其添加、查找、删除数据都需要先进行一次二分查找,所以在数据量大的情况下性能并不明显,将降低至少50%。满足下面两个条件我们可以使用SparseArray代替HashMap:

a:数据量不大,最好在千级以内,如果在数据量比较大时,它的性能将退化至少50%。
b:key必须为int类型,这中情况下的HashMap可以用SparseArray代替。