HashMap,ArrayMap,SparseArray源码分析及性能比照

作者 : 开心源码 本文共4221个字,预计阅读时间需要11分钟 发布时间: 2022-05-14 共136人阅读

ArrayMap及SparseArray是android的系统API,是专门为移动设施而定制的。用于在肯定情况下取代HashMap而达到节省内存的目的。

一.源码分析(因为篇幅限制,源码分析部分会放在单独的文章中)
二.实现原理及数据结构比照
三.性能测试比照
四.总结

一.源码分析
稍后会在下一篇文章中补充(都写在一篇,篇幅太长了)

二.实现原理及数据结构比照
1. hashMap

Paste_Image.png

从hashMap的结构中可以看出,首先对key值求hash,根据hash结果确定在table数组中的位置,当出现哈希冲突时采用开放链地址法进行解决。Map.Entity的数据结构如下:

static class HashMapEntry<K, V> implements Entry<K, V> {    final K key;    V value; final int hash;    HashMapEntry<K, V> next;}   

具体的hashmap源码细节会在其余文章中进行分析,这里可以看出来的是,从空间的角度分析,HashMap中会有一个利用率不超过负载因子(默认为0.75)的table数组,其次,对于HashMap的每一条数据都会用一个HashMapEntry进行记录,除了记录key,value外,还会记录下hash值,及下一个entity的指针。
时间效率方面,利用hash算法,插入和查找等操作都很快,且一般情况下,每一个数组值后面不会存在很长的链表(由于出现hash冲突毕竟占比较小的比例),所以不考虑空间利用率的话,HashMap的效率非常高。

2.ArrayMap

Paste_Image.png

ArrayMap利用两个数组,mHashes用来保存每一个key的hash值,mArrray大小为mHashes的2倍,依次保存key和value。源码的细节方面会在下一篇文章中说明。现在我们先抛开细节部分,只看关键语句:

mHashes[index] = hash;mArray[index<<1] = key;mArray[(index<<1)+1] = value;

相信看到这大家都明白了原理了。但是它怎样查询呢?答案是二分查找。当插入时,根据key的hashcode()方法得到hash值,计算出在mArrays的index位置,而后利用二分查找找到对应的位置进行插入,当出现哈希冲突时,会在index的相邻位置插入。
总结一下,空间角度考虑,ArrayMap每存储一条信息,需要保存一个hash值,一个key值,一个value值。比照下HashMap 粗略的看,只是减少了一个指向下一个entity的指针。还有就是节省了一部分可见空间上的内存节省也不是特别显著。是不是这样呢?后面会验证。
时间效率上看,插入和查找的时候由于都用的二分法,查找的时候应该是没有hash查找快,插入的时候呢,假如顺序插入的话效率一定高,但假如是随机插入,一定会涉及到大量的数组搬移,数据量大,一定不行,再想一下,假如是不恰巧,每次插入的hash值都比上一次的小,那就得次次搬移,效率一下就扛不住了的感脚。

3.SparseArray

Paste_Image.png

sparseArray相对来说就简单的多了,但是不要以为它可以取代前两种,sparseArray只能在key为int的时候才能使用,注意是int而不是Integer,这也是sparseArray效率提升的一个点,去掉了装箱的操作!
由于key为int也就不需要什么hash值了,只需int值相等,那就是同一个对象,简单粗暴。插入和查找也是基于二分法,所以原理和Arraymap基本一致,这里就不多说了。
总结一下:空间上比照,与HashMap,去掉了Hash值的存储空间,没有next的指针占用,还有其余少量小的内存占用,看着节省了不少。
时间上比照:插入和查找的情形和Arraymap基本一致,可能存在大量的数组搬移。但是它避免了装箱的环节,不要小看装箱过程,还是很费时的。所以从源码上来看,效率谁快,就看数据量大小了。

好啦,说半天都是分析,下面来点实际的,用数据说话!

三.性能测试比照
我们从插入和查询两方面来比对试试看。

1.插入性能时间比照
测试代码:

long start = System.currentTimeMillis();Map<Integer, String> hash = new HashMap<Integer, String>();for (int i = 0; i < MAX; i++) {    hash.put(i, i+"");}long ts = System.currentTimeMillis() - start;

就贴这一段吧,其余两段代码无非就是把HashMap换掉,通过改变Max值就行比照。

Paste_Image.png

分析:从结果上来看,数据量小的时候,差异并不大(当然了,数据量小,时间基准小,内容太多,就不贴数据表了,的确差异不大),当数据量大于5000左右,SparseArray,最快,HashMap最慢,乍一看,如同SparseArray是最快的,但是要注意,这是顺序插入的。也就是SparseArray和Arraymap最理想的情况。

来个逆序插入的试试

long start = System.currentTimeMillis();HashMap<Integer, String> hash = new HashMap<Integer, String>();for (int i = 0; i < MAX; i++) {    hash.put(MAX-1-i, i+"");}long ts = System.currentTimeMillis() - start;

Paste_Image.png

分析:从结果上来看,果然,HashMap远超Arraymap和SparseArray,也前面分析一致。
当然了,数据量小的时候,例如1000以下,这点时间差异也是可以忽略的。

下面来看看空间比照:先说一下测试方法,由于测试内存,所以尤其要注意的一点,就是测试的过程不要发生GC,假如发生了GC,那数据就不准了,想了想,用了个比较简单的方法:

Runtime.getRuntime().totalMemory()//获取应用已经申请到的总的内存
Runtime.getRuntime().freeMemory()//获取应用内存的free部分

两个方法的差值就是应用已经使用的内存部分。

Paste_Image.png

值得注意的是当MAX值很大的时候,可能在代码执行过程发生GC,此时可以同时用Android Monitor的Memory窗口监视内存,没有发生gc的过程结果才有效。假设数据量比较大的时候,每测完一次手动GC一次,这样基本上每次都能测试成功;由于数据量也不是特别大,只有很少一部分情况测试过程会发生GC,所以也没有去进一步探索其余方式,比方设置虚拟机参数来延长GC时间,有空了可以搞一下。上数据:

Paste_Image.png

可见,SparseArray在内存占用方面确实要优于HashMap和ArrayMap不少,通过数据观察,大致节省30%左右,而ArrayMap的体现正如前面说的,优化作用有限,几乎和HashMap相同。

2.查找性能比照

long start = System.currentTimeMillis();    SparseArray<String> hash = new SparseArray<String>();for (int i = 0; i < MAX; i++) {    hash.get(i);}long ts = System.currentTimeMillis() - start;

Paste_Image.png

发现SparseArray比HashMap要快,和前面假设的不符,二分查找难道比Hash快?
再一想,由于用这样的代码测试有点不公平,由于SparseArray没有装箱,HashMap有个装箱的过程,似乎不太公平。那么想个办法再来测试下,

ArrayList<IntEntity> intEntityList=new ArrayList<IntEntity>();private void boxing(){    for(int i=0;i<MAX;i++){        IntEntity entity=new IntEntity();        entity.i1=i;            entity.i2=Integer.valueOf(i);        intEntityList.add(entity);    }}class IntEntity{     int i1;    Integer i2;}

给HashMap和ArrayMap的时候给它提前装箱,这样似乎公平些。

long start = System.currentTimeMillis();HashMap<Integer, String> hash = new HashMap<Integer, String>();for (int i = 0; i < MAX; i++) {  //  hash.get(i);   hash.get(intEntityList.get(i).i2);}long ts = System.currentTimeMillis() - start;

Paste_Image.png

果然结果不一样了,HashMap才是查询最快的,这才符合逻辑嘛,但是我们正常用的时候是不论装不装箱的,所以综合起来还是使用SparseArray效率最高。

扯了这么多,终于到了该总结的时候了。
四、总结
1.在数据量小的时候一般认为1000以下,当你的key为int的时候,使用SparseArray的确是一个很不错的选择,内存大概能节省30%,相比用HashMap,由于它key值不需要装箱,所以时间性能平均来看也优于HashMap,建议使用!
2.ArrayMap相对于SparseArray,特点就是key值类型不受限,任何情况下都可以取代HashMap,但是通过研究和测试发现,ArrayMap的内存节省并不显著,也就在10%左右,但是时间性能确是最差的,当然了,1000以内的数据量也无所谓了,加上它只有在API>=19才可以使用,个人建议没必要使用!还不如用HashMap放心。预计这也是为什么我们再new一个HashMap的时候google也没有提醒让我们使用的起因吧。

目前本人在公司负责热修复相关的工作,主要是基于robust的热修复相关工作。感兴趣的同学欢迎进群交流。

image.png

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » HashMap,ArrayMap,SparseArray源码分析及性能比照

发表回复