Хуже всего сложность создания HashSet <int> из коллекции

У меня есть набор значений int, с помощью которых я заполняю HashSet<int> следующим образом -

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

Предполагая, что итерация IEnumerable равна O(n), какова будет сложность наихудшего случая создания HashSet<int> таким образом?

Ответы

Ответ 1

В документации фактически указано:

Этот конструктор является операцией O (n), где n - число элементов в параметре коллекции.

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

Ответ 2

Вы можете принести наихудший случай в O(N^2), поставив объекты, которые все хешируют в том же ковше, когда набор достигнет своего максимального размера. Например, если вы передаете последовательность из 17519 int, построенную как

x[i] = i * 17519

для i между 1 и 17519, включительно, все числа будут хешировать в исходное ведро при реализации Microsoft HashSet<int>, взяв O(N^2) для вставки:

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

Задайте брейн-точку и рассмотрите h в отладчике. Посмотрите на Raw View/Непубличные участники /m _buckets. Обратите внимание, что начальное ведро имеет 17519 элементов, а остальные 17518 имеют нули.

Ответ 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));
}

выходы:

Теперь некоторые утверждают, что вы не получаете множественных столкновений HashCode для int. Хотя это технически верно, что важно для производительности, это не столкновение HashCode, а столкновение индекса ковша. Я думаю, что HashSet<T> использует что-то вроде bucket = (hash&0x7FFFFFFF)%Capacity. Поэтому, если вы добавите последовательность целых чисел, которая будет иметь несколько предпочтительного размера ведра, все равно будет очень медленно.