Android中的SparseArray源码解析

Android中的SparseArray源码解析

一、概述

在Android平台中,更推荐使用SparseArray<E>来替代HashMap的数据结构,更具体的说,是用于替代keyint类型,valueObject类型的HashMap; 用于替代HashMap<Integer, Object>

二、SparseArray的特点

  • ArrayMap类似,它的实现相比HashMap更加节省内存空间,而且因为指定了keyint类型,可以避免int->Integer装箱拆箱带来的性能消耗

  • 仅仅实现了Cloneable接口,所以使用时不能使用Map类型,它不是一个Map,它也是线程不安全的,允许value为null

  • 它内部实现基于两个数组: 一个是int[]类型的数组mKeys,用于保存每个Item的key,key本身就是int类型,所以可以理解为hashCode的值就是key的值; 另一个是Object[]类型的数组mValues,用于保存value,数组容量大小与mKeys数组一致

  • 类似于ArrayMap,但是SparseArray相比它的扩容更为简单,扩容时只需要数组拷贝工作,不需要重建哈希表,同样它不适合大容量的数据存储。存储大容量数据性能会下降50%。

  • 相比传统HashMap时间效率更低,一般HashMap基于哈希表,时间复杂度近似于O(1), 而SparseArray则会对它的key进行从小到大排序,然后使用二分查找查询key对应在数组中的下标,在添加、删除、查找数据的时候都是先使用二分查找法得到相应的index,然后通过index来进行添加、查找、删除等操作。所以SparseArray时间复杂度是O(logn),相对于O(1)的HashMap效率比较低。那么它的key就是按照从小到大升序存储的。

  • SparseArray为了提升性能,在删除操作时做了一些优化
    当删除一个元素时,并不是立即从value数组中删除它,并压缩数组,
    而是将其在value数组中标记为已删除。这样当存储相同的keyvalue时,可以重用这个空间
    如果该空间没有被重用,随后将在合适的时机里执行gc(垃圾收集)操作,将数组压缩,以免浪费空间

三、SparseArray的适用场景

  • 数据量不大

  • 内存空间比时间效率更重要

  • 需要使用Mapkey的类型是int类型

四、SparseArray的基本使用

 private void test() {
        SparseArray<String> stringSparseArray = new SparseArray<>();
        stringSparseArray.put(1, "a");
        stringSparseArray.put(5, "c");
        stringSparseArray.put(4, "e");
        stringSparseArray.put(6, null);
        Log.d(TAG, "onCreate() called with: stringSparseArray = [" + stringSparseArray + "]");
 }

输出结果:

//可以看出是按照key的升序排序的
onCreate() called with: stringSparseArray = [{1=a, 4=e, 5=c, 6=null}]

五、SparseArray的源码解析

1、构造器

    //用于标记value数组,作为已经删除的标记
    private static final Object DELETED = new Object();
    //用于表示是否需要GC,这里的GC是指整理压缩数组中无效需要删除标记元素
    private boolean mGarbage = false;

    //存储key的数组    
    private int[] mKeys;
    //存储value的数组
    private Object[] mValues;
    //集合大小
    private int mSize;

    //默认构造函数,初始化容量为10
    public SparseArray() {
        this(10);
    }

    //指定初始化容量
    public SparseArray(int initialCapacity) {

        //初始容量为0的话,就赋值两个轻量级的引用
        if (initialCapacity == 0) {
            mKeys = EmptyArray.INT;
            mValues = EmptyArray.OBJECT;
        } else {
        //否则初始化对应容量大小的int[]数组mKeys和Object[]数组mValues
            mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
            mKeys = new int[mValues.length];
        }
        //mSize用于统计集合大小,默认初始为0
        mSize = 0;
    }

2、集合的增加、修改

1、单个元素的增加和修改put(key, value)
   public void put(int key, E value) {
        //利用ContainerHelpers的binarySearch进行二分查找,找到待插入key的下标index
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        //如果i下标大于0,说明之前这个key已经存在
        if (i >= 0) {
            mValues[i] = value;//直接覆盖key对应的value即可
        } else {
        //如果i下标小于0,说明mKeys中不存在key,所以这个key是第一次插入
            i = ~i;//先对返回的i取反,得到应该插入的位置i
            //如果i没有越界,且对应位置是已删除的标记,则复用这个空间
            if (i < mSize && mValues[i] == DELETED) {
                //赋值key和value后,返回
                mKeys[i] = key;
                mValues[i] = value;
                return;
            }

            //如果需要GC,且集合mSize大于mKeys的长度(需要扩容)
            if (mGarbage && mSize >= mKeys.length) {
                gc();//先触发GC
                //gc后,下标i可能发生变化,所以再次用二分查找找到应该插入的位置i
                i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
            }

            //插入key(可能需要扩容) 
            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
            //插入value(可能需要扩容)
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
            //集合大小递增
            mSize++;
        }
    }

//ContainerHelpers.binarySearch,标准二分查找的算法
    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;//防止int溢出,采用位运算
            final int midVal = array[mid];

            if (midVal < value) {
                lo = mid + 1;
            } else if (midVal > value) {
                hi = mid - 1;
            } else {
                return mid;  //找到对应key
            }
        }
        return ~lo;  // 若没有找到,则low是value应该插入的位置,是一个正数。对这个正数去反,返回负数回去
    }

//gc,垃圾回收函数,压缩数组
  private void gc() {

        int n = mSize;//保存GC前的集合大小
        int o = 0;//既是下标index,又是GC后的集合大小
        int[] keys = mKeys;
        Object[] values = mValues;
       //遍历values集合,以下算法意义为 从values数组中,删除所有值为DELETED的元素
        for (int i = 0; i < n; i++) {
            Object val = values[i];
            if (val != DELETED) {
                if (i != o) {
                    keys[o] = keys[i];
                    values[o] = val;
                    values[i] = null;
                }
                //递增o,那么它就是gc后的集合大小
                o++;
            }
        }

        mGarbage = false;//GC过后,修改标识,不需要GC
        mSize = o;//更新gc后的集合大小

        // Log.e("SparseArray", "gc end with " + mSize);
    }

GrowingArrayUtils.insert:插入

public static int[] insert(int[] array, int currentSize, int index, int element) {
        //断言 确认 当前集合长度 小于等于 array数组长度
        assert currentSize <= array.length;
        //如果不需要扩容,当前集合大小+1不超过数组容量就不需要扩容
        if (currentSize + 1 <= array.length) {
            //将array数组内元素,从index开始 后移一位
            System.arraycopy(array, index, array, index + 1, currentSize - index);
            //在index处赋值
            array[index] = element;
            //返回
            return array;
        }
        //需要扩容
        //构建新的数组
        int[] newArray = new int[growSize(currentSize)];
        //将原数组中index之前的数据复制到新数组中
        System.arraycopy(array, 0, newArray, 0, index);
        //在index处赋值
        newArray[index] = element;
        //将原数组中index及其之后的数据赋值到新数组中
        System.arraycopy(array, index, newArray, index + 1, array.length - index);
        //返回
        return newArray;
    }

    //根据现在的size 返回合适的扩容后的容量
    public static int growSize(int currentSize) {
        //如果当前size 小于等于4,则返回8, 否则返回当前size的两倍
        return currentSize <= 4 ? 8 : currentSize * 2;
    }
  • 二分查找,若未找到返回下标时,与JDK里的实现不同,JDK是返回return -(low + 1); // key not found.,而这里是对 低位去反 返回。这样在函数调用处,根据返回值的正负,可以判断是否找到index。对负index取反,即可得到应该插入的位置

  • 扩容时,当前容量小于等于4,则扩容后容量为8.否则为当前集合长度的两倍。和ArrayList,ArrayMap不同(扩容一半),和Vector相同(扩容一倍)。

  • 扩容操作依然是用数组的复制、覆盖完成。类似ArrayList.

3、集合的删除

1、按key删除
  public void remove(int key) {
        delete(key);//内部调用delete方法来删除
  }

  public void delete(int key) {
        //二分查找得到要删除的key所在的index 
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        //若i >= 0 表示对应key的index存在
        if (i >= 0) {
            //将对应index位置的value置为标志DELETED 
            if (mValues[i] != DELETED) {
                mValues[i] = DELETED;//value置为标志DELETED
                //并修改需要GC的标识为true,表示稍后需要GC
                mGarbage = true;
            }
        }
  }
2、按index删除(其实就省去二分查找的过程)
  public void removeAt(int index) {
        //直接索引到对应的value,将它置为标志DELETED
        if (mValues[index] != DELETED) {
            mValues[index] = DELETED;
            //并修改需要GC的标识为true,表示稍后需要GC
            mGarbage = true;
        }
  }
3、批量删除
    public void removeAtRange(int index, int size) {
        final int end = Math.min(mSize, index + size);
        for (int i = index; i < end; i++) {//循环对单个元素按照index删除
            removeAt(i);
        }
    }

4、集合的查找

1、按key进行查询
//按照key查询,如果key不存在,返回null
    public E get(int key) {
        return get(key, null);
    }

    //按照key查询,如果key不存在,返回valueIfKeyNotFound
    public E get(int key, E valueIfKeyNotFound) {
        //二分查找到 key 所在的index
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        //不存在
        if (i < 0 || mValues[i] == DELETED) {//如果i下标小于0或者找到i对应的value是一个DELETED已删除状态,就返回value为空的默认值
            return valueIfKeyNotFound;
        } else {//存在就直接返回mValue数组对应i下标的值
            return (E) mValues[i];
        }
    }
2、按index进行查询
 public int keyAt(int index) {
    //按照下标查询时,需要考虑是否先GC
        if (mGarbage) {
            gc();
        }

        return mKeys[index];
    }

    public E valueAt(int index) {
     //按照下标查询时,需要考虑是否先GC
        if (mGarbage) {
            gc();
        }

        return (E) mValues[index];
    }
3、查询对应的index
  public int indexOfKey(int key) {
     //查询下标时,也需要考虑是否先GC
        if (mGarbage) {
            gc();
        }
        //二分查找返回 对应的下标 ,可能是负数
        return ContainerHelpers.binarySearch(mKeys, mSize, key);
    }

    public int indexOfValue(E value) {
     //查询下标时,也需要考虑是否先GC
        if (mGarbage) {
            gc();
        }
        //不像key一样使用的二分查找。是直接线性遍历去比较,而且不像其他集合类使用equals比较,这里直接使用的 ==
        //如果有多个key 对应同一个value,则这里只会返回一个更靠前的index
        for (int i = 0; i < mSize; i++)
            if (mValues[i] == value)
                return i;

        return -1;
    }
  • 按照value查询下标时,不像key一样使用的二分查找。是直接线性遍历去比较,而且不像其他集合类使用equals比较,这里直接使用的 ==
  • 如果有多个key 对应同一个value,则这里只会返回一个第一个相等value的index

六、总结

Android sdk中,还提供了三个类似思想的集合:

  • SparseBooleanArray,value为boolean
  • SparseIntArray,value为int
  • SparseLongArray,value为long

他们和SparseArray唯一的区别在于value的类型,SparseArray的value可以是任意类型。而它们是三个常使用的拆箱后的基本类型。


   转载规则


《Android中的SparseArray源码解析》 mikyou 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
Android中的ArrayMap源码解析 - Android - 面试 - 框架源码解析 Android中的ArrayMap源码解析 - Android - 面试 - 框架源码解析
Android中的ArrayMap源码解析一、概述ArrayMap实现Map<K,V>接口,所以它也是一个关联数组和哈希表。存储是key-value结构形式的数据。所以它也是线程不安全,可以允许key,value都为null.
2019-12-29
下一篇 
Android中线程Thread源码解析 Android中线程Thread源码解析
Android中线程Thread源码解析一、Thread的介绍 Thread线程是进程中的独立运行的子任务。线程是CPU调度的最基本的单元,线程资源开销相对于进程而言比较小,所以我们一般是创建线程来执行任务。 1、Thread继承关系 T
2019-12-29