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更多相关文章
- ANDROID源代码结构
- Android 应用程序结构介绍
- Android ListView元素间隙线自定义渐变效果
- Android必备:Android项目的目录结构
- 移动web在ios和android下点击元素出现阴影问题
- Android系统的体系结构、开发语言及源码结构
- 浅析Android位置权限以及数组寻找索引的坑