java中ArrayList与HashSet的contains方法性能比较


这篇文章主要介绍“java中ArrayList与HashSet的contains方法性能比较”,在日常操作中,相信很多人在java中ArrayList与HashSet的contains方法性能比较问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”java中ArrayList与HashSet的contains方法性能比较”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!在日常开发中,ArrayListHashSet都是Java中很常用的集合类。ArrayListList接口最常用的实现类;HashSet则是保存唯一元素Set的实现。本文主要对两者共有的方法contains()做一个简单的讨论,主要是性能上的对比,并用JMH(ava Microbenchmark Harness)进行测试比较。我们使用一个由OpenJDK/Oracle里面开发了Java编译器的大牛们所开发的Micro Benchmark Framework测试。下面简单展示一下使用过程。导入JMH的相关依赖,可以去官网查看最新版本:因为要测试集合类的方法,所以我们创建一个类来表示集合所储存的对象。如下:接下来我们就来写测试性能对比的类,代码如下:测试类注解说明:@BenchmarkMode:表示进行Benchmark时使用的模式;AverageTime表示测试调用的平均时间。@OutputTimeUnit:测试的度量时间单位;NANOSECONDS表示使用纳秒为单位。@State:接受一个Scope参数表示状态的共享范围;Scope.Thread表示每个线程独享。@Setup:执行Benchmark前执行,类似于JUn 香港云主机it@BeforeAll。@Benchmark:进行Benchmark的对象,类似于JUnit@Test。测试类启动参数Options说明:include:benchmark所在的类名;threads:每个进程中的测试线程数;fork:进程数,如果为3,则JMH会fork出3个进程来测试;warmupIterations:预热的迭代次数,measurementIterations:实际测量的迭代次数。设置好参数后,就可以跑测试了。测试结果如下:经过测试,发现两者耗时差异极大,ArrayList大概是20K纳秒,而HashSet则10纳秒左右。两者完全不在一个数量级上。通过测试得知两者差异极大,就小窥一下源码分析分析。ArrayList的底层使用数组作为数据存储,当给定一个Object去判断是否存在,需要去遍历数组,与每个元素对比。从源码可以发现,contains()方法是通过调用indexOf()来判断的,而后者就是需要遍历数组,直到找到那个与入参相等的元素才会停止。因为,ArrayListcontains()方法的时间复杂度为O(n),也就是说,时间取决于长度,而且是正比的关系。HashSet底层是通过HashMap来实现的,而HashMap的底层结构为数组+链表JDK 8后改为数组+链表+红黑树HashMap的相关代码如下:首先通过获取Hash值来找,如果Hash值相等且对象也相等,则找到。一般来说,在hashCode()方法实现没问题的情况下,发生Hash冲突的情况是比较少。所以可以认为,大部分情况下,contains()的时间复杂度为O(1),元素个数不影响其速度。如果发生Hash冲突,在链表长度小于8时,时间复杂度为O(n);在链表大于8时,转化为红黑树,时间复杂度为O(logn)。一般地,我们认为,HashSet/HashMap的查找的时间复杂度为O(1)。通过JMH测试我们发现ArrayListHashSetcontains()方法性能差异很大。经过源码分析得知,ArrayList对应的时间复杂度为O(n),而HashSet的时间度为O(1)。到此,关于“java中ArrayList与HashSet的contains方法性能比较”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注开发云网站,小编会继续努力为大家带来更多实用的文章!

相关推荐: 浏览器中Internet选项打不开怎么办

小编给大家分享一下浏览器中Internet选项打不开怎么办,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!1、按win+r键,打开运行对话框,输入“gpedit.msc”,回车打开组策…

免责声明:本站发布的图片视频文字,以转载和分享为主,文章观点不代表本站立场,本站不承担相关法律责任;如果涉及侵权请联系邮箱:360163164@qq.com举报,并提供相关证据,经查实将立刻删除涉嫌侵权内容。

(0)
打赏 微信扫一扫 微信扫一扫
上一篇 07/29 22:08
下一篇 07/29 22:08

相关推荐