SparseArray源码解析

最近笔试WPS的时候遇到SparseArray，需要手写Put和Get的方法，那时候并没有看过它的源代码，之前在看《Android源码设计模式》中也看到SparseArray的介绍，说如果Key的值是整形，用SparseArray比HashMap要高效很多，竟然吃亏过了就不能再吃亏了，今天自己手撸了SparseArray的代码，为大家介绍下SparseArray源码。

ContainerHelpers类

1. ContainerHelpers类是一个工具类，其中里面的binSearch方法是二分查找(折半查找),通过Key值查询对应的位置。这个工具类就是SparseArray的效率比HashMap高的原因。
   代码如下:

   /** * @author 林思旭 * @since 2017/4/25 */ public class ContainerHelpers { final static int[] EMPTY_INTS = new int[0]; final static Object[] EMPTY_OBJECTS = new Object[0]; //二分查找 static int binSearch(int a[],int size,int key){ int low = 0; int high = size -1; while(low < high){ int middle = low + ((high - low)>>1); if(a[middle] > key){ high = middle - 1; }else if(a[middle] < key){ low = middle + 1; }else if(a[middle] == key){ return middle; } } return ~low;//在已有数据中找不到Key值，用low的取反值代替 } }

SparseArray类

SparseArray类的构造函数

1. SparseArray中有两种构造方法：其中一种是默认无参数的构造方法，另外一种是用户传递参数的构造方法。
   代码如下:

   //无参数的构造方法 public SparseArray() { this(10);//将默认容量值10传递给有参数的构造方法当中 } public SparseArray(int capacity) { if(capacity == 0){ mKeys = ContainerHelpers.EMPTY_INTS; mValues = ContainerHelpers.EMPTY_OBJECTS; }else { mKeys = new int[capacity]; mValues = new Object[capacity]; } mSize = 0;//已经储存的<key,value>的键值个数 }

SparseArray类的Put方法

1. Put方法也是先进行判断原来的数组中是否已经存在Key值，如果存在的话直接替换掉对应Key值下的Value;如果不存在就进行容量的判断和位置的插入。
   代码如下:

   /** * * @param key 键值 * @param value 内容 */ public void put(int key,Object value){ int i = ContainerHelpers.binSearch(mKeys,mSize,key);// if(i > 0){ mValues[i] = value;//储存对应的Key，覆盖对应的Value }else{ i = ~i;//再取一次反变成正值 if(i < mSize && mValues[i] == DELETED){ mKeys[i] = key; mValues[i] = value; return; } if(i < mSize && mSize >= mKeys.length){ //如果有元素被删除了，并且目前容量不足，进行一次GC整理删除操作 gc(); //再次查找Key位置所在，因为GC之后位置可能发生变化 i = ~ContainerHelpers.binSearch(mKeys,mSize,key); } if(mSize >= mKeys.length){ int n = mSize + 1; int nKeys[] = new int[n]; Object nValues[] = new Object[n]; //进行数组数据拷贝备份 System.arraycopy(mKeys,0,nKeys,0,mKeys.length); System.arraycopy(mValues,0,nValues,0,mValues.length); //扩展之后的数组将引用重新给回之前的数组 mKeys = nKeys; mValues = nValues; } //i为插入位置,如果i<mSize,则i之后的元素需要依次向后移动一位. if(mSize - i != 0){ System.arraycopy(mKeys,i,mKeys,i + 1,mSize - i); System.arraycopy(mValues,i,mValues,i + 1,mSize - i); } mKeys[i] = key; mValues[i] = value; mSize++; } }

其中System.arraycopy(A,B,C,D,E)里面的参数的意思如下解释:
A: 要复制的数组A(源数组)
B: 数组A从B位置开始进行复制
C: 复制到数组C中(目的数组)
D: 数组C从D位置开始赋值(int C[D] = int A[B])
E: 复制的长度

SparseArray类的Get方法

1. Get方法中用了重载机制，在get(int key)方法里面再调用get(key,null),这里的null是当获取不存在的时候的返回值。
   代码如下:

   /** * * @param key 键值 * @return 根据键值寻找Value值 */ public T get(int key){ return get(key,null); } public T get(int key,T valueIfKeyNotFound){ int i = ContainerHelpers.binSearch(mKeys,mSize,key); if( i < 0 || mValues[i] == DELETED){ //如果不存在这个数，或者已经被删除了 return valueIfKeyNotFound; }else{ return (T)mValues[i]; } }

SparseArray类的Remove方法

1. Remove方法里面调用的是delete方法,其中delete方法是通过折半查找,找到对应的index下标后,判断下标是否存在,如存在就将value设置成DELETED参数,再设置mGarbage为true,可以当容量不足时候进行gc()操作。
   代码如下:

   public void delete(int key){ //输入mSize可以控制查找的范围，避免不必要的查找 int i = ContainerHelpers.binSearch(mKeys,mSize,key); if(i >= 0){ if(mValues[i] != DELETED){ //把被删除位置的Value置为DETELE mValues[i] = DELETED; mGarbage = true;//设置gc为true，说明可以进行gc整理工作 } } } /** * 根据键值查找到需要删除的 Value * @param key 键值 */ public void remove(int key){ delete(key); }

SparseArray类的gc()方法

1. 这里的gc()方法不是JVM里面那种gc()操作，这里只是自行定义了一个数组移动的操作，将已经删除数据的数组i,将i+1后面的数组往前面移动。
   代码如下:

   private void gc() { int n = mSize; int o = 0; int[] keys = mKeys; Object[] values = mValues; for (int i = 0; i < n; i++) { Object val = values[i]; if (val != DELETED) { //如果不是已经删除的数据，统计mSize总数 if (i != o) { //如果不等于证明前面i为有被删除的数据，需要移动数组 keys[o] = keys[i];//将非DELETED资源全部移动到数组前面. values[o] = val;//将后面数组的value填进已经删除数据的数据的位置 values[i] = null; } o++; } //如果val == DELETED,o没有+1，因为这时候o的位置是已经被删除了数据，所以要把后面的数据往前面移动 } mGarbage = false;//整理完数组后恢复标记值为false mSize = o; }

SparseArray类的全部代码

/**
 * @author 林思旭
 * @since 2017/4/25
 */
public class SparseArray<T> implements Cloneable{
    private int mKeys[];//索引数组
    private Object mValues[];//储存对象的数组
    private int mSize;//储存的键值对总数
    private boolean mGarbage = false;
    private static final Object DELETED = new Object(); //自定需要被删除的
    public SparseArray() {
        this(10);
    }
    public SparseArray(int capacity) {
        if(capacity == 0){
            mKeys = ContainerHelpers.EMPTY_INTS;
            mValues = ContainerHelpers.EMPTY_OBJECTS;
        }else {
            mKeys = new int[capacity];
            mValues = new Object[capacity];
        }
        mSize = 0;//已经储存的<key,value>的键值个数
    }
    /**
     *
     * @param key 键值
     * @param value  内容
     */
    public void put(int key,Object value){
        int i = ContainerHelpers.binSearch(mKeys,mSize,key);//
        if(i > 0){
            mValues[i] = value;//储存对应的Key，覆盖对应的Value
        }else{
            i = ~i;//再取一次反变成正值
            if(i < mSize && mValues[i] == DELETED){
                mKeys[i] = key;
                mValues[i] = value;
                return;
            }
            if(i < mSize && mSize >= mKeys.length){
                //如果有元素被删除了，并且目前容量不足，进行一次GC整理删除操作
                gc();
                //再次查找Key位置所在，因为GC之后位置可能发生变化
                i = ~ContainerHelpers.binSearch(mKeys,mSize,key);
            }
            if(mSize >= mKeys.length){
                int n = mSize + 1;
                int nKeys[] = new int[n];
                Object nValues[] = new Object[n];
                //进行数组数据拷贝备份
                System.arraycopy(mKeys,0,nKeys,0,mKeys.length);
                System.arraycopy(mValues,0,nValues,0,mValues.length);
                //扩展之后的数组将引用重新给回之前的数组
                mKeys = nKeys;
                mValues = nValues;
            }
            //i为插入位置,如果i<mSize,则i之后的元素需要依次向后移动一位.
            if(mSize - i != 0){
                System.arraycopy(mKeys,i,mKeys,i + 1,mSize - i);
                System.arraycopy(mValues,i,mValues,i + 1,mSize - i);
            }
            mKeys[i] = key;
            mValues[i] = value;
            mSize++;
        }
    }
    /**
     *
     * @param key 键值
     * @return 根据键值寻找Value值
     */
    public T get(int key){
        return get(key,null);
    }
    public T get(int key,T valueIfKeyNotFound){
        int i = ContainerHelpers.binSearch(mKeys,mSize,key);
        if( i < 0 || mValues[i] == DELETED){ //如果不存在这个数，或者已经被删除了
            return valueIfKeyNotFound;
        }else{
            return (T)mValues[i];
        }
    }
    public void delete(int key){
        //输入mSize可以控制查找的范围，避免不必要的查找
        int i = ContainerHelpers.binSearch(mKeys,mSize,key);
        if(i >= 0){
            if(mValues[i] != DELETED){
                //把被删除位置的Value置为DETELE
                mValues[i] = DELETED;
                mGarbage = true;//设置gc为true，说明可以进行gc整理工作
            }
        }
    }
    /**
     * 根据键值查找到需要删除的 Value
     * @param key 键值
     */
    public void remove(int key){
        delete(key);
    }
    private void gc() {
        int n = mSize;
        int o = 0;
        int[] keys = mKeys;
        Object[] values = mValues;
        for (int i = 0; i < n; i++) {
            Object val = values[i];
            if (val != DELETED) { //如果不是已经删除的数据，统计mSize总数
                if (i != o) { //如果不等于证明前面i为有被删除的数据，需要移动数组
                    keys[o] = keys[i];//将非DELETED资源全部移动到数组前面.
                    values[o] = val;//将后面数组的value填进已经删除数据的数据的位置
                    values[i] = null;
                }
                o++;
            }
    //如果val == DELETED,o没有+1，因为这时候o的位置是已经被删除了数据，所以要把后面的数据往前面移动
        }
        mGarbage = false;
        mSize = o;
    }
}

如果Key是其他类型咋办

如果key类型为其它的类型，则使用ArrayMap

• ← Previous Post
• Next Post →