1 简介
在日常开发中,ArrayList 和HashSet 都是Java中很常用的聚集类。
ArrayList 是List 接口最常用的实现类;
HashSet 则是生存唯一元素Set 的实现。
本文主要对两者共有的方法contains() 做一个简朴的讨论,主要是性能上的对比,并用JMH(ava Microbenchmark Harness) 举行测试比较。
2 先看JMH测试结果
我们使用一个由OpenJDK/Oracle里面开发了Java编译器的大牛们所开发的Micro Benchmark Framework 来测试。下面简朴展示一下使用过程。
2.1 Maven导入相关依赖
导入JMH 的相关依赖,可以去官网查察最新版本: - <code><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></code>
复制代码2.2 创建测试相关的类
2.2.1 聚集储存对象的类
由于要测试聚集类的方法,以是我们创建一个类来表示聚集所储存的对象。如下: - <code>@Data
- @AllArgsConstructor(staticName = "of")
- public class Student {
- private Long id;
- private String name;
- }</code>
复制代码2.2.2 JMH测试类
接下来我们就来写测试性能对比的类,代码如下: - <code>@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();
- }
- }</code>
复制代码测试类注解阐明:
- @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:现实丈量的迭代次数。
2.3 测试结果
设置好参数后,就可以跑测试了。测试结果如下: - <code># 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</code>
复制代码颠末测试,发现两者耗时差异极大,ArrayList 大概是20K纳秒,而HashSet 则10纳秒左右。两者完全不在一个数目级上。
3 源码分析
通过测试得知两者差异极大,就小窥一下源码分析分析。
3.1 ArrayList的contains()
ArrayList 的底层使用数组作为数据存储,当给定一个Object 去判定是否存在,需要去遍历数组,与每个元素对比。
- <code>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;
- }</code>
复制代码从源码可以发现,contains() 方法是通过调用indexOf() 来判定的,而后者就是需要遍历数组,直到找到那个与入参相等的元素才会制止。由于,ArrayList 的contains() 方法的时间复杂度为O(n),也就是说,时间取决于长度,而且是正比的关系。
3.2 HashSet的contains()
HashSet 底层是通过HashMap 来实现的,而HashMap 的底层结构为数组+链表,JDK 8 后改为数组+链表+红黑树。
HashMap 的相关代码如下:
- <code>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;
- }</code>
复制代码首先通过获取Hash值来找,如果Hash值相等且对象也相等,则找到。一样平常来说,在hashCode() 方法实现没问题的情况下,发生Hash冲突的情况是比较少。以是可以以为,大部分情况下,contains() 的时间复杂度为O(1),元素个数不影响其速率。如果发生Hash冲突,在链表长度小于8时,时间复杂度为O(n);在链表大于8时,转化为红黑树,时间复杂度为O(logn)。
一样平常地,我们以为,HashSet/HashMap 的查找的时间复杂度为O(1)。
4 总结
通过JMH 测试我们发现ArrayList 和HashSet 的contains() 方法性能差异很大。颠末源码分析得知,ArrayList 对应的时间复杂度为O(n),而HashSet 的时间度为O(1)。
接待关注公众号<南瓜慢说>,将持续为你更新...
来源:https://www.cnblogs.com/larrydpk/p/11729208.html |