Алгоритмическая сложность итерирования по хэшсету в C#

Исследуя Reflector'ом внутренности классов .NET фреймворка, нередко можно узнать много любопытных вещей. Например, однажды (довольно давно) я узнал, что для дотнетовского QuickSort можно очень просто придумать такой класс входных данных, на которых сортировка будет осуществляться за квадратичное время. Так, на массивах-«пирамидках» (то есть на таких, в которых максимальный элемент находится посередине, второй и третий по величине — слева и справа от него, и так далее) быстрая сортировка была сравнима по времени с пузырьковой. Причина очевидна — в качестве медианы выбирался средний элемент массива. Как с этой проблемой дело обстоит сейчас, не знаю, но если она всё ещё имеет место — это заслуживает отдельного поста.

Речь сейчас пойдёт о другом. Всем, кто знаком с дотнетом, полагаю, известен класс System.Collections.Generic.HashSet<T>. Как гласит MSDN, класс HashSet предоставляет высокопроизводительные операции над множествами. Как вы думаете, за какое время ваш компьютер, скажем, двести раз пробежит по хэшсету из одного элемента? Сотая доля секунды? Меньше? Вовсе не факт!

Дело в том, что внутреннее устройстов хэшсета таково, что в нём вместо удалённых элементов могут появляться «дыры» — помеченные специальным образом элементы, по которым итератор бежит в любом случае. Таким образом, если, например, сначала в хэшсет положить миллион элементов, а потом почти все из него удалить, оставив лишь несколько, то время, затраченное на итерацию по этим оставшимся элементам будет гораздо больше времени, которое показала бы пробежка по сравнимому по размеру хэшсету, на котором не выполнялось операций удаления.

Следующий код демонстрирует, как может отличаться время итерации по хэшсету без тяжелого прошлого от времени итерации по потрёпанному жизнью хэшсету, в который сначала набросали миллион элементов, а потом почти все забрали:

1. using System;
2. using System.Collections.Generic;
3. using System.Diagnostics;
4.  
5. public class HashSetIterationPerformance
6. {
7.   public const int MaxItemsCount = 10000000;
8.   public const int RepeatIterations = 200;
9.  
10.   public static TimeSpan MeasureIterationTime(HashSet<int> hashSet)
11.   {
12.     var stopwatch = new Stopwatch();
13.     stopwatch.Start();
14.     for (int i = 0; i < RepeatIterations; ++i)
15.       foreach (var x in hashSet)
16.       {
17.         // Do nothing
18.       }
19.     return new TimeSpan(stopwatch.Elapsed.Ticks / RepeatIterations);
20.   }
21.  
22.   public static void Main(string[] args)
23.   {
24.     var hashSet = new HashSet<int>();
25.     hashSet.Add(0);
26.     Console.WriteLine("Usual scenario. Iteration time: {0}", MeasureIterationTime(hashSet));
27.  
28.     hashSet = new HashSet<int>();
29.     // Добавляем много-много чисел: [0..MaxItemsCount)
30.     for (int i = 0; i < MaxItemsCount; ++i)
31.     {
32.       hashSet.Add(i);
33.     }
34.     // Удаляем все числа, кроме нуля
35.     for (int i = 1; i < MaxItemsCount; ++i)
36.     {
37.       hashSet.Remove(i);
38.     }
39.     Console.WriteLine("Add/Remove scenario. Iteration time: {0}", MeasureIterationTime(hashSet));
40.   }
41. }

* This source code was highlighted with Source Code Highlighter.

На моей машине выводит вот такое:

Usual scenario. Iteration time: 00:00:00.0000032
Add/Remove scenario. Iteration time: 00:00:00.0468619

Как видите, разница по времени огромная — во многие тысячы раз, хотя функционально мы делали одно и то же действие в обоих случаях — бежали по множеству из одного элемента.

Строго говоря, временная сложность итерирования по всем элементам дотнетовского HashSet'а в худшем случае — не O(N), где N — количество элементов в нём, а O(максимальное количество элементов в хэшсете, которое в нём когда-либо было).

Так что, друзья, вывод просто. Читайте MSDN с недоверием, используйте классы .NET с осторожностью, вскрывайте этот фреймворк Рефлектором и любите друг друга. Тогда будет перфоманс.