Android内存优化之使用SparseArray和ArrayMap代替HashMap_sparsearray转hashmap

•在Android开发时，我们使用的大部分都是Java的api，比如HashMap这个api，使用率非常高，但是对于Android这种对内存非常敏感的移动平台，很多时候使用一些java的api并不能达到更好的性能，相反反而更消耗内存，所以针对Android这种移动平台，也推出了更符合自己的api，比如SparseArray、ArrayMap用来代替HashMap在有些情况下能带来更好的性能提升。

 

HashMap

•HashMap内部是使用一个默认容量为16的数组来存储数据的，而数组中每一个元素却又是一个链表的头结点

•且每一个结点都是Entry类型，HashMap中Entry的属性

 

final K key;

 V value; final int hash;

 HashMapEntry<K, V> next;

Entry数据存储规则 hash(key)%len

 

比如：假设hash(14)=14,hash(30)=30,hash(46)=46

hash(14)%16=14，hash(30)%16=14，我们分别对len取余，得到hash(46)%16=14，所以key为14、30、46的这三个元素存储在数组下标为14的位置

•int newCapacity = oldCapacity * 2;

 

SparseArray

 

•SparseArray比HashMap更省内存，在某些条件下性能更好，主要是因为它避免了对key的自动装箱（int转为Integer类型），它内部则是通过两个数组来进行数据存储的，一个存储key，另外一个存储value，为了优化性能，它内部对数据还采取了压缩的方式来表示稀疏数组的数据，从而节约内存空间，我们从源码中可以看到key和value分别是用数组表示：

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

•SparseArray是单纯数组的结合.被称为稀疏数组,对数据保存的时候,不会有额外的开销.结构如下：

 

•SparseArray只能存储key为int类型的数据，同时，SparseArray在存储和读取数据时候，使用的是二分查找法

 public void put(int key, E value) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key); ... } public E get(int key, E valueIfKeyNotFound) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key); ... }

也就是在put添加数据的时候，会使用二分查找法和之前的key比较当前我们添加的元素的key的大小，然后按照从小到大的顺序排列好，所以，SparseArray存储的元素都是按元素的key值从小到大排列好的。

•添加数据

 public void put(int key, E value)

删除数据

Public void remove(int key)

Public void delete(int key)

获取数据

public E get(int key)

•SparseArray还提供了两个特有方法，更方便数据的查询：
获取对应的key：

    public int keyAt(int index)

     获取对应的value：

      public E valueAt(int index)

 

 

 

SparseArray应用场景

 

虽说SparseArray性能比较好，但是由于其添加、查找、删除数据都需要先进行一次二分查找，所以在数据量大的情况下性能并不明显，将降低至少50%。

满足下面两个条件我们可以使用SparseArray代替HashMap：

数据量不大，最好在千级以内

key必须为int类型，这中情况下的HashMap可以用SparseArray代替

 

ArrayMap

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

//如果容量不够
size >= mHashes.length) {
    final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
            : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
  
    if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n);
  
    final int[] ohashes = mHashes;
    final Object[] oarray = mArray;
//分配数组
    allocArrays(n);
  
    if (mHashes.length > 0) {
        if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0");
        //特别注意这，是copy，而不是new，效率提升
        System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
        System.arraycopy(oarray, 0, mArray, 0, oarray.length);
    }
        //释放无用空间，收缩数组
    freeArrays(ohashes, oarray, mSize);
}

ArrayMap用的是copy数据，所以效率相对要高。

 

•SparseArray和ArrayMap都差不多，使用哪个呢？
假设数据量都在千级以内的情况下：

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

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