HashSet<T>与Dictionary<K, V>w.r.t搜索时间来查找项目是否存在

Question

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


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

谁的

.Contains

方法返回速度更快？

澄清一下，我的要求是我有 1000 万个对象（实际上是字符串），我需要检查它们是否存在于数据结构中。我永远不会迭代。

Answer 1

HashSet vs List vs Dictionary 性能测试，摘自这里。

添加 1000000 个对象（不检查重复项）

包含检查 10000 个集合中一半的对象

删除 10000 个集合中的一半对象

Answer 2

我想你的意思是第二种情况下的

Dictionary<TKey, TValue>

？

HashTable

是一个非泛型类。

您应该根据自己的实际需求选择适合工作的集合。您真的想要将每个键映射到一个值吗？如果是这样，请使用

Dictionary<,>

。如果您只关心它作为一个集合，请使用

HashSet<>

。

我希望

HashSet<T>.Contains

和

Dictionary<TKey, TValue>.ContainsKey

（这是可比较的操作，假设您明智地使用字典）基本上执行相同的操作 - 从根本上讲，它们使用相同的算法。我猜想，由于

Dictionary<,>

中的条目较大，因此使用

Dictionary<,>

破坏缓存的可能性比使用

HashSet<>

更大，但我认为与选择错误数据的痛苦相比，这微不足道简单地输入您想要实现的目标。

Answer 3

来自 字典的 MSDN 文档：

“使用键检索值非常快，接近 O(1)，因为 Dictionary 类是作为哈希表实现的。”

附注：

“检索速度取决于为 TKey 指定类型的哈希算法的质量”

Answer 4

此问题接受的答案并未有效回答该问题！它恰好给出了正确的答案，但他们提供的证据并未显示该答案。

这个答案表明，在

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");
    }
}

Answer 5

这些是不同的数据结构。也没有

HashTable

 的通用版本。

HashSet

 包含类型 T 的值，其中 

HashTable

（或 

Dictionary

）包含键值对。所以你应该根据需要存储的数据来选择集合。