Android之ArrayMap

参考Android达摩院的ArrayMap文章。
ArrayMap是Android中存储的一个数据结构。是Android专门针对内存优化而设计的，用于取代Java API中的HashMap。为了进一步优化key是int类型的Map，Android再次提供了效率更高的数据结构SparseArray，可避免自动装箱过程。对于key为其他类型则使用ArrayMap。HashMap的get和put方法的时间复杂度是O(1)是以牺牲大量内存为代价而才得以实现的，SparseArray和ArrayMap性能略低于HashMap，但是更节省内存，用在移动端是权衡的结果。

一、ArrayMap源码分析

1.1 基本成员变量

public final class ArrayMap<K,V> implements Map<K,V> {
    
    private static final boolean CONCURRENT_MODIFICATION_EXCEPTIONS = true;
    //默认的容量的最小值
    private static final int BASE_SIZE = 4;
    //缓存数组的上限
    private static final int CACHE_SIZE = 10;
    //用于缓存大小为4的ArrayMap
    static Object[] mBaseCache;

    static int mBaseCacheSize;
    //用于缓存大小为8的ArrayMap
    static Object[] mTwiceBaseCache;
    static int mTwiceBaseCacheSize;

    final boolean mIdentityHashCode;
    //由key的hashcode所组成的数组
    int[] mHashes;
    //由key-value对所组成的数组，是mHashes的两倍
    Object[] mArray;
    //成员变量的个数
    int mSize;
}

1,ArrayMap对象的存储格式如下图所示：

mHashes是一个记录所有key的hashcode值组成的数组，是从升序排序
mArray是一个记录着所有key-value键值对所组成的数组

mSize:记录ArrayMap对象中有多少对数据，put或append方法时，mSize会加1，执行remove则减1。mSize往往小于mHashes.length，如果mSize大于或等于mHashes.length，则说明mHashes和mArray需要扩容。

2，ArrayMap中还有两个很重要的成员变量mBaseCache和mTwiceBaseCache，用于ArrayMap所在进程的全局缓存功能。

mBaseCache：用于缓存大小为4的ArrayMap，mBaseCacheSize记录着当前已缓存的数据，超过10个就不在缓存

mTwiceBaseCache：用于缓存大小为8的ArrayMap，mTwiceBaseCache记录着当前已缓存的数量，超过10个则不再缓存
ArrayMap用两个大小为10的缓存队列来分别保存大小为4和8的Map对象。为了节省内存有更加保守的内存扩容和内存收缩策略。我们来看看ArrayMap缓存和扩容机制。

1.2 ArrayMap缓存机制

ArrayMap是专门为Android优化而设计的Map对象，使用比较高频，很多场景可能起初都是数据很少，为了减少频繁地创建和回收，特意设计了两个缓存池，分别缓存大小为4和8的ArrayMap对象。要理解缓存机制，就需要看内存是怎么分配(allocArrays)和内存释放(freeArrays)。

1.2.1

228  private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
229        if (hashes.length == (BASE_SIZE*2)) {
230            synchronized (ArrayMap.class) {
                  当大小为8的缓存池数量小于10个，则将其放入缓存池
231                if (mTwiceBaseCacheSize < CACHE_SIZE) {
232                    array[0] = mTwiceBaseCache;//arr[0]指向原来的缓存池
233                    array[1] = hashes;
234                    for (int i=(size<<1)-1; i>=2; i--) {
235                        array[i] = null;//清空其它数据
236                    }
237                    mTwiceBaseCache = array;//mTwiceBaseCache指向新加入缓存池的Array
238                    mTwiceBaseCacheSize++;
239                    if (DEBUG) Log.d(TAG, "Storing 2x cache " + array
240                            + " now have " + mTwiceBaseCacheSize + " entries");
241                }
242            }
243        } else if (hashes.length == BASE_SIZE) {//当释放的是大小为4的对象，原理同上
244            synchronized (ArrayMap.class) {
245                if (mBaseCacheSize < CACHE_SIZE) {
246                    array[0] = mBaseCache;
247                    array[1] = hashes;
248                    for (int i=(size<<1)-1; i>=2; i--) {
249                        array[i] = null;
250                    }
251                    mBaseCache = array;
252                    mBaseCacheSize++;
253                    if (DEBUG) Log.d(TAG, "Storing 1x cache " + array
254                            + " now have " + mBaseCacheSize + " entries");
255                }
256            }
257        }
258  }

如上代码就是freeArrays方法的代码，最初mTwiceBaseCacheSize和mBaseCacheSize缓存池中都没有数据，在freeArrays释放内存时，如果同时满足释放的Arrays大小等于4或8，且对应的缓存池个数未达上限，则会把该array加入到缓存池中。加入的方法时将数组array的0角标元素指向原有的缓存池，1角标元素指向hashes数组的地址，arr[2]元素以后的数据全部为null。再把缓存池的头部指向最新的array的位置，并将该缓存池大小执行加1操作。
freeArrays触发时机

当执行removeAt()移除最后一个元素的情况
当执行clear()清理的时候
当执行ensureCapacity()在当前容量小于预期容量的时候，先执行allocArrays函数，再执行freeArrays函数

当执行put()在容量满的时候，先执行allocArrays，再执行freeArrays

1.2.2

allocArrays()函数代码

190 private void allocArrays(final int size) {
191        if (mHashes == EMPTY_IMMUTABLE_INTS) {
192            throw new UnsupportedOperationException("ArrayMap is immutable");
193        }
194        if (size == (BASE_SIZE*2)) {//当分配大小为8的对象，先查看缓存池
195            synchronized (ArrayMap.class) {
196                if (mTwiceBaseCache != null) {//当缓存池不为空时
197                    final Object[] array = mTwiceBaseCache;
198                    mArray = array;//从缓存中取出mArray
199                    mTwiceBaseCache = (Object[])array[0];//将缓存池指向上一条缓存地址
200                    mHashes = (int[])array[1];//从缓存中mHashes
201                    array[0] = array[1] = null;
202                    mTwiceBaseCacheSize--;//缓存池大小减1
203                    if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes
204                            + " now have " + mTwiceBaseCacheSize + " entries");
205                    return;
206                }
207            }
208        } else if (size == BASE_SIZE) {////当分配的是大小为4的对象，原理同上
209            synchronized (ArrayMap.class) {
210                if (mBaseCache != null) {
211                    final Object[] array = mBaseCache;
212                    mArray = array;
213                    mBaseCache = (Object[])array[0];
214                    mHashes = (int[])array[1];
215                    array[0] = array[1] = null;
216                    mBaseCacheSize--;
217                    if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes
218                            + " now have " + mBaseCacheSize + " entries");
219                    return;
220                }
221            }
222        }
            //分配除了4和8之外大小对象的情况，则直接创建新的数组
223        mHashes = new int[size];
225        mArray = new Object[size<<1];
226  }

allocArrays分配内存时，如果所需分配的大小等于4或8，且相应的缓存池不为空，则会从相应的缓存池中取出