内存优化(使用SparseArray和ArrayMap代替HashMap)

HashMap

关于HashMap的知识请看这篇 优秀文章:http://tryenough.com/java-hashmap


SparseArray

SparseArray 的使用

创建

SparseArray有两个构造方法,一个默认构造方法,一个传入容量。

SparseArray sparseArray = new SparseArray<>();
SparseArray sparseArray = new SparseArray<>(capacity);

首先来看看如何创建一个SparseArray,而SparseArray只需要指定一个泛型表示value类型,而key的类型在SparseArray内部已经指定了为int类型

put()

看看怎么往里面存放数据吧

sparseArray.put(int key,Student value);

put()就跟HashMap的使用方法一样。

get()

sparseArray.get(int key);
sparseArray.get(int key,Student valueIfNotFound);

SparseArray 实现原理

简介:

用int[]数组存放key,避免了HashMap中基本数据类型需要装箱的步骤,其次不使用额外的结构体(Entry),单个元素的存储成本下降。

要理解SparseArray 的实现原理,需要看代码:

SparseArray用两个数组来存放key和value:

    private int[] mKeys; 
    private Object[] mValues;

key的存放按照从小到大的顺序,这样就能保证使用二分查找,而SparseArray内部查找数据也就是使用的二分查找,这样查找的效率比较高。我们来看下put方法,就能大概理解SparseArray的原理了:

//参数是传进来的 int类型的key 和 范形的value 
public void put(int key, E value) {
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);  //使用二分查找寻找key应该在的位置,具体实现请先看下面的讲解

        if (i >= 0) {
            mValues[i] = value;  //如果寻找到lo就直接覆盖value
        } else {
            i = ~i;

            if (i < mSize && mValues[i] == DELETED) { //如果没有找到,并且返回的数组索引对应的值是DELETED那就直接覆盖value
                mKeys[i] = key;
                mValues[i] = value;
                return;
            }

            if (mGarbage && mSize >= mKeys.length) { //如果当前数组已满,检查数组中是否有DELETED的值,然后将其删除gc的操作:可查看下面具体源码
                gc();

                // Search again because indices may have changed.
                i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
            }
            //最后将数据插入到正确的位置
            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key); 
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
            mSize++;
        }
    }

二分查找

//这里传递过来的value是上面的key
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 找到,直接返回key的索引
            }
        }
        return ~lo;  // 没有找到就直接返回最终lo的取反值,此时的lo值就正好是排好序的lo
    }

gc:

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];

            if (val != DELETED) {
                if (i != o) {
                    keys[o] = keys[i];
                    values[o] = val;
                    values[i] = null;
                }

                o++;
            }
        }

        mGarbage = false;
        mSize = o;

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

总结:
SparseArray的优点:

避免了基本数据类型的装箱操作
不需要额外的结构体,单个元素的存储成本更低
数据量小的情况下,随机访问的效率更高

SparseArray的缺点:

插入操作需要复制数组,增删效率降低
数据量巨大时,复制数组成本巨大,gc()成本也巨大
数据量巨大时,查询效率也会明显下降


ArrayMap的原理

ArrayMap是一个<key,value>映射的数据结构,它设计上更多的是考虑内存的优化,内部是使用两个数组进行数据存储,一个数组记录key的hash值,另外一个数组记录Value值,它和SparseArray一样,也会对key使用二分法进行从小到大排序,在添加、删除、查找数据的时候都是先使用二分查找法得到相应的index,然后通过index来进行添加、查找、删除等操作,所以,应用场景和SparseArray的一样,如果在数据量比较大的情况下,那么它的性能将退化至少50%。


总结:

假设数据量都在千级以内的情况下:

1、如果key的类型已经确定为int类型,那么使用SparseArray,因为它避免了自动装箱的过程,如果key为long类型,它还提供了一个LongSparseArray来确保key为long类型时的使用

2、如果key类型为其它的类型,则使用ArrayMap

发表评论

关闭菜单