专栏首页振兴的Android修炼手册Android性能优化之SparseArray源码分析

Android性能优化之SparseArray源码分析

前言

迟到一年的HashMap解读 文章中讲述了常用Java编程的数据结合HashMap的一些知识点。但如果在Android编程中出现HashMap<Interget, Object>的时候,编译器就会提示用SparseArray代替HashMap。为什么呢?众所周知在Android手机中应用的内存占比是衡量一个APP新能的非常重要的指标。而SparseArray就是通过时间换空间的办法降低HashMap的内存占用。

  • HashMap是通过数据加链表的方式存储数据的;
  • SparseArray是使用纯数据的方式实现对数据的存储的;

SparseArray主要是通过将Interger类型的key,以升序方式存储在mKeys中,无论在插入或是查找的时候都可以使用二分查找法进行index的查找,当然其中还有一些细节方面的优化。

SparseArray的构造

//删除了的数据
private static final Object DELETED = new Object();
//是否进行过删除
private boolean mGarbage = false;

private int[] mKeys;
private Object[] mValues;
//数组中创建的对象(实际存在的数据个数和DELETED个数)
private int mSize;

public SparseArray() {
    this(10);
}
public SparseArray(int initialCapacity) {
    if (initialCapacity == 0) {
        mKeys = ContainerHelpers.EMPTY_INTS;
        mValues = ContainerHelpers.EMPTY_OBJECTS;
    } else {
        initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity);
        mKeys = new int[initialCapacity];
        mValues = new Object[initialCapacity];
    }
    mSize = 0;
}

SparseArray的put方法

public void put(int key, E value) {
    //找到key在mKeys中的索引位置
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    //index>0,表示已经存在,value直接覆盖
    if (i >= 0) {
        mValues[i] = value;
    } else {
        //index的反码载取反,表示key应该存在的索引位置
        i = ~i;
        //索引位置在已经被删除了的位置,直接复制key,value
        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }
        //mGarbage=true,表示有删除元素。且数组容量已经满了,触发gc:回收数组中为DELETED的节点,向前补位
        //eg:{1,4,0,5,6,0,7} => {1,4,5,6,7,null,null}
        if (mGarbage && mSize >= mKeys.length) {
            gc();
            //重新进行索引
            // Search again because indices may have changed.
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }
        //数组容量已满(没有触发gc),进行扩容。
        if (mSize >= mKeys.length) {
            //计算将要扩容的数组长度,n为2的指数幂且n >= (mSize + 1)
            int n = ArrayUtils.idealIntArraySize(mSize + 1);
            //创建新的数组
            int[] nkeys = new int[n];
            Object[] nvalues = new Object[n];
            //将原来数组的内容,copy到新的数组
            // Log.e("SparseArray", "grow " + mKeys.length + " to " + n);
            System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
            System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
            //替换引用
            mKeys = nkeys;
            mValues = nvalues;
        }
        //重新排序,保持数组的升序特性
        if (mSize - i != 0) {
            // Log.e("SparseArray", "move " + (mSize - i));
            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++;
    }
}

SparseArray中index查找

class ContainerHelpers {
    static final int[] EMPTY_INTS = new int[0];
    /********************部分代码省略******************/
    //使用二分查找发查找当前value在数组中的索引位置,找到返回该位置,找不到返回value应该处于的位置的反码
    // This is Arrays.binarySearch(), but doesn't do any argument validation.
    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;
            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
    }
    /********************部分代码省略******************/
}

SparseArray中数据扩容

//实现数组的内容复制
public static void arraycopy(int[] src,    //src:源数组;
                                int srcPos,    //srcPos:源数组要复制的起始位置;
                                int[] dst,   //dst:目的数组;
                                int dstPos,   //dstPos:目的数组放置的起始位置;
                                int length) {    //length:复制的长度。
    if (src == null) {
        throw new NullPointerException("src == null");
    }
    if (dst == null) {
        throw new NullPointerException("dst == null");
    }
    if (srcPos < 0 || dstPos < 0 || length < 0 ||
            srcPos > src.length - length || dstPos > dst.length - length) {
        throw new ArrayIndexOutOfBoundsException(
                "src.length=" + src.length + " scrPos=" + srcPos +
                        " dst.length=" + dst.length + " desPos=" + dstPos + " length=" + length);
    }
    if (length <= ARRAYCOPY_SHORT_INT_ARRAY_SHRESHOLD) {
        if (src == dst && srcPos < dstPos && dstPos < srcPos + length) {
            for (int i = length - 1; i >=  0; --i) {
                dst[dstPos + i] = src[srcPos + i];
            }
        } else {
            for (int i = 0; i < length; ++i) {
                dst[dstPos + i] = src[srcPos + i];
            }
        }
    } else {
        arraycopyIntUnchcked(src, srcPos, dst, dstPos, length);
    }
}
//result = (2^n - 3) >= need
public static int idealIntArraySize(int need) {
    return idealByteArraySize(need * 4) / 4;
}
public static int idealByteArraySize(int need) {
    for (int i = 4; i < 32; i++) {
        if (need <= (1 << i) - 12) 
            return (1 << i) - 12;
    }
    return need;
}

SparseArray内部GC

//回收数组mValues中的DELETED数据
private void gc() {
    // Log.e("SparseArray", "gc start with " + mSize);

    int n = mSize;
    int o = 0;
    int[] keys = mKeys;
    Object[] values = mValues;

    for (int i = 0; i < n; i++) {
        Object val = values[i];
        //将数据中的DELETED数据全部剔除,但是依旧保持数据的升序特性
        if (val != DELETED) {
            if (i != o) {
                keys[o] = keys[i];
                values[o] = val;
                values[i] = null;
            }

            o++;
        }
    }
    //重置mGarbage标志
    mGarbage = false;
    //mSize恢复数组中的数据真实数量
    mSize = o;

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

SparseArray的get

public E get(int key) {
    return get(key, null);
}

@SuppressWarnings("unchecked")
public E get(int key, E valueIfKeyNotFound) {
    ////找到key在mKeys中的索引位置
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    //找不到或者索引处的value=DELETE,则返回默认值
    if (i < 0 || mValues[i] == DELETED) {
        return valueIfKeyNotFound;
    } else {
        return (E) mValues[i];
    }
}

SparseArray的优化

想要在数据中存放一个key-value键值对,当这个key值比当前数组中的任何一个key值都大的时候,那么使用这个方法更优。

/**
 * Puts a key/value pair into the array, optimizing for the case where
 * the key is greater than all existing keys in the array.
 */
public void append(int key, E value) {
    //因为数据的key是升序存放的,所以只需要比较最后一个key值就可以。
    //如果比最后一个key值都大,那么该key值存储的index=mSize。
    //否则,调用put方法
    if (mSize != 0 && key <= mKeys[mSize - 1]) {
        put(key, value);
        return;
    }

    if (mGarbage && mSize >= mKeys.length) {
        gc();
    }

    int pos = mSize;
    if (pos >= mKeys.length) {
        int n = ArrayUtils.idealIntArraySize(pos + 1);

        int[] nkeys = new int[n];
        Object[] nvalues = new Object[n];

        // Log.e("SparseArray", "grow " + mKeys.length + " to " + n);
        System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
        System.arraycopy(mValues, 0, nvalues, 0, mValues.length);

        mKeys = nkeys;
        mValues = nvalues;
    }

    mKeys[pos] = key;
    mValues[pos] = value;
    mSize = pos + 1;
}

在网络上看到一些对HashMap和SparseArray内存的分析来看,数据量在100000条时SparseArray要比HashMap要节约27%的内存,因此官方才推荐去使用SparseArray<E>去替换HashMap<Integer,E>.官方也确实声明这种差异性不会超过50%.所以牺牲了部分效率换来内存其实在Android中也算是一种很好的选择。

看完整篇文章是不是迫不及待的就像使用SparseArray呢!!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 如何合理地估算线程池大小?

    制定线程池的长度并不是一门精密的科学,需要做的仅仅是避免“过大”和“过小”者两个极端情况。如果一个线程池过大,那么线程对稀缺的CPU和内存资源的竞争,会导致内存...

    静默加载
  • Java并发编程之线程池必用知识点

    再使用线程池之前,我们应该了解为什么需要使用线程池。进行执行任务(task)的时候我们一般情况是new Thread进行执行,如果进行大量的并发任务的时候呢?

    静默加载
  • Ubuntu 14.04下Django&MySQL环境部署

    目前Django的版本已经到1.11了。先去官网下载Linux对应的文件,然后解压&安装。(官网下载地址)

    静默加载
  • [享学Netflix] 十八、Hystrix配置之:全局配置和实例配置

    上篇文章介绍了Hystrix和Archaius的整合,对深入了解Hystrix内部的属性配置打好了基础。对于属性配置,程序员们的感受可能是可能既爱又恨,因为那些...

    YourBatman
  • Python 获得命令行参数的方法

    如果想对python脚本传参数,python中对应的argc, argv(c语言的命令行参数)是什么呢? 需要模块:sys 参数个数:len(sys.ar...

    py3study
  • 各种平衡树

    记一下自己写的平衡树 方便以后复制粘贴 题目链接 Vector 最快:284ms 1 #include<cstdio> 2 #include<vector>...

    attack
  • iOS面试题-ARC下如何创建栈上的Block

    这题主要是考察如何区分栈,堆,还是全局? 其中栈上block的定义:只用到外部局部变量、成员属性变量,且没有强指针引用的block都是StackBlock。 ...

    大壮
  • 多益网络2016春季实习校招笔试回顾(C++游戏后台开发)

    2016.04.16晚中山大学大学城校区(东校区)参加了多益网络的C++游戏后台开发的笔试。有几道笔试题还是值得斟酌和记录的,特记录如下。比较可惜,因为回老家了...

    Dabelv
  • 数据结构概述、指针与内存

      我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器(内存)中,以及在此基础上为实现某个功能(比如查找某个元素,删除某个元素,对所...

    爱学习的孙小白
  • 20:反反复复

    20:反反复复 总时间限制: 1000ms 内存限制: 65536kB描述 Mo和Larry发明了一种信息加密方法。他们首先决定好列数,然后将信息(只包含字...

    attack

扫码关注云+社区

领取腾讯云代金券