Android中的ArrayMap源码解析 - Android - 面试 - 框架源码解析

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、根据keyhash值在mHashs中的index,如何得到key、valuemArray中的下标位置呢?key的位置是index*2value的位置是index*2+1,也就是说mArray是利用连续的两位空间去存放key、value

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

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

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


   转载规则


《Android中的ArrayMap源码解析 - Android - 面试 - 框架源码解析》 mikyou 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
Android中消息机制与Handler源码解析 Android中消息机制与Handler源码解析
Android中消息机制与Handler源码解析 Android中消息机制构成整个Android系统的应用运行基础,我们都知道在每个应用主UI线程都存在一个消息循环系统也就是我们常说的MainLoop. Android应用中每一个交互动作都
2019-12-29
下一篇 
Android中的SparseArray源码解析 Android中的SparseArray源码解析
Android中的SparseArray源码解析一、概述 在Android平台中,更推荐使用SparseArray<E>来替代HashMap的数据结构,更具体的说,是用于替代key为int类型,value为Object类型的Ha
2019-12-29