安卓性能优化—使用ArrayMap与SparseArray

性能优化是我们做开发的必须要熟练掌握的技能，所以我打算写一个性能优化专题，把平时用到的一些优化方法记录下来，以便忘记的时候可以快速查找，同时也给给其他开发者提供微薄之力吧：

这篇文章讲述的是在一些特定的场景使用使用ArrayMap与SparseArray代替HashMap,提高对数据的操作；
先看看官方文档的描述：

ArrayMap is a generic key->value mapping data structure that is designed to be more memory efficient than a traditional HashMap, this implementation is a version of the platform's ArrayMap that can be used on older versions of the platform.
 
SparseArrays map integers to Objects. Unlike a normal array of Objects, there can be gaps in the indices. It is intended to be more memory efficient than using a HashMap to map Integers to Objects, both because it avoids auto-boxing keys and its data structure doesn't rely on an extra entry object for each mapping.
 
Note that for containers holding up to hundreds of items, the performance difference is not significant, less than 50%.

• 1

从官方文档可以看出使用ArrayMap与SparseArray都要比传统的HashMap 更有效率；但是最后有一个note，也就是当数据量达到千级以上的时候，ArrayMap与SparseArray都要比传统的HashMap 效率更低50%；

HashMap
HashMap允许使用 null 值和 null 键，是基于hashing原理，我们通过put()和get()方法储存和获取对象。
HashMap的结构：

HashMap 有两个参数影响其性能：初始容量 和加载因子。容量是哈希表中桶的数量（默认16组），初始容量只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。加载因子默认值为0.75 。
当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，让后找到bucket位置来储存值对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用LinkedList来解决碰撞问题，当发生碰撞了，对象将会储存在LinkedList的下一个节点中。 HashMap在每个LinkedList节点中储存键值对对象。
put()方法

 @Override public V put(K key, V value) {
        if (key == null) {//允许空值
            return putValueForNullKey(value);
        }
        //使得hash过后的值的分布更加均匀，尽可能地避免冲突
        int hash = Collections.secondaryHash(key);
        HashMapEntry<K, V>[] tab = table;
        //当tab.length为2^n-1的时候，可以保证结果不大于tab.length
        int index = hash & (tab.length - 1);
        for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
            if (e.hash == hash && key.equals(e.key)) {
                preModify(e);
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
        }
 
        // No entry for (non-null) key is present; create one
        modCount++;
        //扩容
        if (size++ > threshold) {
            tab = doubleCapacity();
            index = hash & (tab.length - 1);
        }
        addNewEntry(key, value, hash, index);
        return null;
    }

• 1

当两个Key同时hash到一个值时，就会出现这样的冲突。这个冲突主要有2种解决方法。

1、开放地址，亦即如果hash冲突，则在空闲的位置进行插入
2、hash复用，同一个hash值，链式地加入多个value

• 1

get()方法

  public V get(Object key) {
        if (key == null) {//允许value为空
            HashMapEntry<K, V> e = entryForNullKey;
            return e == null ? null : e.value;
        }
        //使得hash过后的值的分布更加均匀，尽可能地避免冲突
        int hash = Collections.secondaryHash(key);
        HashMapEntry<K, V>[] tab = table;
        for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
                e != null; e = e.next) {
            K eKey = e.key;
            if (eKey == key || (e.hash == hash && key.equals(eKey))) {
                return e.value;
            }
        }
        return null;
    }

• 1

HashMap还有很多方法，这里就不一一例举了；

通过get与put的源码，可以看出HashMap获取数据是通过遍历Entry[]数组来得到对应的元素，在数据量很大时候会比较慢，所以在Android中，HashMap是比较费内存的，我们在一些情况下可以使用SparseArray和ArrayMap来代替HashMap。
SparseArray

/**
 * A copy of the current platform (currently {@link android.os.Build.VERSION_CODES#KITKAT}
 * version of {@link android.util.SparseArray}; provides a removeAt() method and other things.
 */
public class SparseArrayCompat<E> implements Cloneable {
    private static final Object DELETED = new Object();
    private boolean mGarbage = false;
 
    private int[] mKeys;
    private Object[] mValues;
    private int mSize;

• 1

可以看出SparseArray由两个数组mKeys和mValues存放数据;其中key的类型为int型，这就显得SparseArray比HashMap更省内存一些，SparseArray在存储和读取数据时候，使用的是二分查找法，那何为二分法呢？
先看一下put()方法：

public void put(int key, E value) {
        int i =  ContainerHelpers.binarySearch(mKeys, mSize, key);
 
        if (i >= 0) {
            mValues[i] = value;
        } else {
            i = ~i;
 
            if (i < mSize && mValues[i] == DELETED) {
                mKeys[i] = key;
                mValues[i] = value;
                return;
            }
 
            if (mGarbage && mSize >= mKeys.length) {
                gc();
 
                // Search again because indices may have changed.
                i = ~ ContainerHelpers.binarySearch(mKeys, mSize, key);
            }
            //如果容量不够 
            if (mSize >= mKeys.length) {
                int n =  ContainerHelpers.idealIntArraySize(mSize + 1);
 
                int[] nkeys = new int[n];
                Object[] nvalues = new Object[n];
 
                // Log.e("SparseArray", "grow " + mKeys.length + " to " + n);
                //特别注意这，是copy，而不是new，效率提升 
                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++;
        }
    }

• 1

在上面代码中有一个ContainerHelpers.binarySearch(mKeys, mSize, key)方法，这是Arrays提供了一个方便查询的方法，也就是我们所说的“二分法”;

  // 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) {
            int mid = (lo + hi) >>> 1;//无符号右移 
            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
    }

• 1

get()方法：

 public E get(int key, E valueIfKeyNotFound) {
        //二分法
        int i =  ContainerHelpers.binarySearch(mKeys, mSize, key);
 
        if (i < 0 || mValues[i] == DELETED) {
            return valueIfKeyNotFound;
        } else {
            return (E) mValues[i];
        }
    }

• 1

使用二分查找法和之前的key比较当前我们添加的元素的key的大小，然后按照从小到大的顺序排列好，所以，SparseArray存储的元素都是按元素的key值从小到大排列好的。
而在获取数据的时候，也是使用二分查找法判断元素的位置，所以，在获取数据的时候非常快，比HashMap快的多，因为HashMap获取数据是通过遍历Entry[]数组来得到对应的元素。
其他的一些方法：
转存失败重新上传取消
ArrayMap
ArrayMap是一个键值对映射的数据结构，它设计上更多的是考虑内存的优化，内部是使用两个数组进行数据存储，一个数组记录key的hash值，另外一个数组记录Value值，它和SparseArray一样，也会对key使用二分法进行从小到大排序，区别是ArrayMap的key是hash值，

public class ArrayMap, V> extends SimpleArrayMap, V> implements Map, V> {
    MapCollections<K, V> mCollections;
 
    public ArrayMap() {
        super();
    }

• 1

可以看出ArrayMap的构造方法直接调用的父类的构造方法：

    int[] mHashes;
    Object[] mArray;
    public SimpleArrayMap() {
        mHashes = ContainerHelpers.EMPTY_INTS;
        mArray = ContainerHelpers.EMPTY_OBJECTS;
        mSize = 0;
    }

• 1

put()方法：

  public V put(K key, V value) {
        final int hash;
        int index;
        if (key == null) {
            hash = 0;
            index = indexOfNull();
        } else {
            hash = key.hashCode();
            index = indexOf(key, hash);
        }
        if (index >= 0) {
            index = (index<<1) + 1;
            final V old = (V)mArray[index];
            mArray[index] = value;
            return old;
        }
 
        index = ~index;
        if (mSize >= 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");
                System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
                System.arraycopy(oarray, 0, mArray, 0, oarray.length);
            }
           //释放资源
            freeArrays(ohashes, oarray, mSize);
        }
 
        if (index < mSize) {
            if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index)
                    + " to " + (index+1));
            System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index);
            System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
        }
 
        mHashes[index] = hash;
        mArray[index<<1] = key;
        mArray[(index<<1)+1] = value;
        mSize++;
        return null;
    }