填充哈希集的最快方法

Question

我需要定期遍历一个大型对象集合，并在其中维护特定String属性的唯一值。

我使用哈希集来保存唯一的值，但想知道检查哈希集中是否存在一个值，或者只是尝试添加所有值是否更有效？

Answer 1

由于Jon Hanna所说的原因，您的测试是一个糟糕的测试，并且没有给您准确的结果。当您在内部调用Add时，HashSet调用AddIfNotPresent，而AddIfNotPresent所做的第一件事就是检查对象是否存在（从ILSpy获得的代码）

public bool Add(T item)
{
    return this.AddIfNotPresent(item);
}
private bool AddIfNotPresent(T value)
{
    if (this.m_buckets == null)
    {
        this.Initialize(0);
    }
    int num = this.InternalGetHashCode(value);
    int num2 = num % this.m_buckets.Length;
    int num3 = 0;
    for (int i = this.m_buckets[num % this.m_buckets.Length] - 1; i >= 0; i = this.m_slots[i].next)
    {
        if (this.m_slots[i].hashCode == num && this.m_comparer.Equals(this.m_slots[i].value, value))
        {
            return false;
        }
        num3++;
    }
    //(Snip)

因此，通过执行Contains，然后执行Add，可以检查对象是否存在两次。如果你的存储桶中有很多项目，它正在检查，这可能会导致严重的性能损失。

Answer 2

由于我最初的回答通常被嘲笑，我又尝试了一次。

Int32 maxUniques = 1;
Int32 collectionSize = 100000000;
Random rand = new Random();
while (maxUniques <= collectionSize)
{
    List<Int32> bigCollection = new List<Int32>();
    bigCollection.Capacity = collectionSize;
    for (Int32 count = 0; count < collectionSize; count++)
        bigCollection.Add(rand.Next(maxUniques));
    HashSet<Int32> uniqueSources = new HashSet<Int32>();
    Stopwatch watch = new Stopwatch();
    watch.Start();
    foreach (Int32 num in bigCollection)
    {
        if (!uniqueSources.Contains(num))
            uniqueSources.Add(num);
    }
    Console.WriteLine(String.Format("With {0,10:N0} unique values in a set of {1,10:N0} values, the time taken for conditional add: {2,6:N0} ms", uniqueSources.Count, collectionSize, watch.ElapsedMilliseconds));
    uniqueSources = new HashSet<Int32>();
    watch.Restart();
    foreach (Int32 num in bigCollection)
    {
        uniqueSources.Add(num);
    }
    Console.WriteLine(String.Format("With {0,10:N0} unique values in a set of {1,10:N0} values, the time taken for simple add:      {2,6:N0} ms", uniqueSources.Count, collectionSize, watch.ElapsedMilliseconds));
    Console.WriteLine();
    maxUniques *= 10;
}

它给出了以下输出：

在一组100000000个值中有1个唯一值时，条件相加所需的时间：2004毫秒在一组100000000个值中有1个唯一值时，简单相加所需的时间：2540毫秒

在一组100000000个值中有10个唯一值时，条件相加所需时间：2066毫秒在一组100000000个值中有10个唯一值，简单相加所需时间：2391ms

在一组100000000个值中有100个唯一值时，条件相加所需时间：2057毫秒在一组100000000个值中有100个唯一值时，简单相加所需的时间：2410毫秒

在一组100000000个值中有1000个唯一值时，条件相加所需的时间：2011毫秒在一组100000000个值中有1000个唯一值，简单相加所需时间：2459毫秒

在一组100000000个值中有10000个唯一值时，条件加法所需的时间为：2219毫秒
在一组100000000个值中有10000个唯一值，简单相加所需时间：2414ms

在一组100000000个值中有100000个唯一值时，条件加法所需的时间为：3024毫秒
在一组100000000个值中有100000个唯一值，简单相加所需时间：3124ms

在一组100000000个值中有1000000个唯一值时，条件加法所需的时间为：8937毫秒
在一组100000000个值中有1000000个唯一值时，简单相加所需的时间：9310毫秒

在一组100000000个值中有9999536个唯一值时，条件相加所需时间：11798毫秒
在一组100000000个值中有9999536个唯一值，简单相加所需时间：11660 ms

在一组100000000个值中有63199938个唯一值，条件相加所需时间为：20847毫秒
在一组100000000个值中有63199938个唯一值，简单相加所需时间：20213毫秒

这对我来说很奇怪。

最多添加1%，调用Contains（）方法会更快，而不是一直点击Add（）。对于10%和63%，只使用Add（）会更快。

换句话说：
1亿Contains（）比9900万Add（）快
1亿Contains（）比9000万Add（）慢

我调整了代码，以100万的增量尝试了100万到1000万个唯一值，发现拐点在7-10%左右，结果并不是决定性的。

因此，如果您希望添加的值少于7%，那么首先调用Contains（）会更快。超过7%，只需调用Add（）。

Answer 3

当我输入问题时，突然有人问我为什么不自己测试它。所以我自己测试过。

我创建了一个包含126万条记录和21个唯一源字符串的集合，并通过以下代码运行它：

HashSet<String> uniqueSources = new HashSet<String>();
Stopwatch watch = new Stopwatch();
watch.Start();
foreach (LoggingMessage mess in bigCollection)
{
    uniqueSources.Add(mess.Source);
}
Console.WriteLine(String.Format("Time taken for simple add: {0}ms", watch.ElapsedMilliseconds));
uniqueSources.Clear();
watch.Restart();
foreach (LoggingMessage mess in bigCollection)
{
    if (!uniqueSources.Contains(mess.Source))
        uniqueSources.Add(mess.Source);
}
Console.WriteLine(String.Format("Time taken for conditional add: {0}ms", watch.ElapsedMilliseconds));

结果表明：

简单添加所需时间：147ms

条件添加所需时间：125ms

因此，至少对我的数据来说，检查是否存在并不会减慢速度，实际上会稍微快一点。不过，无论哪种方式，差异都很小。