HashSet vs ArrayListにおけるcontains（）のパフォーマンス
1前書き
このクイックガイドでは、
java.util.HashSet
および
java.util.ArrayList
** で使用可能な
contains（）
メソッドのパフォーマンスについて説明します。どちらもオブジェクトを格納し操作するためのコレクションです。
HashSet
は一意の要素を格納するためのコレクションです。 __HashSetの詳細については、https://www.baeldung.com/java-hashset[このリンク]をご覧ください。
ArrayList
は、
java.util.List
インターフェースの一般的な実装です。
ここ
にある
ArrayList
に関する拡張記事があります。
2
HashSet.contains（）
内部的には、
HashSet
実装は
__HashMap
インスタンスに基づいています。
contains（）
メソッドは
HashMap.containsKey（object）__を呼び出します。
ここでは、
オブジェクト
が内部マップにあるかどうかを確認しています。
内部マップは、バケットと呼ばれるデータをノード内に格納します。各バケットは
__hashCode（）
__methodで生成されたハッシュコードに対応します。
そのため、
contains（）
は実際には
_オブジェクトの
locationを見つけるために
hashCode（）
_
methodを使用しています。
それでは、ルックアップ時間の複雑さを判断しましょう。先に進む前に、あなたがhttps://www.baeldung.com/big-o-notation[Big-O表記]をよく知っていることを確認してください。
平均して、
HashSet
の
contains（）
は
O（1）
time
で実行されます。
-
オブジェクトのバケット位置を取得することは、一定時間の操作です。
衝突の可能性を考慮に入れると、内部のバケット構造は
TreeMap
。** であるため、ルックアップ時間は
log（n）
になります。
これは、内部バケット構造に
LinkedList
を使用したJava 7からの改善点です。一般に、ハッシュコードの衝突はまれです。そのため、要素の検索の複雑さを
O（1）
と見なすことができます。
3.
ArrayList.c
_
ontains（）
_
内部的には、
ArrayList
は
indexOf（object）
メソッドを使用して、オブジェクトがリスト内にあるかどうかを確認します
。
indexOf（object）
メソッドは配列全体を繰り返し、各要素を
equals（object）
メソッドと比較します。
複雑さの分析に戻ると、
ArrayList
.
contains（）
メソッドには
O（n）
時間が必要です。したがって、ここで特定のオブジェクトを見つけるために費やす時間は、配列内にある項目の数によって異なります。
4ベンチマークテスト
それでは、パフォーマンスベンチマークテストでJVMをウォームアップしましょう。 JMH（Java Microbenchmark Harness）OpenJDK製品を使用します。セットアップと実行の詳細については、https://www.baeldung.com/java-microbenchmark-harness[役に立つガイド]をご覧ください。
はじめに、簡単な
CollectionsBenchmark
クラスを作成しましょう。
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 5)
public class CollectionsBenchmark {
@State(Scope.Thread)
public static class MyState {
private Set<Employee> employeeSet = new HashSet<>();
private List<Employee> employeeList = new ArrayList<>();
private long iterations = 1000;
private Employee employee = new Employee(100L, "Harry");
@Setup(Level.Trial)
public void setUp() {
for (long i = 0; i < iterations; i++) {
employeeSet.add(new Employee(i, "John"));
employeeList.add(new Employee(i, "John"));
}
employeeList.add(employee);
employeeSet.add(employee);
}
}
}
ここでは、
HashSet
と
Employee
オブジェクトの
ArrayList
を作成して初期化します。
public class Employee {
private Long id;
private String name;
//constructor and getter setters go here
}
両方のコレクションの最後の要素として、
__ employee = new Employee（100L、“ Harry”）
インスタンスを追加します。そのため、最悪の場合について
employee__オブジェクトのルックアップ時間をテストします。
@ OutputTimeUnit（TimeUnit.NANOSECONDS）
は、結果がナノ秒単位であることを示します。デフォルトの
@ Warmup
反復回数は、この例では5です。
@ BenchmarkMode
は
Mode.AverageTime
に設定されています。これは、平均実行時間の計算に関心があることを意味します。最初の実行では、
iterations = 1000
個のアイテムをコレクションに入れます。
その後、ベンチマークメソッドを
CollectionsBenchmark
クラスに追加します。
@Benchmark
public boolean testArrayList(MyState state) {
return state.employeeList.contains(state.employee);
}
ここでは、
employeeList
に
employee
オブジェクトが含まれているかどうかを確認します。
同様に、
employeeSet
についてもおなじみのテストがあります。
@Benchmark
public boolean testHashSet(MyState state) {
return state.employeeSet.contains(state.employee);
}最後に、テストを実行します。
public static void main(String[]args) throws Exception {
Options options = new OptionsBuilder()
.include(CollectionsBenchmark.class.getSimpleName())
.forks(1).build();
new Runner(options).run();
}結果は次のとおりです。
Benchmark Mode Cnt Score Error Units
CollectionsBenchmark.testArrayList avgt 20 4035.646 ± 598.541 ns/op
CollectionsBenchmark.testHashSet avgt 20 9.456 ± 0.729 ns/op-
testArrayList
メソッドの平均検索スコアは
4035.646 ns
であるのに対し、
testHashSet
のパフォーマンスは平均して
9.456 ns
と速くなっています。
それでは、テストの要素数を増やして、反復回数= 10.000項目で実行しましょう。
Benchmark Mode Cnt Score Error Units
CollectionsBenchmark.testArrayList avgt 20 57499.620 ± 11388.645 ns/op
CollectionsBenchmark.testHashSet avgt 20 11.802 ± 1.164 ns/op
ここでも、
HashSet
の
contains（）
は
ArrayList
よりもパフォーマンスが非常に優れています。
5結論
この簡単な記事では、
HashSet
および
ArrayList
コレクションの
contains（）
メソッドのパフォーマンスについて説明します。 JMHベンチマークの助けを借りて、コレクションの種類ごとに
contains（）
のパフォーマンスを示しました。
結論として、
Contains（）メソッドは
ArrayList
と比較して
HashSet__の方が速く動作することがわかります。
いつものように、この記事の完全なコードはhttps://github.com/eugenp/tutorials/tree/master/core-java-collections[GitHubプロジェクトについて]です。
-
**
