这篇文章主要介绍“java中ArrayList与HashSet的contains方法性能比较”,在日常操作中,相信很多人在java中ArrayList与HashSet的contains方法性能比较问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”java中ArrayList与HashSet的contains方法性能比较”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!
在日常开发中,ArrayList
和HashSet
都是Java中很常用的集合类。
ArrayList
是List
接口最常用的实现类;
HashSet
则是保存唯一元素Set
的实现。
本文主要对两者共有的方法contains()
做一个简单的讨论,主要是性能上的对比,并用JMH(ava Microbenchmark Harness)
进行测试比较。
我们使用一个由OpenJDK/Oracle里面开发了Java编译器的大牛们所开发的Micro Benchmark Framework
来测试。下面简单展示一下使用过程。
导入JMH
的相关依赖,可以去官网查看最新版本:
<dependencies> <dependency> <groupId>org.openjdk.jmh</groupId> <artifactId>jmh-core</artifactId> <version>${openjdk.jmh.version}</version> </dependency> <dependency> <groupId>org.openjdk.jmh</groupId> <artifactId>jmh-generator-annprocess</artifactId> <version>${openjdk.jmh.version}</version> </dependency> </dependencies> <properties> <openjdk.jmh.version>1.19</openjdk.jmh.version> </properties>
因为要测试集合类的方法,所以我们创建一个类来表示集合所储存的对象。如下:
@Data @AllArgsConstructor(staticName = "of") public class Student { private Long id; private String name; }
接下来我们就来写测试性能对比的类,代码如下:
@BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.NANOSECONDS) public class ContainsPerformanceTest { @State(Scope.Thread) public static class MyState { private Set<Student> studentSet = new HashSet<>(); private List<Student> studentList = new ArrayList<>(); private Student targetStudent = Student.of(99L, "Larry"); @Setup(Level.Trial) public void prepare() { long MAX_COUNT = 10000; for (long i = 0; i < MAX_COUNT; i++) { studentSet.add(Student.of(i, "MQ")); studentList.add(Student.of(i, "MQ")); } studentList.add(targetStudent); studentSet.add(targetStudent); } } @Benchmark public boolean arrayList(MyState state) { return state.studentList.contains(state.targetStudent); } @Benchmark public boolean hashSet(MyState state) { return state.studentSet.contains(state.targetStudent); } public static void main(String[] args) throws Exception { Options options = new OptionsBuilder() .include(ContainsPerformanceTest.class.getSimpleName()) .threads(6) .forks(1) .warmupIterations(3) .measurementIterations(6) .shouldFailOnError(true) .shouldDoGC(true) .build(); new Runner(options).run(); } }
测试类注解说明:
@BenchmarkMode:表示进行Benchmark时使用的模式;AverageTime
表示测试调用的平均时间。
@OutputTimeUnit:测试的度量时间单位;NANOSECONDS
表示使用纳秒为单位。
@State:接受一个Scope
参数表示状态的共享范围;Scope.Thread
表示每个线程独享。
@Setup:执行Benchmark前执行,类似于JUnit
的@BeforeAll
。
@Benchmark:进行Benchmark的对象,类似于JUnit
的@Test
。
测试类启动参数Options
说明:
include:benchmark所在的类名;
threads:每个进程中的测试线程数;
fork:进程数,如果为3,则JMH会fork出3个进程来测试;
warmupIterations:预热的迭代次数,
measurementIterations:实际测量的迭代次数。
设置好参数后,就可以跑测试了。测试结果如下:
# Benchmark: ContainsPerformanceTest.arrayList # Run progress: 0.00% complete, ETA 00:00:18 # Fork: 1 of 1 # Warmup Iteration 1: 42530.408 ±(99.9%) 2723.999 ns/op # Warmup Iteration 2: 17841.988 ±(99.9%) 1882.026 ns/op # Warmup Iteration 3: 18561.513 ±(99.9%) 2021.506 ns/op Iteration 1: 18499.568 ±(99.9%) 2126.172 ns/op Iteration 2: 18975.407 ±(99.9%) 2004.509 ns/op Iteration 3: 19386.851 ±(99.9%) 2248.536 ns/op Iteration 4: 19279.722 ±(99.9%) 2102.846 ns/op Iteration 5: 19796.495 ±(99.9%) 1974.987 ns/op Iteration 6: 21363.962 ±(99.9%) 2175.961 ns/op Result "ContainsPerformanceTest.arrayList": 19550.334 ±(99.9%) 2771.595 ns/op [Average] (min, avg, max) = (18499.568, 19550.334, 21363.962), stdev = 988.377 CI (99.9%): [16778.739, 22321.929] (assumes normal distribution) # Benchmark: ContainsPerformanceTest.hashSet # Run progress: 50.00% complete, ETA 00:00:16 # Fork: 1 of 1 # Warmup Iteration 1: 10.662 ±(99.9%) 0.209 ns/op # Warmup Iteration 2: 11.177 ±(99.9%) 1.077 ns/op # Warmup Iteration 3: 9.467 ±(99.9%) 1.462 ns/op Iteration 1: 9.540 ±(99.9%) 0.535 ns/op Iteration 2: 9.388 ±(99.9%) 0.365 ns/op Iteration 3: 10.604 ±(99.9%) 1.008 ns/op Iteration 4: 9.361 ±(99.9%) 0.154 ns/op Iteration 5: 9.366 ±(99.9%) 0.458 ns/op Iteration 6: 9.274 ±(99.9%) 0.237 ns/op Result "ContainsPerformanceTest.hashSet": 9.589 ±(99.9%) 1.415 ns/op [Average] (min, avg, max) = (9.274, 9.589, 10.604), stdev = 0.505 CI (99.9%): [8.174, 11.004] (assumes normal distribution) # Run complete. Total time: 00:00:32 Benchmark Mode Cnt Score Error Units ContainsPerformanceTest.arrayList avgt 6 19550.334 ± 2771.595 ns/op ContainsPerformanceTest.hashSet avgt 6 9.589 ± 1.415 ns/op
经过测试,发现两者耗时差异极大,ArrayList
大概是20K纳秒,而HashSet
则10纳秒左右。两者完全不在一个数量级上。
通过测试得知两者差异极大,就小窥一下源码分析分析。
ArrayList
的底层使用数组作为数据存储,当给定一个Object
去判断是否存在,需要去遍历数组,与每个元素对比。
public boolean contains(Object o) { return indexOf(o) >= 0; } public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) if (elementData[i]==null) return i; } else { for (int i = 0; i < size; i++) if (o.equals(elementData[i])) return i; } return -1; }
从源码可以发现,contains()
方法是通过调用indexOf()
来判断的,而后者就是需要遍历数组,直到找到那个与入参相等的元素才会停止。因为,ArrayList
的contains()
方法的时间复杂度为O(n),也就是说,时间取决于长度,而且是正比的关系。
HashSet
底层是通过HashMap
来实现的,而HashMap
的底层结构为数组+链表,JDK 8
后改为数组+链表+红黑树。
HashMap
的相关代码如下:
public boolean containsKey(Object key) { return getNode(hash(key), key) != null; } final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }
首先通过获取Hash值来找,如果Hash值相等且对象也相等,则找到。一般来说,在hashCode()
方法实现没问题的情况下,发生Hash冲突的情况是比较少。所以可以认为,大部分情况下,contains()
的时间复杂度为O(1),元素个数不影响其速度。如果发生Hash冲突,在链表长度小于8时,时间复杂度为O(n);在链表大于8时,转化为红黑树,时间复杂度为O(logn)。
一般地,我们认为,HashSet/HashMap
的查找的时间复杂度为O(1)。
通过JMH
测试我们发现ArrayList
和HashSet
的contains()
方法性能差异很大。经过源码分析得知,ArrayList
对应的时间复杂度为O(n),而HashSet
的时间度为O(1)。
到此,关于“java中ArrayList与HashSet的contains方法性能比较”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注亿速云网站,小编会继续努力为大家带来更多实用的文章!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。