HashSetとArrayListでのcontains()のパフォーマンス

1.はじめに

このクイックガイドでは、java.utilで使用可能なcontains()メソッドのパフォーマンスについて説明しますHashSetjava.util。ArrayList。これらは両方とも、オブジェクトを格納および操作するためのコレクションです。

HashSetは、一意の要素を格納するためのコレクションです。HashSetの詳細についてはこのリンクを確認してください。

ArrayListは、java.util.Listインターフェースの一般的な実装です

ArrayListに関する拡張記事がここにあります。

2. HashSet.contains()

内部的には、HashSetの実装はHashMapインスタンスに基づいています。含有()メソッドを呼び出しHashMap.containsKey(オブジェクト)

ここでは、オブジェクトが内部マップにあるかどうかをチェックしています。内部マップには、バケットと呼ばれるノード内のデータが格納されます。各バケットは、hashCode()メソッドで生成されたハッシュコードに対応します。したがって、contains()は実際にはhashCode()メソッドを使用してオブジェクトの場所を見つけています

次に、ルックアップ時間の複雑さを判断しましょう。先に進む前に、Big-O表記に精通していることを確認してください。

平均して、()含有HashSetので実行O(1)時間オブジェクトのバケット位置取得は、一定時間の操作です。内部バケット構造はTreeMapであるため、衝突の可能性を考慮すると、ルックアップ時間はlog(n)に達する可能性があります。

これは、内部バケット構造にLinkedListを使用したJava7からの改善です。一般に、ハッシュコードの衝突はまれです。したがって、要素のルックアップの複雑さをO(1)と見なすことができます。

3. ArrayList.c ontains()

内部的には、ArrayListindexOf(object)メソッドを使用して、オブジェクトがリストにあるかどうかを確認しますindexOf(オブジェクト)メソッドは、アレイ全体を反復処理し、各要素を比較し、等しい(オブジェクト)メソッド。

複雑さの分析に戻ると、ArrayListですcontains()メソッドにはO(n)時間が必要です。したがって、ここで特定のオブジェクトを見つけるために費やす時間は、配列内のアイテムの数によって異なります。

4.ベンチマークテスト

それでは、パフォーマンスベンチマークテストでJVMをウォームアップしましょう。JMH(Java Microbenchmark Harness)OpenJDK製品を使用します。セットアップと実行の詳細については、便利なガイドをご覧ください。

まず、簡単なCollectionsBenchmarkクラスを作成しましょう。

@BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.NANOSECONDS) @Warmup(iterations = 5) public class CollectionsBenchmark { @State(Scope.Thread) public static class MyState { private Set employeeSet = new HashSet(); private List 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のArrayList従業員は、オブジェクト:

public class Employee { private Long id; private String name; // constructor and getter setters go here }

両方のコレクションの最後の要素として、employee = new Employee(100L、“ Harry”)インスタンスを追加します。そのため、最悪の場合について、従業員オブジェクトのルックアップ時間をテストします。

@OutputTimeUnit(TimeUnit.NANOSECONDS)は、結果をナノ秒単位で表示することを示します。この場合、デフォルトの@Warmup反復回数は5回です。@BenchmarkModeがに設定されているMode.AverageTime我々は平均実行時間を計算することに興味を持っていることを意味し、。最初の実行では、コレクションに反復= 1000アイテムを配置します

その後、ベンチマークメソッドをCollectionsBenchmarkクラスに追加します。

@Benchmark public boolean testArrayList(MyState state) { return state.employeeList.contains(state.employee); }

ここでは、employeeListemployeeオブジェクトが含まれているかどうかを確認します。

同様に、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()のパフォーマンスを示しました。

結論として、私たちがいることを、学ぶことができます含まれています()メソッドは、より高速で動作しますHashSetのに比べArrayListに

いつものように、この記事の完全なコードはGitHubプロジェクトにあります。