1

私はクラスを作成して、arraylistとhashsetの間の挿入パフォーマンスをテストします。予想どおり、ハッシュセットの挿入パフォーマンスはarraylistよりもはるかに優れています（おそらく本は私をだましました）が、テスト結果は私をとても混乱させます

    HashSet<String> hashSet = new HashSet<String>();

    long start = System.currentTimeMillis();
    for (int i = 0; i < 900000; i++) {
        hashSet.add(String.valueOf(i));
    }

    System.out.println("Insert HashSet Time: " + (System.currentTimeMillis() - start));


    ArrayList<String> arrayList = new ArrayList<String>();

    start = System.currentTimeMillis();

    for (int i = 0; i < 900000; i++) {
        arrayList.add(String.valueOf(i));
    }
    System.out.println("Insert ArrayList Time: " + (System.currentTimeMillis() - start));

result:
Insert HashSet Time: 978
Insert ArrayList Time: 287

私はこのメインメトッドを何度も実行しましたが、結果はこれの間で違いはありません。配列リストの挿入時間は、ハッシュセットの挿入時間よりもはるかに短く、誰もがこの奇妙な結果を説明できます。

4

5 に答える 5

4

ハッシュセットとリストは、異なるタイプのデータ構造です。したがって、1つを選択する前に、それらをどのように処理したいかを考える必要があります。

HashSet

挿入時間が長くなります

要素への高速アクセス時間

リスト

速い追加時間

要素へのアクセス時間が長い

リストは、リストの最後に要素を追加するだけで、ハッシュセットが挿入する場所を見つけて要素にアクセスできるようにする必要があるため、より高速です。これは、リストの最後に要素を追加するので、より多くの作業（時間）になります。

于 2013-02-25T15:18:47.720 に答える
2

データ構造とアルゴリズムの正確なパフォーマンス特性は、マシンと実装に大きく固有です。ただし、挿入が一定の係数で挿入ArrayListよりも高速であることは、私には驚くことではありません。HashSetに挿入するにArrayListは、配列内の特定のインデックスに値を設定する必要があります。ハッシュセットに挿入するには、挿入されたアイテムのハッシュコードを計算し、それを配列インデックスにマップし、そのインデックスを確認し、見つかったものに基づいてアクションを実行し、最後に配列に挿入する必要があります。さらに、HashSetメモリの局所性が低下するため、キャッシュミスが頻繁に発生します。

配列のサイズ変更の問題もあります。両方のデータ構造で行う必要がありますが、両方のデータ構造のサイズをほぼ同じ速度で変更する必要があります（また、ハッシュテーブルのサイズ変更は、再ハッシュのために一定の要因でおそらくより高価になります） 。

どちらのアルゴリズムも一定の（予想される）時間ですが、配列リストよりもハッシュテーブルに関係することがたくさんあります。したがって、一定の係数で遅くなることは驚くべきことではありません。（繰り返しになりますが、正確な違いはマシンと実装に大きく依存します。）

于 2013-02-25T15:28:44.687 に答える
0

ハッシュセットの挿入パフォーマンスは、arraylistよりもはるかに優れています

どこでそのアイデアを思いついたのですか？
HashSet検索でパフォーマンスが向上します。ArrayListつまり、次のようになりget()ます。
しかし、挿入すると、同等のパフォーマンスが得られます。ArrayList配列の制限内にあり（サイズ変更は不要）、ハッシュ関数が適切でない場合、実際にはさらに高速になります

于 2013-02-25T15:24:06.673 に答える
0

HashSetはhashtableによって支えられています。ハッシュテーブルについて知っていれば、ハッシュ関数があることを知っているでしょう。また、新しい要素を追加するときの衝突処理（衝突があった場合）。hashSetは衝突を処理しません。ハッシュが同じ場合は、古い値を上書きするだけです。ただし、容量に達した場合は、サイズを変更する必要があり、再ハッシュする可能性があります。それは非常に遅いでしょう。

ArrayListは、オブジェクトをリストの最後に追加するだけです。サイズに達すると、サイズが変更されます。

于 2013-02-25T15:24:31.013 に答える
0

実際、あなたは正しい結果を得ています。また、上記の回答で指摘されているように、これらはさまざまなタイプのデータ構造です。それらを比較することは、自転車と車の速度を比較するようなものです。キーの重複は許されないので、mustに挿入する時間はaに挿入する時間HashSetより長くなければならないと思います。したがって、挿入する前に、挿入前に重複するキーをチェックする必要があり、それらを処理する方法が必要であると思います。これにより、キーはに比べて多少遅くなります。ArrayListHashSetArrayList

于 2013-02-25T15:25:14.377 に答える