c# - 创建 HashSet 的最坏情况复杂度从一个集合

Question

我有一组值，我用以下方式int填充 a -HashSet<int>

var hashSet = new HashSet<int>(myIEnumerable);

假设迭代IEnumerableis O(n)，以这种方式创建 a的最坏情况HashSet<int>复杂度是多少？

Answer 1

该文档实际上指出：

此构造函数是一个 O(n) 操作，其中 n 是集合参数中的元素数。

http://msdn.microsoft.com/en-us/library/bb301504.aspx

Answer 2

当集合达到其最大大小时，O(N^2)您可以通过将所有散列到同一存储桶的对象提供最坏的情况。例如，如果您传递一个 17519的序列，构造为int

x[i] = i * 17519

在i1 到 17519 之间（包括 1 和 17519），所有数字都将散列到 Microsoft 实现的初始存储桶中HashSet<int>，O(N^2)插入：

var h = new HashSet<int>(Enumerable.Range(1, 17519).Select(i => i*17519));

设置一个断点，并h在调试器中检查。查看原始视图/非公共成员/m_buckets。观察初始存储桶有 17519 个元素，而其余 17518 个元素都为零。

Answer 3

简并哈希码（一个常数）的快速实验表明它是二次的。

for(int n=0;n<100;n++)
{
    var start=DateTime.UtcNow;
    var s=new HashSet<Dumb>(Enumerable.Range(0,n*10000).Select(_=>new Dumb()));
    Console.Write(n+" ");
    Console.WriteLine((int)((DateTime.UtcNow-start).TotalSeconds*10));
}

输出：

0 0
1 8
2 34
3 73
4 131

---

现在有些人声称您不会遇到HashCodefor int 的多次冲突。虽然这在技术上是正确的，但对性能而言重要的不是 HashCode 的冲突，而是桶索引的冲突。我认为HashSet<T>使用类似bucket = (hash&0x7FFFFFFF)%Capacity. 因此，如果您添加一个整数序列是首选存储桶大小的倍数，它仍然会非常慢。