ArrayList到HashSet的一次优化
一、前言
最近共事分享了一次遍历List判断元素是否存在的优化技巧，亲自试验的一波，还是很nb。
（一）本地试验后果
1. 环境信息
- jdk1.8
- 测试工具：JMH 1.22
- 测试机器：mbp 16C32G
2. 测试后果
在同样10000个元素数量的状况下进行蕴含判断，HashSet比ArrayList快了约7660多倍。尽管试验之前晓得HashSet必定比ArrayList性能快，然而后果还是有点超出预期。
* 测试后果（依照吞吐量来测试）： * Benchmark Mode Cnt Score Error Units * perfTuning.TestListAndHashSet.checkArrayListWithContains thrpt 5 24.929 ± 9.703 ops/ms * perfTuning.TestListAndHashSet.checkArrayListWithIndex thrpt 5 25.505 ± 1.811 ops/ms * perfTuning.TestListAndHashSet.checkArrayListWithIterator thrpt 5 23.496 ± 3.172 ops/ms * perfTuning.TestListAndHashSet.checkHashSet thrpt 5 191505.153 ± 9573.444 ops/ms二、测试代码
（一）测试源码
- 这边思考了极其状况，待判断的元素默认放在了最初。
/** * @Author: allen * @Date: 2022/2/16 5:45 下午 * @Description: 比照ArrayList和HashSet各种场景下判断元素是否存在的性能状况 * * 测试后果： * Benchmark Mode Cnt Score Error Units * perfTuning.TestListAndHashSet.checkArrayListWithContains thrpt 5 24.929 ± 9.703 ops/ms * perfTuning.TestListAndHashSet.checkArrayListWithIndex thrpt 5 25.505 ± 1.811 ops/ms * perfTuning.TestListAndHashSet.checkArrayListWithIterator thrpt 5 23.496 ± 3.172 ops/ms * perfTuning.TestListAndHashSet.checkHashSet thrpt 5 191505.153 ± 9573.444 ops/ms */@State(Scope.Benchmark)public class TestListAndHashSet { public static final HashSet<String> hashSet = new HashSet<String>(); public static final ArrayList<String> arrayList = new ArrayList<String>(); /** * 构建测试汇合HashSet和ArrayList，都寄存10001个元素，并将待判断元素增加至尾部 */ @Setup(Level.Trial) public void init() { for (int i = 0; i < 10000; i++) { hashSet.add(UuidUtil.getStrUuid()); } hashSet.add("hashSet-test"); for (int i = 0; i < 10000; i++) { arrayList.add(UuidUtil.getStrUuid()); } arrayList.add("arrayList-test"); } /** * HashSet通过定位key的hash值进行查找，工夫复杂度O(1) * @return Boolean */ @Benchmark @BenchmarkMode(Mode.Throughput) @OutputTimeUnit(TimeUnit.MILLISECONDS) public Boolean checkHashSet() { return hashSet.contains("hashSet-test"); } /** * 通过迭代器遍历ArrayList进行一一比对，工夫复杂度O(n) * 能够查看编译之后的字节码，会应用迭代器进行遍历操作 * @return Boolean */ @Benchmark @BenchmarkMode(Mode.Throughput) @OutputTimeUnit(TimeUnit.MILLISECONDS) public Boolean checkArrayListWithIterator() { for (String s : arrayList) { if (s.equals("arrayList-test")) { return true; } } return false; } /** * 通过index手工遍历ArrayList进行一一比对，工夫复杂度O(n) * @return Boolean */ @Benchmark @BenchmarkMode(Mode.Throughput) @OutputTimeUnit(TimeUnit.MILLISECONDS) public Boolean checkArrayListWithIndex() { for (int i = 0; i < arrayList.size(); i++) { if (arrayList.get(i).equals("arrayList-test")) { return true; } } return false; } /** * ArrayList的contains办法通过遍历list进行一一比对，工夫复杂度O(n) * @return Boolean */ @Benchmark @BenchmarkMode(Mode.Throughput) @OutputTimeUnit(TimeUnit.MILLISECONDS) public Boolean checkArrayListWithContains() { return arrayList.contains("arrayList-test"); } public static void main(String[] args) throws RunnerException { Options opt = new OptionsBuilder() .include(TestListAndHashSet.class.getSimpleName()) .forks(1) .build(); new Runner(opt).run(); }}（二）简略记录下心得
- 对于
ArrayList这种底层应用数组实现的数据结构，应用数组index遍历会比应用迭代器遍历效率高一些，迭代器遍历更适宜链表类数据； ArrayList的contains办法，源码中默认应用的就是index遍历，因而contains效率和我手动index遍历的效率差不多；HashSet的contains办法，应用的是hash值定位，同HashMap的hash定位，工夫复杂度是O(1)，效率远大于遍历操作；
之后存在汇合蕴含判断的场景，HashSet就是大妙招。
《Java性能优化之影响性能的那些细节》继续更新中...