Android中的ArrayMap源码解析

一、概述

ArrayMap实现Map<K,V>接口，所以它也是一个关联数组和哈希表。存储是key-value结构形式的数据。所以它也是线程不安全，可以允许key,value都为null.

二、特点

• ArrayMap相比HashMap，空间效率更高

• 内部实现同样基于两个数组，一个int[]数组用于保存每个Item的hashCode,一个Object[]数组，用于存储key/value键值对。容量是上一个数组的两倍

• 它可以避免在将数据插入Map中时额外的空间消耗（对比HashMap）。

  而且它扩容的更合适，扩容时只需要数组拷贝工作，不需要重建哈希表。

  和HashMap相比，它不仅有扩容功能，在删除时，如果集合剩余元素少于一定阈值，还有收缩（shrunk）功能。减少空间占用。

  对于哈希冲突的解决，查看源码可以得知采用的是开放地址法。

• 不适合大容量的数据存储。存储大量数据时，它的性能将退化至少50%。
  比传统的HashMap时间效率低。因为其会对key从小到大排序，使用二分法查询key对应在数组中的下标。在添加、删除、查找数据的时候都是先使用二分查找法得到相应的index，然后通过index来进行添加、查找、删除等操作。所以其是按照key的大小排序存储的。

三、适用场景

• 数据量不大

• 空间比时间重要

• 需要使用Map

• 在Android平台上，相对来说内存空间更宝贵。所以当使用的key是Object类型的Map时，考虑使用ArrayMap替代HashMap

Map<String, String> map = new ArrayMap<>();
map.put("1", "1")
map.put("2", "2")
map.put(null, "3")
map.put("4", null)
Log.d("TAG", "onCreate() called with: map = [" + map + "]");

输出:

onCreate() called with: map = [{1=1, 2=2, null=3, 4=null}]

四、构造器函数

    private static final int BASE_SIZE = 4;//扩容默认大小
    static final int[] EMPTY_IMMUTABLE_INTS = new int[0];//表示集合不可变
    public static final ArrayMap EMPTY = new ArrayMap<>(-1);

    static Object[] mBaseCache;
    static int mBaseCacheSize;
    static Object[] mTwiceBaseCache;
    static int mTwiceBaseCacheSize;

    final boolean mIdentityHashCode;//是否利用System.identityHashCode(key) 获取唯一HashCode模式。 
    int[] mHashes;//保存hash值的数组
    Object[] mArray;//保存key/value的数组
    int mSize;//集合大小

    public ArrayMap() {//默认构造器，创建一个空的ArrayMap，默认容量是0.当有Item被添加进来，会自动扩容
        this(0, false);
    }

    public ArrayMap(int capacity) {//指定容量构造器
        this(capacity, false);
    }

    public ArrayMap(int capacity, boolean identityHashCode) {
        mIdentityHashCode = identityHashCode;
        //容量小于0的时候，创建一个不可变的ArrayMap
        if (capacity < 0) {
            mHashes = EMPTY_IMMUTABLE_INTS;
            mArray = EmptyArray.OBJECT;
        } else if (capacity == 0) {//构建空的mHashs、mArray两个数组
            mHashes = EmptyArray.INT;
            mArray = EmptyArray.OBJECT;
        } else {//数量>0，分配空间初始化数组
            allocArrays(capacity);
        }
        mSize = 0;
    }

    public ArrayMap(ArrayMap<K, V> map) {//指定一个ArrayMap为参数
        this();
        if (map != null) {
            putAll(map);//把传入map全部加入到map中
        }
    }

//ArrayMap#allocArrays
private void allocArrays(final int size) {
        if (mHashes == EMPTY_IMMUTABLE_INTS) {
            throw new UnsupportedOperationException("ArrayMap is immutable");
        }
        //如果初始空间是BASE_SIZE的两倍，也就是扩容容量是8
        if (size == (BASE_SIZE*2)) {
            synchronized (ArrayMap.class) {
                //查看之前是否有缓存的 容量为8的int[]数组和容量为16的object[]数组 
                //如果有，复用给mArray mHashes
                if (mTwiceBaseCache != null) {
                    final Object[] array = mTwiceBaseCache;
                    mArray = array;
                    mTwiceBaseCache = (Object[])array[0];
                    mHashes = (int[])array[1];
                    array[0] = array[1] = null;
                    mTwiceBaseCacheSize--;
                    if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes
                            + " now have " + mTwiceBaseCacheSize + " entries");
                    return;
                }
            }
        } else if (size == BASE_SIZE) {//扩容数量是4
            synchronized (ArrayMap.class) {
                 //查看之前是否有缓存的 容量为4的int[]数组和容量为8的object[]数组 
                //如果有，复用给mArray mHashes
                if (mBaseCache != null) {
                    final Object[] array = mBaseCache;
                    mArray = array;
                    mBaseCache = (Object[])array[0];
                    mHashes = (int[])array[1];
                    array[0] = array[1] = null;
                    mBaseCacheSize--;
                    if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes
                            + " now have " + mBaseCacheSize + " entries");
                    return;
                }
            }
        }

        mHashes = new int[size];//创建mHashes数组
        mArray = new Object[size<<1];//创建mArray,mArray是mHashes的长度两倍，因为既需要存储key也要存储value
    }


//ArrayMap#putAll 批量put方法
public void putAll(ArrayMap<? extends K, ? extends V> array) {
        final int N = array.mSize;
        //确认当前空间是否足够
        ensureCapacity(mSize + N);
        //如果当前集合为空
        if (mSize == 0) {
            if (N > 0) {//直接覆盖数组内容
                System.arraycopy(array.mHashes, 0, mHashes, 0, N);
                System.arraycopy(array.mArray, 0, mArray, 0, N<<1);
                mSize = N;
            }
        } else {//不为空需要一个一个执行插入put操作
            for (int i=0; i<N; i++) {
                put(array.keyAt(i), array.valueAt(i));
            }
        }
    }

//ArrayMap#ensureCapacity 确保空间足够存放 minimumCapacity 个数据
public void ensureCapacity(int minimumCapacity) {
        final int osize = mSize;
        //如果不够扩容
        if (mHashes.length < minimumCapacity) {
            final int[] ohashes = mHashes;
            final Object[] oarray = mArray;
            //执行扩容
            allocArrays(minimumCapacity);
            if (mSize > 0) {
            //如果原集合不为空，就把原集合数组数据复制过来
                System.arraycopy(ohashes, 0, mHashes, 0, osize);
                System.arraycopy(oarray, 0, mArray, 0, osize<<1);
            }
            //释放回收暂存的数组空间
            freeArrays(ohashes, oarray, osize);
        }
        if (CONCURRENT_MODIFICATION_EXCEPTIONS && mSize != osize) {
            throw new ConcurrentModificationException();
        }
    }

五、增、删、改、查

待定

六、总结

ArrayMap的实现细节很多地方都和ArrayList类似，有关ArrayMap几点总结如下:

• 1、每次插入时，根据key的哈希值，利用二分查找，去寻找key在int[]mHashes数组中的下标位置

• 2、如果出现hash冲突，就需要从目标点向两头遍历，找到正确的index

• 3、扩容时，会查看之前是否存在缓存的int[]数组和Object[]数组

• 4、如果有，复用给mHashes和mArray

• 5、扩容规则: 如果容量大于8(两倍)，则扩容一半

• 6、根据key的hash值在mHashs中的index，如何得到key、value在mArray中的下标位置呢？key的位置是index*2，value的位置是index*2+1,也就是说mArray是利用连续的两位空间去存放key、value。

• 7、根据元素数量和集合占用的空间情况，判断是否要执行收缩操作

• 8、如果 mHashes长度大于8，且 集合长度 小于当前空间的 1/3,则执行一个 shrunk，收缩操作，避免空间的浪费

• 9、类似ArrayList，用复制操作去覆盖元素达到删除的目的。