从集合创建HashSet<int>的最坏情况复杂度是什么？

Question

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

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

假设迭代 IEnumerable 的复杂度为 O(n)，那么以这种方式创建 HashSet<int> 的最坏情况复杂度是什么？

- UghSegment

Answer 1

文档实际上声明：

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

http://msdn.microsoft.com/zh-cn/library/bb301504.aspx

- Robert Levy

---

但这是最坏情况下的复杂度还是摊销复杂度？ - UghSegment

@UghSegment的意思是“平均”复杂性而不是“摊销”。 “摊销”用于有时昂贵（例如，背景存储器翻倍）且其余部分廉价的操作。 这个概念与最坏情况和平均情况无关。 - CodesInChaos

@Servy 我了解它们两个可能是相同的；但这并不影响我的问题 - 最坏情况下的复杂度是否为 O(n)？ - UghSegment

不，一般情况下最坏的情况当然是二次的，但这是针对具有相同GetHashCode()输出的对象。我在想int类型的情况。 - SergeyS

@JeppeStigNielsen 我使用了.NET Reflector来查找HashSet在哈希计算中获取模数值的方法。我使用这些信息向构造函数提供了各种值，这些值都落入同一个索引中，并且在我的测试中性能下降几乎是完美的二次方。看来最坏情况下的复杂度确实是O(n^2)，即使哈希值没有发生冲突。 - UghSegment

Answer 2

你可以通过提供所有哈希到同一个桶中的对象来将最坏情况带到 O(N^2)，当集合达到其最大大小时。例如，如果你传递一个由17519个int构成的序列。

x[i] = i * 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个都为零。

- Sergey Kalinichenko

---

我不会感到惊讶，如果它是O(N^2)。 - CodesInChaos

但是对于非摊销的最坏情况复杂度呢？ - UghSegment

你可以强行让时间复杂度比O（n^2）更差，只要你假设一个具有糟糕或恶意的”GetHashCode“的自定义时间即可。例如，你可以拥有一个永远不返回的“GetHashCode”算法，因此永远无法完成任务；或者你可以拥有一个计算时间复杂度为O(n^2)的“GetHashCode”算法，这样就会使“HashSet”方法……变得比那更糟糕。 - Servy

@Servy 我的观点是，由于您无法控制.NET的Int32的GetHashCode，因此您无法将OP的new HashSet<int>(myIEnumerable)强制转换为O(N^2)领域。当您可以控制GetHashCode时，您可以强制HashSet<T>无限期地阻塞:) HashSet<long>处于中间状态：您可以通过为Int64.GetHashCode的.NET实现提供特别糟糕的序列来做到最坏的情况是O(N^2)。 - Sergey Kalinichenko

对于 int，您仍然可以创建桶索引的冲突。只需添加是 Capacity 的倍数的整数即可。在这种情况下，我预计添加性能为 O(n^2)，但我太懒了，不想弄清楚 HashSet<T> 的首选容量。 - CodesInChaos

@CodesInChaos 你说得对，你可以强制使用 O(N^2)。我没有意识到只考虑最后一个大小就足够了，以为需要尝试3、7、17、37、89等等。感谢你的提示！ - Sergey Kalinichenko

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

---

现在有人声称，对于int类型的HashCode，不会出现多重碰撞。虽然从技术上讲这是正确的，但对于性能来说，重要的不是HashCode的碰撞，而是桶索引的碰撞。我认为HashSet<T>使用类似于bucket = (hash&0x7FFFFFFF)%Capacity的方法。因此，如果您添加的整数序列是首选桶大小的倍数，它仍然会非常慢。

- CodesInChaos

---

如果所有对象返回相同的哈希码，那么是的，由于碰撞，这是O(n*n)。但OP的问题是关于int集合的。因此，我想知道选择具有相等哈希码的一对int是否很困难（可能）？ - SergeyS

我认为你所执行的测试与我在问题中描述的不同。我特别关注的是将具有已知元素数量的集合传递给HashSet构造函数的最坏情况复杂度，而不是多个Add调用的复杂度。 - UghSegment

@SergeyS int是仅有的几种类型之一，没有任何冲突。可能的int值数量不会大于可能的int值数量，因此int值的哈希码实际上对于不同的值是唯一的。(换句话说，它的哈希码可以直接返回自身。)其他类型，如byte和char，其取值范围也小于int，因此永远不会发生冲突。 - Servy

即使使用它，仍然可能导致桶索引的冲突。只是更麻烦一些。| @UghSegment 构造函数也是如此。请参见更新的代码。 - CodesInChaos