Android性能优化之SparseArray源码分析

静默加载

发布于 2020-05-29 10:23:20

5670

发布于 2020-05-29 10:23:20

前言

迟到一年的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呢！！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

hashmap