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プロジェクトについて]です。

  • **