Worst case complexity of creating a HashSet<int> from a collection

Question

I have a collection of int values with which I populate a HashSet<int> in the following manner -

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

Assuming that iterating the IEnumerable is O(n), what will be the worst case complexity of creating a HashSet<int> in such a way?

Answer 1

You can bring the worst case to O(N^2) by supplying objects that all hash to the same bucket when the set reaches its maximum size. For example, if you pass a sequence of 17519 ints constructed as

x[i] = i * 17519

for i between 1 and 17519, inclusive, all numbers will hash to the initial bucket on Microsoft's implementation of HashSet<int>, taking O(N^2) to insert:

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

Set a brea kpoint, and examine h in the debugger. Look at Raw View / Non-public members / m_buckets. Observe that the initial bucket has 17519 elements, while the remaining 17518 all have zeros.

Answer 2

The documentation actually states:

This constructor is an O(n) operation, where n is the number of elements in the collection parameter.

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