118 
HashSet<T> t = new HashSet<T>();
// add 10 million items


Dictionary<K, V> t = new Dictionary<K, V>();
// add 10 million items.

誰の.Containsメソッドがより早く戻りますか？

明確にするために、私の要件は、データ構造に存在するかどうかを確認する必要がある1,000万個のオブジェクト（実際には文字列）があることです。私は決して繰り返しません。

4

5 に答える 5

176

HashSet vs List vs Dictionaryパフォーマンステスト、ここから取得。

1000000オブジェクトを追加します（重複をチェックせずに）

10000のコレクションのオブジェクトの半分のチェックが含まれています

10000のコレクションのオブジェクトの半分を削除します

于 2012-04-27T09:43:07.373 に答える
74

私はあなたDictionary<TKey, TValue>が2番目の場合を意味すると思いますか？HashTable非ジェネリッククラスです。

実際の要件に基づいて、ジョブに適したコレクションを選択する必要があります。実際に各キーを値にマップしますか？その場合は、を使用しますDictionary<,>。セットとしてのみ気にする場合は、を使用してHashSet<>ください。

HashSet<T>.Contains私は、 （辞書を賢明に使用していると仮定すると、同等の操作です）基本的に同じことを実行することを期待Dictionary<TKey, TValue>.ContainsKeyします-基本的に同じアルゴリズムを使用しています。エントリDictionary<,>が大きくなると、キャッシュを吹き飛ばす可能性が高くなるDictionary<,>とHashSet<>思いますが、単に自分が何であるかという点で間違ったデータ型を選択するという苦痛と比較すると、取るに足らないものになると思います。達成しようとしています。

于 2010-04-28T10:15:02.593 に答える
9

Dictionary <TKey、TValue>のMSDNドキュメントから

「 Dictionaryクラスはハッシュテーブルとして実装されているため、キーを使用して値を取得するのは非常に高速で、 O（1）に近いです。 」

注付き：

「取得の速度は、TKeyに指定されたタイプのハッシュアルゴリズムの品質に依存します」

あなたの質問/投稿が古いことは知っていますが、同様の質問に対する答えを探しているときに、私はこれに遭遇しました。

お役に立てれば。詳細については、[備考]セクションまで下にスクロールしてください。 https://msdn.microsoft.com/en-us/library/xfhwa508(v=vs.110).aspx

于 2017-01-24T19:37:12.363 に答える
4

これらは異なるデータ構造です。また、の汎用バージョンはありませんHashTable。

HashSetキーと値のペアを含むHashTable（または）タイプTの値が含まれます。Dictionaryしたがって、保存する必要のあるデータの収集を選択する必要があります。

于 2010-04-28T10:16:41.727 に答える
2

この質問に対する受け入れられた回答は、質問に有効に回答しません！それはたまたま正しい答えを与えますが、その答えは彼らが提供した証拠によって示されていません。

その答えが示しているのは、Dictionaryまたはでのキーのルックアップは、でのルックアップHashSetよりもはるかに高速であるということListです。これは真実ですが、面白くもなく、驚くべきことでも、同じ速度であるという証拠でもありません。

以下のコードを実行してルックアップ時間を比較しましたが、実際には同じ速度であると結論付けています。（または、少なくとも、違いがある場合、その違いはその速度の標準偏差の範囲内です）

具体的には、このテストでは、100,000,000回のルックアップに、両方で10〜11.5秒かかりました。

テストコード：

private const int TestReps = 100_000_000;
[Test]
public void CompareHashSetContainsVersusDictionaryContainsKey()
{
    for (int j = 0; j < 10; j++)
    {
        var rand = new Random();
        var dict = new Dictionary<int, int>();
        var hash = new HashSet<int>();

        for (int i = 0; i < TestReps; i++)
        {
            var key = rand.Next();
            var value = rand.Next();
            hash.Add(key);
            dict.TryAdd(key, value);
        }

        var testPoints = Enumerable.Repeat(1, TestReps).Select(_ => rand.Next()).ToArray();
        var timer = new Stopwatch();
        var total = 0;
        
        timer.Restart();
            for (int i = 0; i < TestReps; i++)
            {
                var newKey = testPoints[i];
                if (hash.Contains(newKey))
                {
                    total++;
                }
            }
        Console.WriteLine(timer.Elapsed);
        
        var target = total;
        Assert.That(total == target);
        

        timer.Restart();
            for (int i = 0; i < TestReps; i++)
            {
                var newKey = testPoints[i];
                if (dict.ContainsKey(newKey))
                {
                    total++;
                }
            }
        Console.WriteLine(timer.Elapsed);

        Assert.That(total == target * 2);
        Console.WriteLine("Set");
    }
}
于 2020-07-28T09:34:43.317 に答える