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

avatar
Android @奇舞团Android团队

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

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

继承结构

可以看到,```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```在存储结构上保持了统一。

添加和删除

ArraySetArrayMap在实现上保持了统一,阅读原码可以发现,他们拥有同样的缓存结构,删除和添加元素时会有相同的逻辑流程。大致看下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两个元素。

元素查找

经过上面的分析,可能发现了一个问题,ArrayMapArraySet太相似了。确实是,他们在底层存储结构,缓存结构都是一样的。添加和删除元素的时候,需要查找元素,添加元素时根据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函数的实现。通过对比源码,可以发现,ArrayMapArraySet使用了相同的二分查找逻辑,可以肯定的,和ArraySet一样,ArrayMap在存储hash值时是有序的。具体的查找过程的分析可以参考ArraySet 添加和删除元素分析

不同点

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

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

ArrayMap<String, String> 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<String, String> 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.ConcurrentModificationException
at 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

跟踪下添加元素的过程

 @Override
public 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%

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