ArrayMap是如何提高内存的使用效率的？

系列文章地址：
Android容器类-ArraySet原理解析(一)
Android容器类-ArrayMap原理解析(二)
Android容器类-SparseArray原理解析(三)
Android容器类-SparseIntArray原理解析(四)

ArraySet使用数组保存数据，提高了内存的使用效率，在数据量不超过1000时，相较于HashSet，效率最多不会降低50%，本节来分析下ArraySet 添加和删除元素分析，谷歌指出ArrayMap的设计也是为了更加高效地使用内存，在数据量不超过1000时，效率最多不会降低50%。阅读原码可以发现，ArrayMap和ArraySet在实现上保持了统一，主要的不同是元素的存储方式。

继承结构

可以看到，ArrayMap的继承结构比较简单，只是实现了Map接口。

存储结构

可以回忆一下ArraySet的存储结构：一个int类型的数组mHashes存储hash值，一个object类型的数组mArray存储内容，这两个数组的下标一一对应。

ArrayMap的存储结构猜想应该和ArraySet不一样，因为ArrayMap不仅仅需要存储value，还需要存储key，Google的大神们是怎样解决这个问题的呢？

Google的大神们还是使用了和ArraySet一样的数据结构，在存储key和value时设计了一个非常巧妙的方法。

如上图所示，mHashes中存储了key的hash值，key在mHashes的下标为index，在mArray中，mArray[index<<1]存储key，mArray[index<<1 + 1]存储value。故mArray的长度是mHashes的2倍。这样的设计使的ArraySet和ArrayMap在存储结构上保持了统一。

添加和删除

ArraySet和ArrayMap在实现上保持了统一，阅读原码可以发现，他们拥有同样的缓存结构，删除和添加元素时会有相同的逻辑流程。大致看下HashMap的存储结构上图是HashMap的存储结构，每个链表后面的元素的数量没有达到将链表树化的数目。HashMap在存储k-v键值对的时候，首先根据k的hash值找到k-v存储的链表数组的下标，然后将k-v键值对存储在链表的最后。
ArrayMap使用两个一维数组分别存储k的hash值和k-v键值对。添加元素时根据k查找元素以确认元素是否已经存在，如果已经存在则直接更新，否则添加；删除元素时查找元素以确定元素是否存在，如果不存在则直接返回，否则删除元素。ArrayMap在添加删除元素的过程中，也会涉及到元素的移动，缓存的添加和删除。整个流程和ArraySet相同。但是需要注意的是，ArrayMap在添加和删除元素的过程中，存储k-v键值对mArray数组需要同时修改k和v两个元素。

元素查找

经过上面的分析，可能发现了一个问题，ArrayMap和ArraySet太相似了。确实是，他们在底层存储结构，缓存结构都是一样的。添加和删除元素的时候，需要查找元素，添加元素时根据k查找元素以确认元素是否已经存在，如果已经存在则直接更新，否则添加；删除元素时查找元素以确定元素是否存在，如果不存在则直接返回，否则删除元素。ArrayMap是否和ArraySet具有相同的查找过程呢。直接上源码：

    int indexOf(Object key, int hash) {        final int N = mSize;        // Important fast case: if nothing is in here, nothing to look for.        if (N == 0) {            return ~0;        }        int index = binarySearchHashes(mHashes, N, hash);        // If the hash code wasn't found, then we have no entry for this key.        if (index < 0) {            return index;        }        // If the key at the returned index matches, that's what we want.        if (key.equals(mArray[index<<1])) {            return index;        }        // Search for a matching key after the index.        int end;        for (end = index + 1; end < N && mHashes[end] == hash; end++) {            if (key.equals(mArray[end << 1])) return end;        }        // Search for a matching key before the index.        for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {            if (key.equals(mArray[i << 1])) return i;        }        // Key not found -- return negative value indicating where a        // new entry for this key should go.  We use the end of the        // hash chain to reduce the number of array entries that will        // need to be copied when inserting.        return ~end;    }            private static int binarySearchHashes(int[] hashes, int N, int hash) {        try {            return ContainerHelpers.binarySearch(hashes, N, hash);        } catch (ArrayIndexOutOfBoundsException e) {            if (CONCURRENT_MODIFICATION_EXCEPTIONS) {                throw new ConcurrentModificationException();            } else {                throw e; // the cache is poisoned at this point, there's not much we can do            }        }    }

以上为indexOf函数和binarySearchHashes函数的实现。通过对比源码，可以发现，ArrayMap和ArraySet使用了相同的二分查找逻辑，可以肯定的，和ArraySet一样，ArrayMap在存储hash值时是有序的。具体的查找过程的分析可以参考ArraySet 添加和删除元素分析

不同点

上面的分析容易让人产生一种感觉ArraySet和ArrayMap的实现完全相同。这是一种误解，ArraySet和ArrayMap在实现的逻辑流程是相同的，但在细节处理上还是有不同。添加删除元素的过程中，不同点主要体现在在添加和删除元素的过程中，如果有其他操作改变了ArrayMap存储的内容的数量，则会抛出ConcurrentModificationException，ArrayMap中能改变存储容量的是以下三个方法：put、remove、clear

可以做一个小实验
首先，两个线程同时修改ArrayMap同一个key下的value

ArrayMap aMap = new ArrayMap<>();    aMap.put("key", "value");    new Thread(new Runnable() {                @Override        public void run() {            // TODO Auto-generated method stub            for (int i = 0 ; ; i++) {                aMap.put("key", "value" + i);            }        }    }).start();        new Thread(new Runnable() {                @Override        public void run() {            // TODO Auto-generated method stub            for (int i = 0 ; ; i++) {                aMap.put("key", "value" + i);            }        }    }).start();

运行后可以发现，程序会一直运行，也不会报错。

接下来看下两个线程同时向ArrayMap中添加元素

ArrayMap aMap = new ArrayMap<>();    new Thread(new Runnable() {                @Override        public void run() {            // TODO Auto-generated method stub            for (int i = 0 ; ; i++) {                aMap.put("key" + i, "value" + i);            }        }    }).start();        new Thread(new Runnable() {                @Override        public void run() {            // TODO Auto-generated method stub            for (int i = 0 ; ; i++) {                aMap.put("key" + i, "value" + i);            }        }    }).start();

运行程序后，会报如下异常

Exception in thread "Thread-1" java.util.ConcurrentModificationExceptionat com.rock.collections.array.ArrayMap.put(ArrayMap.java:527)at com.rock.collections.Client$2.run(Client.java:50)at java.lang.Thread.run(Thread.java:748)

（我将ArrayMap抽出来进行测试，故显示的包名是我自定义的）
可以发现由于两个线程同时向aMap中添加了元素，修改了元素的数量，系统抛出了ConcurrentModificationException。

跟踪下添加元素的过程

 @Overridepublic V put(K key, V value) {    final int osize = mSize;    ......    index = ~index;    if (osize >= mHashes.length) {        // 数组扩容        final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))                : (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);        ......        allocArrays(n);        if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {            throw new ConcurrentModificationException();        }        ......    }    ......    if (CONCURRENT_MODIFICATION_EXCEPTIONS) {        if (osize != mSize || index >= mHashes.length) {            throw new ConcurrentModificationException();        }    }    mHashes[index] = hash;    mArray[index<<1] = key;    mArray[(index<<1)+1] = value;    mSize++;    return null;}

源码已经很清晰了，CONCURRENT_MODIFICATION_EXCEPTIONS = true，在添加元素之前，使用osize记录mSize，在扩容之后和最后添加元素之前会对当前元素的数量进行判断，如果发生了变化则抛出异常。

再跟踪下删除元素的过程

public V removeAt(int index) {    final int osize = mSize;    ......    if (osize <= 1) {        ......    } else {        nsize = osize - 1;        if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {            ......            if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {                throw new ConcurrentModificationException();            }            ......        } else {            ......        }    }    if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {        throw new ConcurrentModificationException();    }    mSize = nsize;    return (V)old;}

在缩容或者记录最终元素的数量之前，如果发现元素的数量被修改过，则抛出异常。这个地方还有一个要注意的，由于是删除元素，mSize最终是要发生变化的，但是源码中对比的mSize发生变化之前的值。

小结

ArrayMap的设计是为了更加高效地利用内存，高效体现在以下几点

ArrayMap使用更少的存储单元存储元素
ArrayMap使用int类型的数组存储hash，使用Object类型数组存储k-v键值对，相较于HashMap使用Node存储节点，ArrayMap存储一个元素占用的内存更小。
ArrayMap在扩容时容量变化更小
HashMap在扩容的时候，通常会将容量扩大一倍，而ArrayMap在扩容的时候，如果元素个数超过8，最多扩大自己的1/2。

虽然有以上有点，但是和ArraySet一样，ArrayMap也存在以下劣势：

存储大量（超过1000）元素时比较耗时
在对元素进行查找或者确定待插入元素的位置时使用二分查找，当元素较多时，耗时较长
频繁扩容和缩容，可能会产生大量复制操作
ArrayMap在扩容和缩容时需要移动元素，且扩容时容量变化比HashMap小，扩容和缩容的频率可能更高，元素数量过多时，元素的移动可能会对性能产生影响。

基于以上优缺点，google给出的建议是当元素数量小于1000时，建议使用Array代替HashMap，效率降低最多不会超过50%

关注微信公众号，最新技术干货实时推送

image

继承结构

存储结构

添加和删除

元素查找

不同点

小结

关注微信公众号，最新技术干货实时推送

更多相关文章

随机推荐