Меня зовут Женя, я работаю в Itransition как backend .Net developer – и это моя первая статья на техническую тему. Сегодня я хочу рассказать о типах словарей, которые бывают в .Net, а также о Hash table, о сложности поиска и вставки, о применимости в различных условиях, и даже слегка о Tree.

Big O

Для самого начала нам нужно хотя-бы вскользь пробежаться по алгоритмической сложности. Звучит заумно, но на практике обычно не вызывает сложностей. Мы не будем строить графики и выдвигать математическое доказательство почему O(1) лучше O(n), но нам нужно в самом начале понять, что O(1) означает. Сложность алгоритмов оценивается по двум критериям – временная и по затрачиваемой памяти, потому что и время, и память не безграничны, и мы хотим понять как много мы будем их тратить в сравнении одного и другого пути развития. Нам на данном этапе понадобиться только 3 из них:

O(1) – самый желанный, простой в понимании и сложный в достижении. Означает, что при неограниченно растущей нагрузке мы будем делать то, что нам требуется за условную единицу времени, эта единица времени может быть и секунда и день, но глобально это одно и то же время для любой нагрузки, которое будет испытывать алгоритм.

O(n) – гораздо хуже O(1), но часто приемлемый, а иногда максимально возможный. Означает, что единица времени растет линейно с ростом нагрузки, примером может служить АЗС – в единицу времени колонка качает 1 л. топлива: чтобы перекачать 100 литров, нам нужно в 100 раз больше колонок с той же производительностью.

O(logN) – опять же, хуже O(1), но лучше O(n). Чтобы понять, лучше почитать больше литературы, связанной со сложностью. Но если очень приближенно, то смысл в том, что алгоритм на каждом этапе дает выигрыш в 2 раза, центральная идея бинарных деревьев основана именно на этом (к деревьям мы еще вернемся чуть ниже), данная сложность дает большой профит на большой объеме данных.

Hashtable

Начнем рассказ о HashTable – данная структура доступна для использования и сейчас (.net6) и как любой объект его можно создать:

var hashTable = new Hashtable();

и мы можем даже что-то там хранить в виде пары ключ-значение:

hashTable.Add("company", "Itransition");

hashTable.Add(56, "numberKey");

Но тут мы получаем проблему использования, а именно: и ключ и значение не типизированы, и могут быть чем угодно, что обеспечивается тем, что и ключ, и значение хранится в виде object, что приводит к проблеме boxing/unboxing. А это дополнительные расходы ресурсов – как памяти, так и времени. В общем, в явном виде им уже давно никто не пользуется.

Dictionary<TKey,TValue>

Любой разработчик .Net, который слышит слово Dictionary, представляет себе конструкцию вида:

var dictionary = new Dictionary<TKey, TValue>();

где TKey – это ключ, а TValue – значение, которое соответствует этому ключу. Использование такой структуры данных очень эффективно с точки зрения скорости поиска, вставки и объема используемой памяти. В среднем сложность поиска и вставки составляет O(1), в худшем же O(n) – почему это так, останется за рамками данной статьи.

Чтобы добиться такого шикарного результата, dictionary внутри себя использует HashTable, но в свою очередь dictionary типизирован, т.е. если пользователь создал dictionary для хранения ключей тип число, а для значений объекты котиков, использовать строки он уже не сможет – компилятор будет против) – и это убирает проблему boxing/unboxing, что существенно может сэкономить дополнительные накладные расходы.

Если не используется многопоточность, то dictionary является шикарным выбором для хранения и получения сохраненного результата.

ConcurrentDictionary<TKey,TValue>

Вот это штука очень крутая – в мире, когда все хотят многопоточный код, этот вид dictionary как эликсир жизни и скорости в одном флаконе. Реализуется потокобезопасность с помощью механизма Monitor, который вешает lock на запись значения по ключу, что в свою очередь и закрывает проблему одновременной записи в словарь двух одинаковых значений одновременно. Как раз из-за того, что нет гарантии, что значение было записано в названия методов, добавлено Try – TryAdd(), TryUpdate(), TryDelete()
Но вдруг вы хотите усложнить себе жизнь, тогда для вас есть 

Hashtable.Synchronized(hashTable);

Данный HashTable также потокобезопаснен, но хранит и ключ, и значение в виде object – и опять же мы встречаемся с проблемой boxing/unboxing.

ImmutableDictionary<TKey,TValue>

Как и ConcurrentDictionary, данный вид dictionary является потокобезопасным, т.к. не существует проблемы одновременной записи, мы можем только получать сохраненные значения. Если посмотреть, то у данного dictionary есть методы добавления новых ключ-значение, но на самом деле этого не происходит, потому что при добавлении новой записи в ImmutableDictionary, мы получим новый словарь с копией всех данных из первого словаря, плюс еще одна запись, а исходный не изменится.

А самое интересное, что внутри это не HashTable, а AVL Tree, для которого скорость поиска и вставки составляет уже O(logN). Что такое AVL Tree и деревья в общем, останется за пределами данной статьи.

Производительность

Мы никогда не должны основываться на «мне так кажется»: цифры лучше показывают реальность, нежели ощущения. Поэтому нужно измерять: все что измерено, то оторвано от стереотипов. Для себя я использую BenchmarkDotNet – пакет для .net приложений, позволяющий очень быстро и просто оценить: лучше/хуже стало и на сколько. За примерами использования лучше обратиться к документации или посмотреть в код. Для моей задачки показать, чем отличаются словари, этот инструмент подходит идеально. Для всех тестов будет использоваться .NET SDK=6.0.101

Для начала давайте посмотрим, как словари справляются с вставкой 100, 1000 и 10000 значений

Видно, что обычный Dictionary 100 записей вставляет за 12 наносекунд, а 1000 примерно за 120.от мы и получили почти O(1) сложность вставки одной записи! HashTable чуть медленнее, но он хранит и возвращает все в object и нет проверки на уровне компиляции. ConcurrentDictionary еще немного медленнее – это связано с накладными расходами, обеспечивающими потокобезопасность, но очень даже неплохо для такой мощной системы! Самый же медленный – это ImmutableDictionary. еще прошу обратить внимание на потребляемую им память: при каждой итерации она значительно больше, чем у всех собратьев. Это связано с тем, что при каждой вставке в новый словарь копируются все значения из старого словаря и еще одно, которое мы хотим добавить. Еще прошу заметить, насколько он медленнее при вставке новой записи – все потому что данные в нем хранятся без использования HashTable, а с использованием AVL Tree, у которого сложность вставки O(logN).

Теперь предлагаю посмотреть, как словари справляются с поиском из 1000 значений при 100, 1000 и 10000 попытках.

Тут видно, что время поиска у Dictionary и ConcurrentDictionary практически одинаковое. Оно на самом деле является одинаковым в пределах погрешности и незначительно изменяется при разных прогонах. Поэтому можно считать, что скорость поиска, в отличие от вставки, у обеих коллекций одинаковая и она очень хорошая, даже отличная! Для HashTable можно заметить, что выделяется память, а в других словарях такого нет – это как раз связано с тем, что HashTable хранит и ключ, и значение в виде object, и есть накладные расходы на boxing/unboxing  последующую чистку возникшего мусора с помощью Garbage Collection. Часто это не тривиально и просто так не увидеть, читая код, поэтому еще раз призываю Вас измерять свой код на производительность. И самый медленный из всех опять же ImmutableDictionary, что наводит на следующую мысль: нужно очень внимательно выбирать структуры данных для использования, так есть области применения, где ImmutableDictionary раскрывается с наилучшей стороны – там, где нужно чтобы коллекция была неизменяема – вот так поворот!

Как можно все испортить

Для завершения расскажу, как можно взять отличный Dictionary (я надеюсь, что к этому моменту вы уже с уважением относитесь к этой структуре данных) и испортить его функционал поиска в 257 раз! Будем сравнивать поиск по ключу через метод TryGetValue, ContainsKey, ручной поиск по ключу, Linq.FirstOrDefault. Взглянем на результаты:

Вот это да!!! Между TryGetValue и FirstOrDefault разница в 257 раз – и это на словаре в 100 записей, и дополнительно нужно выделять память и еще создавать работу для GC, подчищая за нами. С умом подходите к использованию методов.

Репозитоторий для тех, кому интересно запустить у себя.