在 C# 中，为什么从列表创建 HashSet 比从 HashSet 开始更快？

我有一个方法，它采用上限，并返回达到该限制的素数列表。

    public static List<int> AllPrimesUnder(int upperLimit)

后来我决定，我真的只需要在列表上进行查找，通常只是问“这是素数吗”这个问题。由于我处理的是一百万以下的所有素数，我意识到 HashSet 是我应该使用的结构。当然，使用该方法的结果进行查找速度更快，但该方法本身是slower.

我认为它速度较慢的原因是 HashSet 在添加之前检查重复项，而 List 只是将其推到末尾。让我惊讶的是，为什么从 List 开始并使用它来创建 HashSet，就像这样：

    hashSet = new HashSet<int>(Prime.AllPrimesUnder(1000000));

比使用方法内部的哈希集更快，支持如下调用：

    hashSet = Prime.AllPrimesUnder_Hash(1000000);

如果速度减慢是由于重复检查，那么无论如何都应该进行相同数量的检查，对吗？这可能是我的理解失败的地方。

以下是我获得一百万以下素数的次数。

• 0.1136s 纯哈希
• 0.0975s 纯列表 (预计会更快)
• 0.0998s 纯列表转换为哈希 (没有预料到)

如果可以用简单的术语解释其原因，我很想听听。我想至少我正在寻找的是足够的理解，以知道如果最终结果将是一个大型项目的哈希集，我是否应该从列表或哈希集开始。

我在下面添加了 prime 方法的主体，但请注意，两者之间与数据结构的所有交互都是相同的（代码方面）。我不相信我向结构添加数据的方式会影响异常。

    public static List<int> AllPrimesUnder(int upperLimit)
    {
        List<int> primeList = new List<int>();
        primeList.Add(2);
        int testNumber = 3;
        bool isPrime;

        while (testNumber <= upperLimit)
        {
            isPrime = true;

            foreach (int prime in primeList)
            {
                if (testNumber % prime == 0)
                {
                    isPrime = false;
                    break;
                }
                if (testNumber < prime*prime)
                    break;
            }

            if (isPrime)
                primeList.Add(testNumber);

            testNumber++;
        }

        return primeList;
    }

编辑：根据要求，我添加了哈希方法的代码。如果它看起来几乎相同，那是因为它确实如此。

public static HashSet<int> AllPrimesUnder_Hash(int upperLimit)
{
    HashSet<int> primeHash = new HashSet<int>();
    primeHash.Add(2);
    int testNumber = 3;
    bool isPrime;

    while (testNumber <= upperLimit)
    {
        isPrime = true;

        foreach (int prime in primeHash)
        {
            if (testNumber % prime == 0)
            {
                isPrime = false;
                break;
            }
            if (testNumber < prime*prime)
                break;
        }

        if (isPrime)
            primeHash.Add(testNumber);

        testNumber++;
    }

    return primeList;
}

另外根据要求，我用来测试执行时间的（丑陋的黑客）代码：

        Stopwatch stopWatch = new Stopwatch();
        int iterations = 1;
        HashSet<int> hashSet = new HashSet<int>();
        List<int> list = new List<int>();

        stopWatch.Restart();
        for (int i = 0; i < iterations; i++)
        {
            hashSet = Prime.AllPrimesUnder_Hash(1000000);
        }
        stopWatch.Stop();

        Console.WriteLine("Hash: " + (stopWatch.Elapsed.TotalSeconds / iterations).ToString("#.###################"));

////////////////////////////////////////////////////

        stopWatch.Restart();
        for (int i = 0; i < iterations; i++)
        {
            hashSet = new HashSet<int>(Prime.AllPrimesUnder(1000000));
        }
        stopWatch.Stop();


        Console.WriteLine("List converted: " + (stopWatch.Elapsed.TotalSeconds / iterations).ToString("#.###################"));

原因是当HashSet使用集合进行初始化，它可以使用集合的大小来设置容量。将值添加到空值时HashSet容量需要不时增加，这是一个 O(n) 操作。
由于某种原因HashSet不像构造函数那样将容量作为参数List does.