HashSet <T>与Dictionary <K,V>搜索时间以查找项目是否存在

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

来自Dictionary <TKey，TValue>的MSDN文档

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

带有注释：

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

我知道您的问题/帖子很旧-但是在寻找类似问题的答案时，我偶然发现了这个问题。

希望这可以帮助。向下滚动到“ 备注”部分以获取更多详细信息。 https://msdn.microsoft.com/zh-CN/library/xfhwa508(v=vs.110).aspx

Answer 4

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

该答案表明，在 aDictionary或上进行键查找HashSet比在 a 中查找要快得多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");
    }
}