java中ArrayList与HashSet的contains方法性能比较
这篇文章主要介绍“java中ArrayList与HashSet的contains方法性能比较”，在日常操作中，相信很多人在java中ArrayList与HashSet的contains方法性能比较问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”java中ArrayList与HashSet的contains方法性能比较”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！
创新互联建站长期为成百上千客户提供的网站建设服务，团队从业经验10年，关注不同地域、不同群体，并针对不同对象提供差异化的产品和服务；打造开放共赢平台，与合作伙伴共同营造健康的互联网生态环境。为修水企业提供专业的成都网站设计、成都做网站、外贸网站建设，修水网站改版等技术服务。拥有10多年丰富建站经验和众多成功案例,为您定制开发。
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的相关依赖，可以去官网查看最新版本：
org.openjdk.jmh jmh-core ${openjdk.jmh.version} org.openjdk.jmh jmh-generator-annprocess ${openjdk.jmh.version} 1.19
2.2 创建测试相关的类
2.2.1 集合储存对象的类
因为要测试集合类的方法，所以我们创建一个类来表示集合所储存的对象。如下：
@Data
@AllArgsConstructor(staticName = "of")
public class Student {
private Long id;
private String name;
}2.2.2 JMH测试类
接下来我们就来写测试性能对比的类，代码如下：
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class ContainsPerformanceTest {
@State(Scope.Thread)
public static class MyState {
private Set studentSet = new HashSet<>();
private List 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：实际测量的迭代次数。
2.3 测试结果
设置好参数后，就可以跑测试了。测试结果如下：
# 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纳秒左右。两者完全不在一个数量级上。
3 源码分析
通过测试得知两者差异极大，就小窥一下源码分析分析。
3.1 ArrayList的contains()
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)，也就是说，时间取决于长度，而且是正比的关系。
3.2 HashSet的contains()
HashSet底层是通过HashMap来实现的，而HashMap的底层结构为数组+链表，JDK 8后改为数组+链表+红黑树。
HashMap的相关代码如下：
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
final Node getNode(int hash, Object key) {
Node[] tab; Node 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)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)。
4 总结
通过JMH测试我们发现ArrayList和HashSet的contains()方法性能差异很大。经过源码分析得知，ArrayList对应的时间复杂度为O(n)，而HashSet的时间度为O(1)。
到此，关于“java中ArrayList与HashSet的contains方法性能比较”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注创新互联网站，小编会继续努力为大家带来更多实用的文章！
当前标题：java中ArrayList与HashSet的contains方法性能比较
URL地址：http://scyanting.com/article/iggdjh.html
