HashSetとArrayListでのcontains（）のパフォーマンス

投稿日: 2019-10-19 2022-11-07
タグ: Java, Java Collections, Java List, Java Search, Java Set

1. 序章

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

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

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

ArrayListに関する拡張記事がここで利用可能です。

2. HashSet.contains（）

内部的には、HashSetの実装はHashMapインスタンスに基づいています。 contains（）メソッドは HashMap.containsKey（object）を呼び出します。

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

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

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

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

3. ArrayList.c ontains（）

内部的には、 ArrayListはindexOf（object）メソッドを使用して、オブジェクトがlistにあるかどうかを確認します。 indexOf（object）メソッドは配列全体を反復処理し、各要素を equals（object）メソッドと比較します。

複雑さの分析に戻ると、 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<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.646ns であるのに対し、testHashSetの平均パフォーマンスは9.456nsであることがはっきりとわかります。

それでは、テストで要素数を増やして、反復=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でより高速に動作することがわかります。

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

getdocs

13036