最糟糕的情况是从集合中创建HashSet <int>的复杂性

Question

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

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

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

Answer 1

文档实际上说明:

此构造函数是O(n)操作,其中n是collection参数中的元素数.

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

Answer 2

O(N^2)通过在集合达到其最大大小时将所有散列的对象提供给同一个存储桶,可以使最坏的情况发生.例如,如果你传递一个17519 int秒的序列作为

x[i] = i * 17519

对于i介于1和17519之间(包括1和17519)的所有数字,将在Microsoft的实现中散列到最初的存储桶HashSet<int>,O(N^2)并插入:

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

设置brea kpoint,并h在调试器中检查.查看Raw View /非公共成员/ m_buckets.观察到初始存储桶有17519个元素,而剩余的17518都有零.