美文网首页Android进阶之路Android开发Android开发经验谈
内存优化之ArrayMap、SparseArray、Sparse

内存优化之ArrayMap、SparseArray、Sparse

作者: 木木玩Android | 来源:发表于2020-08-31 16:53 被阅读0次

    原文链接:https://juejin.im/post/6865980083388186637

    1、前言

    这几个数据结构呢,都是Android这家伙搞出来;为啥呢,打的旗号是节约内存,系统的很多地方都有他们的身影;为了追随google的脚步,也为了扩展自己对于数据结构的理解,我们有必要学习它;

    这里先大致说下,ArrayMap是一个map,是为了解决HashMap存储数据浪费空间情况;SparseArray是数组,为稀疏数据准备的;SparseXXXArray,也是数组,也为稀疏数据准备,xxx是基本数据类型,这样使用时不存在自动拆装箱操作(就是基本类型和相对应类之间的自动转换);SparseXXXArray的原理实现一致,这里只介绍SparseIntArray

    2、存储结构

    ArrayMap结构

    两个数组来存储;key的hash数据,key-value组成的数组;通过index来映射,2倍位置为key, 2倍位置+1 为value;mHashes数据,是从小到大有序存储的

    SparseArray结构

    也是两个数组,存储数组索引的key,存储数据value,通过相等索引来映射;mKeys是从小到大有序存储的

    从图来看,我觉得是结构思想整体是一致的;但他们的实现思路还是存在不同的地方

    3、ArrayMap特点

    3.1 hash计算

    这里key是可以为null,null是hash值为0,不为空时,其计算方式与下面变量有关,这个可以仅可以在构造器中设置,默认为false

        final boolean mIdentityHashCode;
    复制代码
    

    计算区别如下:

        mIdentityHashCode ? System.identityHashCode(key) : key.hashCode()
    复制代码
    

    由于是以hash来排序,如果使用默认,那么我们的hashCode方法,要是每个对象固定,最好且是不同的

    3.2 容器大小

    我们有必要先介绍以下,申请内存缓存机制,这涉及到下面两个数组,其原理是一样的,只是容量不同;

    static Object[] mBaseCache;
    static int mBaseCacheSize;
    
    static Object[] mTwiceBaseCache;
    static int mTwiceBaseCacheSize;
    
    private static final int CACHE_SIZE = 10;
    private static final int BASE_SIZE = 4; // 是以mHashes的大小来算的
    复制代码
    

    mBaseCache的容量大小为8, mTwiceBaseCache容量大小为16;两个缓存每种最多缓存10个;缓存结构如下图,入量按照8来绘制的:

    这里的容量是申请的数组容量,数据存储key-value,所以其能存储的数据个数为其一半;初始化、扩容都是根据存储个数来计算的

    初始化

    • 初始化容器大小小于0时,不允许申请内存,否则直接抛出异常
    • 大小为0时,赋值空数组
    • 大小为4个,优先从mBaseCache找有效数组
    • 大小为8,优先从mTwiceBaseCache找有效数组
    • 大于0时,或者缓存中没有时,直接申请,mHashes申请一倍大小,mArray申请两倍大小

    扩容

    调用下面两个方法时,可能会扩容

    public void ensureCapacity(int minimumCapacity)
    public V put(K key, V value)
    复制代码
    
    • put方法,容器中存储新数据时,数组已满;
    • ensureCapacity方法,容量小于minimumCapacity个

    数组的移动System.arraycopy方法处理,如果容器大小增加了,则废弃的数组;废弃的数组,进行回收,如果存储容量大小为4或者8,会放入缓存中

    3.3 索引查找

    查找可以插入或者替换数据的位置;查找思想:

    1\. 进行二分查找,先查找到一个hash相等的位置;
    2\. 根据查找的位置,若相等则返回查找位置
    3\. 依据hash值相等,往后查找,若key相等,则返回,hash不等则结束;这时位置跟随hash相等而向后移动
    4\. 依据hash值相等,往后查找,若key相等,则返回,hash不等则结束
    5\. 没有找到,返回前面四步处理后的位置,并取非操作,返回负数值
    复制代码
    

    查找位置为正整数,说明此处有数据,可替换,负整数,表示无数据且取非表示可插入位置

    3.4 添加数据

    增加数据时,可能会扩容;如果数据未找到且容器存储个数已满,这时会进行扩容

     小于4时,扩容到4个;小于8个,扩容到8个;大于等于8时,进行1.5倍扩容
    复制代码
    

    3.5 删除数据

    删除数据时,可能会进行容量缩减

    1. 如果数组现有数据个数为1,删除后,数组置为空数组;原数组容量大小为4或者8,则被放入缓存

    2. 如果数据容量大小大于8个,且存储数据个数小于容量的1/3,则容量大小需要重新计算

      1. 已有数据个数小于8时,新容量大小为8
      2. 大于等于8时,新容量大小为现有数据个数的1.5倍

    4、SparseIntArray

    如果你上面ArrayMap已经懂了,那么SparseIntArray其实已经很简单了;它存在下面的差异

    1. list集合
    2. 没有缓存机制
    3. 扩容大小不同;如果小于等于4,变为8,否则2倍扩容
    4. 排序以key排序,数据只存储int类型的value值,key为稀疏数组的索引;ArrayMap,是以key的hash排序,数据数组为key-value交替存储
    5. 位置查找时,直接进行二分查找,找到即为插入位置
    6. 删除数据时,对容量大小不做处理

    5、SparseArray

    SparseArray和SparseXXXArray那就更接近了;不过我们还是和ArrayMap做对比吧

    1. list集合
    2. 没有缓存机制
    3. 扩容大小不同;如果小于等于4,变为8,否则2倍扩容
    4. 排序以key排序,数据只存储Object类型的value值,key为稀疏数组的索引;ArrayMap,是以key的hash排序,数据数组为key-value交替存储
    5. 位置查找时,直接进行二分查找,找到即为插入位置
    6. 删除数据时,只是把value置为固定的一个删除标志值
    7. 增加数据时,如果存储数据已满且存在删除数据标志,则调用gc方法
    8. 如果在查找数据位置,获取数据大小,则都有可能调用gc方法

    和SparseXXXArray区别就是:无gc方法机制、存储value值是类而不是基本数据

    gc方法:如果有效数据前存在删除数据标志值DELETED,则后面把有效数据往前移位

    有没有小伙伴在想,为何SparseXXXArray,没有这种gc行为呢,因为基本类型,存什么都无法标志其是无效数据啊;

    技术变化都很快,但基础技术、理论知识永远都是那些;作者希望在余后的生活中,对常用技术点进行基础知识分享;如果你觉得文章写的不错,请给与关注和点赞;如果文章存在错误,也请多多指教!

    相关文章

      网友评论

        本文标题:内存优化之ArrayMap、SparseArray、Sparse

        本文链接:https://www.haomeiwen.com/subject/gkxpsktx.html