SparseArray and ArrayMap

[yunshuipiao]

SparseArray and ArrayMap

[TOC]

Android 设备为了较少内存的使用和装拆箱损耗的性能，提供一些特有的数据结构代替 java 中原来的数据结构，适当采用这些数据结构可以优化应用的内存。

ArrayMap

用于代替 HashMap 使用，有几个特点：

• 内部实现基于两个数组，可以避免在数据插入 Map 时额外的空间消耗
• 有扩容和收缩功能
• 不适合存储大容量数据；数据量大时，性能退化至少 50 %。

/** {@hide} */
public ArrayMap(int capacity, boolean identityHashCode) {
  // 是否返回系统唯一 hashcode
    mIdentityHashCode = identityHashCode;
		
    // If this is immutable, use the sentinal EMPTY_IMMUTABLE_INTS
    // instance instead of the usual EmptyArray.INT. The reference
    // is checked later to see if the array is allowed to grow.
    if (capacity < 0) {
      	// 不可变 ArrayMap
        mHashes = EMPTY_IMMUTABLE_INTS;
        mArray = EmptyArray.OBJECT;
    } else if (capacity == 0) {
      	// 空 ArrayMap
        mHashes = EmptyArray.INT;
        mArray = EmptyArray.OBJECT;
    } else {
        allocArrays(capacity);
    }
  	// 容量
    mSize = 0;
}

 private void allocArrays(final int size) {
        if (mHashes == EMPTY_IMMUTABLE_INTS) {
            throw new UnsupportedOperationException("ArrayMap is immutable");
        }
        // 保存 hash 值大小的数组
        mHashes = new int[size];
   			// 保存 key， value 的数据，2倍。
        mArray = new Object[size<<1];
    }

上面是基本的构造函数，负责给 ArrayMap 的存储结构分配大小，下面看一下具体的 put 和 get 操作。

// 如果 key 存在，则返回 oldValue
@Override
public V put(K key, V value) {
    final int osize = mSize;
    final int hash;
    int index;
    if (key == null) {
        hash = 0;
      	// 寻找 null 的下标
        index = indexOfNull();
    } else {
        hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
      	// 下标，二分查找
        index = indexOf(key, hash);
    }
  	// key 存在，找到值并返回
    if (index >= 0) {
        index = (index<<1) + 1;
        final V old = (V)mArray[index];
        mArray[index] = value;
        return old;
    }
		// index < 0, 说明是插入操作
    index = ~index;
  	// 需要扩容
    if (osize >= mHashes.length) {
        final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))
                : (osize >= 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 (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
            throw new ConcurrentModificationException();
        }
				// 复制临时数组中的数据到新数组
        if (mHashes.length > 0) {
            if (DEBUG) Log.d(TAG, "put: copy 0-" + osize + " to 0");
            System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
            System.arraycopy(oarray, 0, mArray, 0, oarray.length);
        }
				// 释放临时数据的内容
        freeArrays(ohashes, oarray, osize);
    }
		
  
  	// 插入数据在中间
    if (index < osize) {
        if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (osize-index)
                + " to " + (index+1));
        System.arraycopy(mHashes, index, mHashes, index + 1, osize - index);
        System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
    }

    if (CONCURRENT_MODIFICATION_EXCEPTIONS) {
        if (osize != mSize || index >= mHashes.length) {
            throw new ConcurrentModificationException();
        }
    }
    mHashes[index] = hash;
    mArray[index<<1] = key;
    mArray[(index<<1)+1] = value;
    mSize++;
    return null;

// get 操作主要是找到下标
@Override
public V get(Object key) {
    final int index = indexOfKey(key);
    return index >= 0 ? (V)mArray[(index<<1)+1] : null;
}

下面来看一下 查找下标的操作：

int indexOf(Object key, int hash) {
  	// 当前数据的大小
    final int N = mSize;

    // Important fast case: if nothing is in here, nothing to look for.
  	// 如果大小为0，说明没有数据存在，返回 -1 表示插入
    if (N == 0) {
        return ~0;
    }
		
  	// 二分查找到下标
    int index = binarySearchHashes(mHashes, N, hash);

    // If the hash code wasn't found, then we have no entry for this key.
  	// 返回要插入的下标位置
    if (index < 0) {
        return index;
    }

    // If the key at the returned index matches, that's what we want.
    if (key.equals(mArray[index<<1])) {
        return index;
    }

    // Search for a matching key after the index.
  	// 遇到冲突，开放地址发解决冲突，从前往后找
    int end;
    for (end = index + 1; end < N && mHashes[end] == hash; end++) {
        if (key.equals(mArray[end << 1])) return end;
    }

    // Search for a matching key before the index.
  	// 从后往前找
    for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
        if (key.equals(mArray[i << 1])) return i;
    }

    // Key not found -- return negative value indicating where a
    // new entry for this key should go.  We use the end of the
    // hash chain to reduce the number of array entries that will
    // need to be copied when inserting.
 		// 未找到是取反表示需要插入的位置
    return ~end;
}

SparseArray

与上面介绍的一样，也是用来在 key 为 int 类型时代替 HashMap 的，直接看源码吧。采用稀疏数组保存数据。

// 默认容量是 10
public SparseArray(int initialCapacity) {
    if (initialCapacity == 0) {
        mKeys = EmptyArray.INT;
        mValues = EmptyArray.OBJECT;
    } else {
      	// 数组，存储的 value
        mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
      	// key，int 类型
        mKeys = new int[mValues.length];
    }
    mSize = 0;
}

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);
        }

        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}

get 操作就是一个取下标的过程。

用Bundle而不是用HashMap来进行数据传递

• Bundle内部是由ArrayMap实现的，ArrayMap的内部实现是两个数组，一个int数组是存储对象数据对应下标，一个对象数组保存key和value，内部使用二分法对key进行排序，所以在添加、删除、查找数据的时候，都会使用二分法查找，只适合于小数据量操作，如果在数据量比较大的情况下，那么它的性能将退化。而HashMap内部则是数组+链表结构，所以在数据量较少的时候，HashMap的Entry Array比ArrayMap占用更多的内存。因为使用Bundle的场景大多数为小数据量。所以相比之下，在这种情况下使用ArrayMap保存数据，在操作速度和内存占用上都具有优势，因此使用Bundle来传递数据，可以保证更快的速度和更少的内存占用。
• Android中如果使用Intent来携带数据的话，需要数据是基本类型或者是可序列化类型，HashMap使用Serializable进行序列化，而Bundle则是使用Parcelable进行序列化。而在Android平台中，更推荐使用Parcelable实现序列化，虽然写法复杂，但是开销更小，所以为了更加快速的进行数据的序列化和反序列化，系统封装了Bundle类，方便我们进行数据的传输。

总结

在 Android 系统是可以使用 Arraymap 和 SparseArray 来代替 HashMap 的使用。

其中前者直接用数组存储 key 和 value， 而不是使用 Entry 对象。点那个数组需要增长时，无需重新构建 hash。

而后者主要是解决 hashMap 自动装拆箱过程带来的内存消耗，并且使用稀疏数组存储数据。

两者都是围绕时间换空间的方式来解决移动端内存有限的问题，但是都只适用于数据量比较小的情况，官方推荐不超过 1000。