您的位置: 首页  >  文章  >  Android中HashMap内存优化之ArrayMap和SparseArray

Android中HashMap内存优化之ArrayMap和SparseArray

分类: 文章 • 2025-01-20 15:19:05
ArrayMap及SparseArray是android的系统API，是专门为移动设备而定制的。用于在一定情况下取代HashMap而达到节省内存的目的。

在Android开发中HashMap使用频率相当高，回顾一下HashMap的结构，其是以array存储链表的头结点，找到头结点后在进行遍历查找，如下图：
Android中HashMap内存优化之ArrayMap和SparseArray

时间效率方面，利用hash算法，插入和查找等操作都很快，且一般情况下，每一个数组值后面不会存在很长的链表（因为出现hash冲突毕竟占比较小的比例），所以不考虑空间利用率的话，HashMap的效率非常高。

但是HashMap有如下特点：

1: HashMap中默认的存储大小是一个容量为16的数组，所以当我们创建出一个HashMap对象时，即使里面没有任何元素，也要分别一块内存空间给它，而且当我们不断的向HashMap里put数据时，达到一定的容量限制时HashMap的空间将会扩大，从图示中可以看出当HashMap扩容容量过多，元素较少时会产生内存使用不平衡，即浪费不少内存。

2: 还有使用HashMap会涉及一个要求：key与value必须为对象类型，而不能为基本类型，这就导致了本可以使用基本类型的数据必须转换为其对象包装类型（int->Integer,long->Long......）这就涉及到需要占用更多内存以及拆箱装箱频繁转换问题。
在jvm中一个Integer类型占用内存大小 > 12byte，一个空Object对象的大小是8byte，这个大小只是保存堆中一个没有任何属性的对象的大小。Object ob = new Object();这样在程序中完成了一个空Java对象的声明，但是它所占的空间为：4byte+8byte，4byte是Java statck中保存引用所需要的空间，而8byte则是Java heap中对象的信息。所有的Java非基本类型的对象都需要默认继承Object对象，因此不论什么样的Java对象，其大小都必须是大于8byte。包装类型已经成为对象类型，因此需要按照对象类型的大小计算至少是12byte（声明一个空Object至少需要的空间），而且12byte没有包含任何有效信息，同时，Java进行对对象的内存分配时其大小是8的整数倍，因此一个基本类型包装类的大小至少是16byte。

3:HashMap本质上是一个HashMapEntry构成的数组。每个HashMapEntry的实体都包括:
  • 一个非基本类型的key
  • 一个非基本类型的value
  • 一个key的Hashcode
  • 指向下一个Entry的指针
            final K key;
            V value;
            HashMapEntry<K,V> next;
            int hash;
所以总结下HashMap的缺点：
  • 当HashMap扩容容量过多，元素较少时会产生内存使用不平衡，即浪费不少内存。
  • 基本数据类型自动装箱意味着需要产生额外的对象。
  • HashMapEntry对象的创建，并且HashMapEntry自己本身也会产生额外的对象。
  • 哈希是很好的实现方案，但是如果实现的不好将会让我们的开销回到O(N)


所以下面开始介绍Android为我们提供的各种优化的类：ArrayMap，SimpleArrayMap，SparseArray，LongSparseArray，SparseIntArray, SparseLongArray，SparseBooleanArray。

先从如何使用它们开始吧：

java.util.HashMap<String, String> hashMap = new java.util.HashMap<String, String>(16);
hashMap.put("key", "value");
hashMap.get("key");
hashMap.entrySet().iterator();

android.util.ArrayMap<String, String> arrayMap = new android.util.ArrayMap<String, String>(16);
arrayMap.put("key", "value");
arrayMap.get("key");
arrayMap.entrySet().iterator();

android.support.v4.util.ArrayMap<String, String> supportArrayMap =
        new android.support.v4.util.ArrayMap<String, String>(16);
supportArrayMap.put("key", "value");
supportArrayMap.get("key");
supportArrayMap.entrySet().iterator();

android.support.v4.util.SimpleArrayMap<String, String> simpleArrayMap =
        new android.support.v4.util.SimpleArrayMap<String, String>(16);
simpleArrayMap.put("key", "value");
simpleArrayMap.get("key");
//simpleArrayMap.entrySet().iterator();      <- will not compile

android.util.SparseArray<String> sparseArray = new android.util.SparseArray<String>(16);
sparseArray.put(10, "value");
sparseArray.get(10);

android.util.LongSparseArray<String> longSparseArray = new android.util.LongSparseArray<String>(16);
longSparseArray.put(10L, "value");
longSparseArray.get(10L);

android.util.SparseLongArray sparseLongArray = new android.util.SparseLongArray(16);
sparseLongArray.put(10, 100L);
sparseLongArray.get(10);



SparseArray

先看看SparseArray的结构如下图：

Android中HashMap内存优化之ArrayMap和SparseArray
SparseArray比HashMap更省内存，在某些条件下性能更好，主要是因为它避免了对key的自动装箱（int转为Integer类型），还避免了HashMapEntry对象的创建，它内部则是通过两个数组来进行数据存储的，一个存储key（有序），另外一个存储value，为了优化性能，对key使用了二分查找的方法，它内部对数据还采取了压缩的方式来表示稀疏数组的数据，从而节约内存空间，我们从源码中可以看到key和value分别是用数组表示：
    private int[] mKeys;
    private Object[] mValues;
因为key为int也就不需要什么hash值了，只要int值相等，那就是同一个对象，简单粗暴。
空间上对比：与HashMap，去掉了Hash值的存储空间，没有next的指针占用，还有HashMapEntry的内存占用。
时间上对比：因为需要有序，可能存在大量的数组搬移。但是它避免了装箱的环节，装箱过程还是很费时的。

  • 它里面也用了两个数组。一个int[] mKeys和Object[] mValues。从名字都可以看得出来一个用来存储key一个用来保存value的。
  • key（不是它的hashcode）保存在mKeys[]的下一个可用的位置上。所以不会再对key自动装箱了。
  • value保存在mValues[]的下一个位置上，value还是要自动装箱的，如果它是基本类型。
  • 查找key还是用的二分法查找。也就是说它的时间复杂度还是O(logN)
  • 知道了key的index，也就可以用key的index来从mValues中检索出value。
SparseArray只能存储key为int类型的数据，同时SparseArray在存储和读取数据时候，对key使用的是二分查找法，所以key存储是有序的并不是按插入的顺序，可以看看：
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，然后按照从小到大的顺序排列好，所以，SparseArray存储的元素都是按元素的key值从小到大排列好的。 而在获取数据的时候，也是使用二分查找法判断元素的位置，所以，在获取数据的时候非常快。

满足下面两个条件我们可以使用SparseArray代替HashMap：
  • 数据量不大，最好在千级以内
  • key必须为int类型

LongSparseArray，SparseIntArray，SparseLongArray，SparseBooleanArray

SparseArray只接受int类型作为key,而LongSparseArray可以用long作为key，实现原理和SparseArray一致。
其次对于key是int类型而value也是基本数据类型，我们可以对应使用SparseIntArray,SparseLongArray ,SparseBooleanArray 。它们使用方式是和SparseArray一样的。它的好处是mValues[]是基本类型的数组。也就意味着无论是key还是value都不用装箱。并且相对于HashMap来说我们节约了3个对象的初始化（Entry,Key和Value），但是我们将查询复杂度从O(1)上升到了O(logN)

SparseArray实现
  1. public class SparseArray<E> implements Cloneable {  
  2.     private static final Object DELETED = new Object();  
  3.     private boolean mGarbage = false;  
  4.   
  5.     private int[] mKeys;//使用array存储int key  
  6.     private Object[] mValues;//使用array存储泛型Value  
  7.     private int mSize;  
  8.   
  9.     /** 
  10.      * Creates a new SparseArray containing no mappings. 
  11.      */  
  12.     public SparseArray() {  
  13.         this(10);//默认容量10  
  14.     }  
  15.   
  16.     public SparseArray(int initialCapacity) {  
  17.         if (initialCapacity == 0) {  
  18.             mKeys = EmptyArray.INT;  
  19.             mValues = EmptyArray.OBJECT;  
  20.         } else {  
  21.             mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);  
  22.             mKeys = new int[mValues.length];  
  23.         }  
  24.         mSize = 0;  
  25.     }  
  26.       
  27.         /** 
  28.      * Gets the Object mapped from the specified key, or <code>null</code> 
  29.      * if no such mapping has been made. 
  30.      */  
  31.     public E get(int key) {  
  32.         return get(key, null);  
  33.     }  
  34.   
  35.     /** 
  36.      * Gets the Object mapped from the specified key, or the specified Object 
  37.      * if no such mapping has been made. 
  38.      */  
  39.     @SuppressWarnings("unchecked")  
  40.     public E get(int key, E valueIfKeyNotFound) {  
  41.         int i = ContainerHelpers.binarySearch(mKeys, mSize, key);//使用二分查找查找key  
  42.   
  43.         if (i < 0 || mValues[i] == DELETED) {//没有找到key或者Value已经被deleted  
  44.             return valueIfKeyNotFound;  
  45.         } else {  
  46.             return (E) mValues[i];  
  47.         }  
  48.     }  
  49.   
  50.      public void put(int key, E value) {  
  51.         int i = ContainerHelpers.binarySearch(mKeys, mSize, key);//二分查找key是否存在，如果没有找到时，这里返回的是-low，也就是待插入位置取反  
  52.   
  53.         if (i >= 0) {//存在直接替换value  
  54.             mValues[i] = value;  
  55.         } else {  
  56.             i = ~i;//待插入位置  
  57.   
  58.             if (i < mSize && mValues[i] == DELETED) {//pos在size范围内，并且该pos被deleted直接赋值  
  59.                 mKeys[i] = key;  
  60.                 mValues[i] = value;  
  61.                 return;  
  62.             }  
  63.   
  64.             if (mGarbage && mSize >= mKeys.length) {//是否需要回收处理  
  65.                 gc();  
  66.   
  67.                 // Search again because indices may have changed.  
  68.                 i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);  
  69.             }  
  70.   
  71.             mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);//扩容key处理  
  72.             mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);//扩容value处理  
  73.             mSize++;  
  74.         }  
  75.     }  
  76. ......  
这里注意到一个Deleted标识，这个是什么呢？就是前面类的一个object成员变量，当执行delete，remove时value[i]被标记
  1. public void delete(int key) {  
  2.         int i = ContainerHelpers.binarySearch(mKeys, mSize, key);  
  3.   
  4.         if (i >= 0) {//执行remove不会立即回收，而是做个标记处理  
  5.             if (mValues[i] != DELETED) {  
  6.                 mValues[i] = DELETED;  
  7.                 mGarbage = true;  
  8.             }  
  9.         }  
  10.     }  
  11.   
  12. public void removeAt(int index) {  
  13.         if (mValues[index] != DELETED) {  
  14.             mValues[index] = DELETED;  
  15.             mGarbage = true;  
  16.         }  
  17.     }  
这样标记的一个好处就是避免array频繁移动元素，对数据频繁的delete，removed，put操作时，在一定程度上可以起到缓存作用，避免GC频繁，提高效率，只有当执行gc时才进行回收处理
  1. private void gc() {  
  2.        // Log.e("SparseArray", "gc start with " + mSize);  
  3.   
  4.        int n = mSize;  
  5.        int o = 0;  
  6.        int[] keys = mKeys;  
  7.        Object[] values = mValues;  
  8.   
  9.        for (int i = 0; i < n; i++) {//回收处理，遍历array，对array未被标记delete元素移位放在一起，重新定位index  
  10.            Object val = values[i];  
  11.   
  12.            if (val != DELETED) {  
  13.                if (i != o) {  
  14.                    keys[o] = keys[i];  
  15.                    values[o] = val;  
  16.                    values[i] = null;  
  17.                }  
  18.   
  19.                o++;  
  20.            }  
  21.        }  
  22.   
  23.        mGarbage = false;  
  24.        mSize = o;  
  25.   
  26.        // Log.e("SparseArray", "gc end with " + mSize);  
  27.    }  



ArrayMap

先来看看ArrayMap的结构如下图：

Android中HashMap内存优化之ArrayMap和SparseArray

  • ArrayMap 用了两个数组，mHashes用来保存每一个key的hash值，mArrray大小为mHashes的2倍，依次保存key和value。
  • Key/Value会被自动装箱。
  • key会存储在mArray[]的下一个可用的位置。
  • 而value会存储在mArray[]中key的下一个位置。（key和value在mArray中交叉存储）
  • key的哈希值会被计算出来并存储在mHashed[]中。
    当查找一个key的时候：
  • 计算key的hashcode。
  • 在mHashes[]中对这个hashcode进行二分法查找。也就意味着时间复杂度增加到了O(logN)
  • 一旦我们得到了这个哈希值的位置index。我们就知道这个key是在mArray的2index的位置，而value则在2index+1的位置。
    这个ArrayMap还是没能解决自动装箱的问题。当put一对键值对进入的时候，它们只接受Object，但是我们相对于HashMap来说每一次put会少创建一个对象(HashMapEntry)。这是不是值得我们用O(1)的查找复杂度来换呢？对于大多数app应用来说是值得的。

当出现哈希冲突时，会在index的相邻位置插入。从空间角度考虑，ArrayMap每存储一条信息，需要保存一个hash值，一个key值，一个value值，对比下HashMap 只是减少了一个entity，还有就是节省了一部分内存使用不平衡的内存。时间效率上看，插入和查找的时候都用的二分法，查找是没有hash查找快，插入的时候呢，如果顺序插入的话效率肯定高，但如果是随机插入，肯定会涉及到大量的数组搬移，如果是每次插入的hash值都比上一次的小，那就得次次搬移，效率很差。

ArrayMap实现
  1. public final class ArrayMap<K, V> implements Map<K, V> {  
  2.     ...  
  3.       
  4.     /** 
  5.      * @hide Special immutable empty ArrayMap. 
  6.      */  
  7.     public static final ArrayMap EMPTY = new ArrayMap(true);  
  8.     ...  
  9.      
  10.     /** 
  11.      * Special hash array value that indicates the container is immutable. 
  12.      */  
  13.     static final int[] EMPTY_IMMUTABLE_INTS = new int[0];  
  14.   
  15.     int[] mHashes;//存储key的hashCode  
  16.     Object[] mArray;//存储key（偶数索引存储key）与value(奇数索引存储value)  
  17.     int mSize;  
  18.       
  19.       
  20.      int indexOf(Object key, int hash) {//查找hash code索引位置  
  21.         final int N = mSize;  
  22.   
  23.         // Important fast case: if nothing is in here, nothing to look for.  
  24.         if (N == 0) {  
  25.             return ~0;  
  26.         }  
  27.   
  28.         int index = ContainerHelpers.binarySearch(mHashes, N, hash);//二分查找hash code的index  
  29.   
  30.         // If the hash code wasn't found, then we have no entry for this key.  
  31.         if (index < 0) {//未查找到  
  32.             return index;  
  33.         }  
  34.   
  35.         // If the key at the returned index matches, that's what we want.  
  36.         if (key.equals(mArray[index<<1])) {//查找到index，对应到mArray位置中指定的key index  
  37.             return index;  
  38.         }  
  39.   
  40.         // Search for a matching key after the index.  
  41.         int end;  
  42.         for (end = index + 1; end < N && mHashes[end] == hash; end++) {  
  43.             if (key.equals(mArray[end << 1])) return end;  
  44.         }  
  45.   
  46.         // Search for a matching key before the index.  
  47.         for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {  
  48.             if (key.equals(mArray[i << 1])) return i;  
  49.         }  
  50.   
  51.         return ~end;  
  52.     }  
  53.       
  54.     private void allocArrays(final int size) {  
  55.         if (mHashes == EMPTY_IMMUTABLE_INTS) {  
  56.             throw new UnsupportedOperationException("ArrayMap is immutable");  
  57.         }  
  58.         ......  
  59.         mHashes = new int[size];//指定hash array size  
  60.         mArray = new Object[size<<1];//mArray大小为size x2，因为这里使用一个array即存储key，又存储value  
  61.     }  
  62.       
  63.     public void ensureCapacity(int minimumCapacity) {//容量不足时扩容处理  
  64.         if (mHashes.length < minimumCapacity) {  
  65.             final int[] ohashes = mHashes;  
  66.             final Object[] oarray = mArray;  
  67.             allocArrays(minimumCapacity);  
  68.             if (mSize > 0) {  
  69.                 System.arraycopy(ohashes, 0, mHashes, 0, mSize);  
  70.                 System.arraycopy(oarray, 0, mArray, 0, mSize<<1);  
  71.             }  
  72.             freeArrays(ohashes, oarray, mSize);  
  73.         }  
  74.     }  
  75.   
  76.     @Override  
  77.     public boolean containsKey(Object key) {  
  78.         return indexOfKey(key) >= 0;  
  79.     }  
  80.   
  81.     public int indexOfKey(Object key) {  
  82.         return key == null ? indexOfNull() : indexOf(key, key.hashCode());  
  83.     }  
  84.   
  85.     int indexOfValue(Object value) {//查找指定value的索引位置  
  86.         final int N = mSize*2;  
  87.         final Object[] array = mArray;  
  88.         if (value == null) {//null分开查找，value存储在奇数位置，每次+2跳步  
  89.             for (int i=1; i<N; i+=2) {  
  90.                 if (array[i] == null) {  
  91.                     return i>>1;  
  92.                 }  
  93.             }  
  94.         } else {  
  95.             for (int i=1; i<N; i+=2) {  
  96.                 if (value.equals(array[i])) {  
  97.                     return i>>1;  
  98.                 }  
  99.             }  
  100.         }  
  101.         return -1;  
  102.     }  
  103.   
  104.     @Override  
  105.     public boolean containsValue(Object value) {  
  106.         return indexOfValue(value) >= 0;  
  107.     }  
  108.   
  109.     @Override  
  110.     public V get(Object key) {  
  111.         final int index = indexOfKey(key);  
  112.         return index >= 0 ? (V)mArray[(index<<1)+1] : null;  
  113.     }  

  1. @Override  
  2.    public V remove(Object key) {  
  3.        final int index = indexOfKey(key);  
  4.        if (index >= 0) {  
  5.            return removeAt(index);  
  6.        }  
  7.   
  8.        return null;  
  9.    }  
  10.   
  11.    public V removeAt(int index) {  
  12.        final Object old = mArray[(index << 1) + 1];  
  13.        if (mSize <= 1) {  
  14.            // Now empty.  
  15.            if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0");  
  16.            freeArrays(mHashes, mArray, mSize);  
  17.            mHashes = EmptyArray.INT;  
  18.            mArray = EmptyArray.OBJECT;  
  19.            mSize = 0;  
  20.        } else {  
  21.            if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {//hash array长度>预定baseSize 2倍，元素个数小于3分之一时，进行容量缩减处理  
  22.                // Shrunk enough to reduce size of arrays.  We don't allow it to//减少内存占用，提供使用效率  
  23.                // shrink smaller than (BASE_SIZE*2) to avoid flapping between  
  24.                // that and BASE_SIZE.  
  25.                final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2);  
  26.   
  27.                if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n);  
  28.   
  29.                final int[] ohashes = mHashes;  
  30.                final Object[] oarray = mArray;  
  31.                allocArrays(n);  
  32.   
  33.                mSize--;  
  34.                if (index > 0) {  
  35.                    if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0");  
  36.                    System.arraycopy(ohashes, 0, mHashes, 0, index);  
  37.                    System.arraycopy(oarray, 0, mArray, 0, index << 1);  
  38.                }  
  39.                if (index < mSize) {  
  40.                    if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + mSize  
  41.                            + " to " + index);  
  42.                    System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index);  
  43.                    System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1,  
  44.                            (mSize - index) << 1);  
  45.                }  
  46.            } else {  
  47.                mSize--;  
  48.                if (index < mSize) {  
  49.                    if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + mSize  
  50.                            + " to " + index);  
  51.                    System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index);  
  52.                    System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1,  
  53.                            (mSize - index) << 1);  
  54.                }  
  55.                mArray[mSize << 1] = null;  
  56.                mArray[(mSize << 1) + 1] = null;  
  57.            }  
  58.        }  
  59.        return (V)old;  
  60.    }  
  1. @Override  
  2.    public V put(K key, V value) {  
  3.        final int hash;  
  4.        int index;//根据key为null，不为null两种方式查找index  
  5.        if (key == null) {  
  6.            hash = 0;  
  7.            index = indexOfNull();  
  8.        } else {  
  9.            hash = key.hashCode();  
  10.            index = indexOf(key, hash);  
  11.        }  
  12.        if (index >= 0) {//查找到已有key，则替换新值，返回旧值  
  13.            index = (index<<1) + 1;  
  14.            final V old = (V)mArray[index];  
  15.            mArray[index] = value;  
  16.            return old;  
  17.        }  
  18.   
  19.        index = ~index;//等到插入位置  
  20.        if (mSize >= mHashes.length) {//扩展array大小  
  21.            final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))  
  22.                    : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);  
  23.   
  24.            if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n);  
  25.   
  26.            final int[] ohashes = mHashes;  
  27.            final Object[] oarray = mArray;  
  28.            allocArrays(n);  
  29.   
  30.            if (mHashes.length > 0) {  
  31.                if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0");  
  32.                System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);  
  33.                System.arraycopy(oarray, 0, mArray, 0, oarray.length);  
  34.            }  
  35.   
  36.            freeArrays(ohashes, oarray, mSize);  
  37.        }  
  38.   
  39.        if (index < mSize) {//移位腾出指定位置空间，待插入位置  
  40.            if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index)  
  41.                    + " to " + (index+1));  
  42.            System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index);  
  43.            System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);  
  44.        }  
  45.   
  46.        mHashes[index] = hash;  
  47.        mArray[index<<1] = key;  
  48.        mArray[(index<<1)+1] = value;  
  49.        mSize++;  
  50.        return null;  
  51.    }  
  52.   
  53.    /** 
  54.     * Special fast path for appending items to the end of the array without validation. 
  55.     * The array must already be large enough to contain the item. 
  56.     * @hide 
  57.     */  
  58.    public void append(K key, V value) {//快速插入指定key-value，当array容量够大，元素较少时使用，去掉了扩容，处理使用抛异常替代  
  59.        int index = mSize;//在最后一个元素位置后执行添加  
  60.        final int hash = key == null ? 0 : key.hashCode();  
  61.        if (index >= mHashes.length) {//hash array边界检测  
  62.            throw new IllegalStateException("Array is full");  
  63.        }  
  64.        if (index > 0 && mHashes[index-1] > hash) {  
  65.        //hash array采用升序排序存储，即前面hash code <后面元素，当插入元素<最后元素时，说明需要进行元素移动  
  66.            RuntimeException e = new RuntimeException("here");  
  67.            e.fillInStackTrace();  
  68.            Log.w(TAG, "New hash " + hash  
  69.                    + " is before end of array hash " + mHashes[index-1]  
  70.                    + " at index " + index + " key " + key, e);  
  71.            put(key, value);//执行移动元素  
  72.            return;  
  73.        }  
  74.        mSize = index+1;  
  75.        mHashes[index] = hash;  
  76.        index <<= 1;  
  77.        mArray[index] = key;  
  78.        mArray[index+1] = value;  
  79.    }  


关于ArrayMap的冲突处理：
我们知道在HashMap中当出现hash冲突时，不同的key映射到同一位置，在冲突位置上，使用单链表形式将该元素插入头部（即采用拉链法解决方案）。
在ArrayMap中则是采取另一种方式，ArrayMap在插入和查找时都用了indexOf方法，在插入时如果发现已经存在相同的hash值则比较它们的key是否相等，相等则替换，不相等则插入下一个位置，mHashes数组中同时存储了出现冲突的hash值，因为排序的原因这些冲突的hash值存储在相邻的位置，在查找时使用了线性探测方案：在冲突发生位置，依次向后或者向前检测是否存在相同的hash值，如果存在则比较他们的key是否equal来找到key真实的index，在indexOf方法可以看到
  1. int indexOf(Object key, int hash) {  
  2.         ...  
  3.         int index = ContainerHelpers.binarySearch(mHashes, N, hash); // 二分查找key是否存在，如果没有找到时，这里返回的是-low，也就是待插入位置取反
  4.         ...  
  5.   
  6.         // .匹配key找到则返回  
  7.         if (key.equals(mArray[index<<1])) {  
  8.             return index;  
  9.         }  
  10.   
  11.         // 没找到继续向后(查找后一半)查找  
  12.         int end;  
  13.         for (end = index + 1; end < N && mHashes[end] == hash; end++) {  
  14.             if (key.equals(mArray[end << 1])) return end;  
  15.         }  
  16.   
  17.         // 还没找到向前查找
  18.         for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {  
  19.             if (key.equals(mArray[i << 1])) return i;  
  20.         }  
  21.         ...  
  22.         return ~end;  
  23.     }  

SimpleArrayMap
在之前代码片段中你可以看到，这个类没有entrySet()这个支持迭代的方法。如果你查看它的文档，你会发现很多java标准集合的方法它都没有。那我们为什么要用它呢。让它失去与其它java容器的相互操作的特性来减小apk的大小。这样的话，Proguard(代码优化和混沌工具)可以帮你减少大多数没有使用的Collections API代码从而减小你的apk大小。它的内部工作和ArrayMap是一样的。

总结：

1，android采用时间换空间的方式，平衡移动设备内存问题而使用SparseArray，ArrayMap替换HashMap。
2，SparseArray使用int[]为Integer类型key存储，Object[]为value，即双数组一一对应的方式实现代替HashMap<Integer,Object>，ArrayMap使用int[] hash 存储Hashcode，Object[] mArrays偶数索引存储key，奇数索引存储value的巧妙方式存储keyPair
3，当key为int类型value为reference object可以使用SparseArray，value为基本类型时使用使用SparsexxxArray，当key为其它引用类型时使用ArrayMap<K, V>替换HashMap
4.即使它们听起来像数组(Array)，但是ArrayMap和SparseArray不能保证保留它们的插入顺序，因为为了实现二分查找，它们是经过排序的（其中SparseArray是根据key排序，而ArrayMap是根据key的hashcode排序），在迭代的时候应该注意。

5.在数据量小的时候一般认为1000以下，当key为int，使用SparseArray确实是一个很不错的选择，相比用HashMap内存大概能节省30%，而且它key值不需要装箱，所以时间性能平均来看也优于HashMap。

6.ArrayMap相对于SparseArray，特点是key值类型不受限任何情况下都可以取代HashMap,但是ArrayMap的内存节省并不明显，时间性能却是最差的，加上它只有在API>=19才可以使用，还不如用HashMap放心。

相关推荐