Java教程

ArrayMap 原理

本文主要是介绍ArrayMap 原理,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

一 概述

在移动设备端内存资源很珍贵,HashMap为实现快速查询带来了很大内存的浪费。为此,2013年5月20日Google工程师Dianne Hackborn在Android系统源码中新增ArrayMap类,从Android源码中发现有不少提交专门把之前使用HashMap的地方改用ArrayMap,不仅如此,大量的应用开发者中广为使用。

然后,你是否研究过这么广泛使用的基础数据结构存在缺陷?要回答这个问题,需要先从源码角度来理解ArrayMap的原理。

ArrayMap是Android专门针对内存优化而设计的,用于取代Java API中的HashMap数据结构。为了更进一步优化key是int类型的Map,Android再次提供效率更高的数据结构SparseArray,可避免自动装箱过程。对于key为其他类型则可使用ArrayMap。HashMap的查找和插入时间复杂度为O(1)的代价是牺牲大量的内存来实现的,而SparseArray和ArrayMap性能略逊于HashMap,但更节省内存。

接下来,从源码看看ArrayMap,为了全面解读,文章有点长,请耐心阅读。

二 源读ArrayMap

2.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; // 缓存数组的上限

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

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

ArrayMap对象的数据储存格式如图所示:

  • mHashes是一个记录所有key的hashcode值组成的数组,是从小到大的排序方式;
  • mArray是一个记录着key-value键值对所组成的数组,是mHashes大小的2倍;

在这里插入图片描述
其中mSize记录着该ArrayMap对象中有多少对数据,执行put()或者append()操作,则mSize会加1,执行remove(),则mSize会减1。mSize往往小于mHashes.length,如果mSize大于或等于mHashes.length,则说明mHashes和mArray需要扩容。

ArrayMap类有两个非常重要的静态成员变量mBaseCache和mTwiceBaseCacheSize,用于ArrayMap所在进程的全局缓存功能:

  • mBaseCache:用于缓存大小为4的ArrayMap,mBaseCacheSize记录着当前已缓存的数量,超过10个则不再缓存;
  • mTwiceBaseCacheSize:用于缓存大小为8的ArrayMap,mTwiceBaseCacheSize记录着当前已缓存的数量,超过10个则不再缓存。

为了减少频繁地创建和回收Map对象,ArrayMap采用了两个大小为10的缓存队列来分别保存大小为4和8的Map对象。为了节省内存有更加保守的内存扩张以及内存收缩策略。 接下来分别说说缓存机制和扩容机制。

2.2 缓存机制

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

2.2.1 freeArrays

private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
    if (hashes.length == (BASE_SIZE*2)) {  //当释放的是大小为8的对象
        synchronized (ArrayMap.class) {
            // 当大小为8的缓存池的数量小于10个,则将其放入缓存池
            if (mTwiceBaseCacheSize < CACHE_SIZE) { 
                array[0] = mTwiceBaseCache;  //array[0]指向原来的缓存池
                array[1] = hashes;
                for (int i=(size<<1)-1; i>=2; i--) {
                    array[i] = null;  //清空其他数据
                }
                mTwiceBaseCache = array; //mTwiceBaseCache指向新加入缓存池的array
                mTwiceBaseCacheSize++; 
            }
        }
    } else if (hashes.length == BASE_SIZE) {  //当释放的是大小为4的对象,原理同上
        synchronized (ArrayMap.class) {
            if (mBaseCacheSize < CACHE_SIZE) {
                array[0] = mBaseCache;
                array[1] = hashes;
                for (int i=(size<<1)-1; i>=2; i--) {
                    array[i] = null;
                }
                mBaseCache = array;
                mBaseCacheSize++;
            }
        }
    }
}

最初mTwiceBaseCache和mBaseCache缓存池中都没有数据,在freeArrays释放内存时,如果同时满足释放的array大小等于4或者8,且相对应的缓冲池个数未达上限,则会把该arrya加入到缓存池中。加入的方式是将数组array的第0个元素指向原有的缓存池,第1个元素指向hashes数组的地址,第2个元素以后的数据全部置为null。再把缓存池的头部指向最新的array的位置,并将该缓存池大小执行加1操作。具体如下所示。
在这里插入图片描述
freeArrays()触发时机:

  • 当执行removeAt()移除最后一个元素的情况
  • 当执行clear()清理的情况
  • 当执行ensureCapacity()在当前容量小于预期容量的情况下, 先执行allocArrays,再执行freeArrays
  • 当执行put()在容量满的情况下, 先执行allocArrays, 再执行freeArrays

2.2.2 allocArrays

private void allocArrays(final int size) {
    if (size == (BASE_SIZE*2)) {  //当分配大小为8的对象,先查看缓存池
        synchronized (ArrayMap.class) {
            if (mTwiceBaseCache != null) { // 当缓存池不为空时
                final Object[] array = mTwiceBaseCache; 
                mArray = array;         //从缓存池中取出mArray
                mTwiceBaseCache = (Object[])array[0]; //将缓存池指向上一条缓存地址
                mHashes = (int[])array[1];  //从缓存中mHashes
                array[0] = array[1] = null;
                mTwiceBaseCacheSize--;  //缓存池大小减1
                return;
            }
        }
    } else if (size == BASE_SIZE) { //当分配大小为4的对象,原理同上
        synchronized (ArrayMap.class) {
            if (mBaseCache != null) {
                final Object[] array = mBaseCache;
                mArray = array;
                mBaseCache = (Object[])array[0];
                mHashes = (int[])array[1];
                array[0] = array[1] = null;
                mBaseCacheSize--;
                return;
            }
        }
    }
    
    // 分配大小除了4和8之外的情况,则直接创建新的数组
    mHashes = new int[size];
    mArray = new Object[size<<1];
}

当allocArrays分配内存时,如果所需要分配的大小等于4或者8,且相对应的缓冲池不为空,则会从相应缓存池中取出缓存的mArray和mHashes。从缓存池取出缓存的方式是将当前缓存池赋值给mArray,将缓存池指向上一条缓存地址,将缓存池的第1个元素赋值为mHashes,再把mArray的第0和第1个位置的数据置为null,并将该缓存池大小执行减1操作,具体如下所示。
在这里插入图片描述
allocArrays触发时机:

  • 当执行ArrayMap的构造函数的情况
  • 当执行removeAt()在满足容量收紧机制的情况
  • 当执行ensureCapacity()在当前容量小于预期容量的情况下, 先执行allocArrays,再执行freeArrays
  • 当执行put()在容量满的情况下, 先执行allocArrays, 再执行freeArrays

这里需要注意的是只有大小为4或者8的内存分配才有可能从缓存池取数据,因为freeArrays过程放入缓存池的大小只有4或8,对于其他大小的内存分配则需要创建新的数组。 优化小技巧,对于分配数据不超过8的对象的情况下,一定要创建4或者8大小,否则浪费了缓存机制。比如ArrayMap[7]就是不友好的写法,建议写成ArrayMap[8]。

2.3 扩容机制

2.3.1 容量扩张

public V put(K key, V value) {
    ...
    final int osize = mSize;
    if (osize >= mHashes.length) { //当mSize大于或等于mHashes数组长度时需要扩容
        final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))
                : (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
        allocArrays(n);  //分配更大的内存【小节2.2.2】
    }
    ...
}

当mSize大于或等于mHashes数组长度时则扩容,完成扩容后需要将老的数组拷贝到新分配的数组,并释放老的内存。

  • 当map个数满足条件 osize<4时,则扩容后的大小为4;
  • 当map个数满足条件 4<= osize < 8时,则扩容后的大小为8;
  • 当map个数满足条件 osize>=8时,则扩容后的大小为原来的1.5倍;

可见ArrayMap大小在不断增加的过程,size的取值一般情况依次会是4,8,12,18,27,40,60,…

这篇关于ArrayMap 原理的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!