在C＃中，为什么从List创建HashSet更快，而不是从HashSet开始？
我有一个采用上限的方法，并返回一个素数列表，直到该限制。
public static List AllPrimesUnder(int upperLimit) 我后来决定我真的只需要在列表上进行查找，通常只是询问“Is This Prime”这个问题。 由于我在处理价值百万的所有素数时，我意识到HashSet是我应该使用的结构。 当然使用该方法的结果查找速度更快，但该方法的自身速度较慢 。
我认为它较慢的原因是因为HashSet在添加之前检查重复项，而List只是在最后推送它。 令我惊讶的是，产生问题和标题的原因是为什么从List开始并使用它来创建HashSet，如下所示：
hashSet = new HashSet(Prime.AllPrimesUnder(1000000));
比使用方法内部的Hashset更快，启用如下调用：
hashSet = Prime.AllPrimesUnder_Hash(1000000);
如果减速是在重复检查中，则无论如何都应该进行相同数量的检查，对吧？ 这可能是我理解失败的地方。
以下是我获得100万以下素数的时间。
- 0.1136s Pure Hash
- 0.0975s纯清单（ 预计会更快 ）
- 0.0998s Pure List转换为Hash（ 未预期 ）
如果可以用简单的术语解释原因，我很乐意听到。 我想至少我正在寻找足够的理解知道我是否应该从List或HashSet开始，如果最终结果将是一个大的HashSet项。
我在下面添加了prime方法的主体，但请注意，与数据结构的所有交互在两者之间是相同的（代码方式）。 我不相信我如何添加数据到结构应该影响exception。
public static List AllPrimesUnder(int upperLimit) { List primeList = new List(); 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 AllPrimesUnder_Hash(int upperLimit) { HashSet primeHash = new HashSet(); 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; }
另外通过请求我用来测试执行时间的（丑陋的hackish）代码：
Stopwatch stopWatch = new Stopwatch(); int iterations = 1; HashSet hashSet = new HashSet(); List list = new List(); 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(Prime.AllPrimesUnder(1000000)); } stopWatch.Stop(); Console.WriteLine("List converted: " + (stopWatch.Elapsed.TotalSeconds / iterations).ToString("#.###################"));
在AllPrimesUnder您多次枚举主要列表（每个主要候选人一次）。 枚举List比枚举HashSet更快，因为HashSet的内部数组更稀疏。
没有看到AllPrimesUnder_Hash的代码我猜这是主要原因。
我不相信重新调整几千个项目的列表可能会消耗20ms。 使用memcpy复制内存（这是内部发生的事情）是您可以执行的吞吐量最高的操作之一。 您可以为每个核心每秒复制数十GB。
原因是当使用集合初始化HashSet时，它可以使用集合的大小来设置容量。 将值添加到空HashSet ，需要不时增加容量，这是O（n）操作。
由于某种原因， HashSet不像List那样将容量作为构造函数中的参数。
看看你的算法，我怀疑纯哈希是慢的，因为它是哈希，而不是有序列表。 使用有序列表时，按顺序测试2,3,5,7等的可分性，因此首先测试较小的除数（更常见的是除数）。 使用哈希时，顺序是任意的，因此在测试可被3整除之前，您可以测试23可整除。
顺便说一下，你应该使用testnumber + = 2，并从你的素数列表中排除2，当你完成你的循环时插入2。
更好的是， Eratosthenes筛选通常是一种更快的方法来计算相对较小数量的所有素数。 或者甚至更好，预先计算您的低值素数并从磁盘加载它
编辑 – 增加
不是我最初的期望（哈希是乱序的），但它看起来像是在MoveNext（）中更多的开销 – 这就是foreach在内部工作的方式
比较MoveNext（）函数的差异 – 你将在最里面的循环中调用数百万次。
// HashSet<>.MoveNext() public bool MoveNext() { if (this.version != this.set.m_version) { throw new InvalidOperationException(SR.GetString("InvalidOperation_EnumFailedVersion")); } while (this.index < this.set.m_lastIndex) { if (this.set.m_slots[this.index].hashCode >= 0) { this.current = this.set.m_slots[this.index].value; this.index++; return true; } this.index++; } this.index = this.set.m_lastIndex + 1; this.current = default(T); return false; } List<>.MoveNext() public bool MoveNext() { List list = this.list; if ((this.version == list._version) && (this.index < list._size)) { this.current = list._items[this.index]; this.index++; return true; } return this.MoveNextRare(); // this call should be rare as the name implies } private bool MoveNextRare() { if (this.version != this.list._version) { ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); } this.index = this.list._size + 1; this.current = default(T); return false; }