Меня зовут Женя, я работаю в 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 значений

Method

Target

Mean

Error

StdDev

Rank

Allocated

Dictionary_Add

100

11.50 us

0.036 us

0.032 us

1

11 KB

Hashtable_Add

100

16.33 us

0.282 us

0.325 us

2

14 KB

ConcurrentDictionary_Add

100

20.34 us

0.072 us

0.060 us

3

25 KB

ImmutableDictionary_Add

100

62.62 us

0.900 us

0.842 us

4

49 KB

Dictionary_Add

1000

118.59 us

0.398 us

0.372 us

5

114 KB

Hashtable_Add

1000

162.68 us

0.968 us

0.905 us

6

140 KB

ConcurrentDictionary_Add

1000

209.76 us

2.043 us

1.811 us

7

220 KB

ImmutableDictionary_Add

1000

903.69 us

9.405 us

7.854 us

8

723 KB

Dictionary_Add

10000

1,254.97 us

11.560 us

10.248 us

9

1,051 KB

Hashtable_Add

10000

1,903.21 us

27.632 us

25.847 us

10

1,335 KB

ConcurrentDictionary_Add

10000

2,583.28 us

43.599 us

40.782 us

11

1,782 KB

ImmutableDictionary_Add

10000

12,779.01 us

206.515 us

183.070 us

12

9,601 KB

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

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

Method

Target

Mean

Error

StdDev

Rank

Gen 0

ConcurrentDictionary_Get 

100

    9.276 us 

0.0784 us 

0.0695 us 

1

      - 

Dictionary_Get 

100

    9.374 us 

0.0549 us 

0.0487 us 

1

      - 

Hashtable_Get 

100

    10.651 us 

0.0537 us 

0.0476 us 

2

0.7629

ImmutableDictionary_Get 

100

    14.019 us 

0.0436 us 

0.0340 us 

3

      - 

ConcurrentDictionary_Get 

1000

    84.548 us 

0.2929 us 

0.2596 us 

4

      - 

Dictionary_Get 

1000

    90.155 us 

0.3177 us 

0.2817 us 

5

      - 

Hashtable_Get 

1000

  108.548 us 

0.4798 us 

0.4253 us 

6

7.5684

ImmutableDictionary_Get 

1000

  140.010 us 

0.2568 us 

0.2276 us 

7

      - 

ConcurrentDictionary_Get 

10000

  891.774 us 

3.0775 us 

2.7281 us 

8

      - 

Dictionary_Get 

10000

  936.266 us 

2.9327 us 

2.7433 us 

9

      - 

Hashtable_Get 

10000

1,082.217 us 

7.7229 us 

6.8461 us 

10

76.1719

ImmutableDictionary_Get 

10000

1,391.331 us 

4.9817 us 

4.4161 us 

11

      - 

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

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

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


Method

Mean

Error

StdDev

Ratio

RatioSD

Gen 0

GetValueByKeyWithTryGet 

    7.550 ns 

  0.0767 ns 

  0.0718 ns 

0.96

0.02

      - 

GetValueByKey 

    7.864 ns 

  0.1307 ns 

  0.1158 ns 

1

0

      - 

GetValueByKeyManual 

  571.320 ns 

  7.4372 ns 

  6.5929 ns 

72.66

1.37

      - 

GetValueByKeyWithLinq 

1,839.986 ns 

30.7720 ns 

32.9257 ns 

234.3

5.68

0.0343


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

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

Комментарии (16)


  1. onets
    17.02.2022 14:07

    Жаль нет объяснения, почему ручной по ключу настолько медленней.


    1. EvgenyKlenov Автор
      17.02.2022 14:24

      Для ручного поиска используется цикл foreeach которая инициализирует Enumerator и мы бежим по все коллекции и сравиваем с Key - а это занимает время.
      Есть ссылка на репозиторий - посмотрите метод GetValueByKeyManual(string key)


    1. beskaravaev
      17.02.2022 14:51
      +2

      Для этого достаточно посмотреть на код в репе. Ручной, это проход форичем по словарю


  1. beskaravaev
    17.02.2022 15:03
    +1

    Кто в здравом уме будет использовать Linq для поиска чего-то в словаре?


  1. hornT
    17.02.2022 15:36

    Видно, что обычный Dictionary 100 записей вставляет за 12 наносекунд, а 1000 примерно за 120.от мы и получили почти O(1) сложность вставки одной записи!

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

    Время тут выросло в 10 раз, во столько же и нагрузка, что больше подходит под определение O(n)


    1. EvgenyKlenov Автор
      17.02.2022 15:45

      Тут идея в том что не важно какого размера словарь, время вставки +- одинаковое. Время выросло в 10 раз, т.к. вставляется в 10 раз больше чисел, то время и ростет в 10 раз.
      Линейный рост в данном случае будет если при вставке в 10 записей была 1 секунда, а при вставке в 100 записей - 10 секунд.


      1. hornT
        17.02.2022 15:50

        Так это как раз и есть O(n) - в 10 раз увеличилось кол-во данных, в 10 раз и время выросло. Линейная зависимость


        1. terrapod
          17.02.2022 15:57

          Нет. Это о1. Неважно ваш словарь 10 или 100 элементов вы все равно добавляете новый элемент за Х времени. Оно не растет (понятно, коллизии и прочие худшие не в счёт).

          Иначе по вашей логике доступ к элементу массива по индексу это о(н). Ведь если мне надо достать 1 элемент то это Х времени, а 10 элементов я достану за 10Х.


          1. hornT
            17.02.2022 16:08

            Признаю, был неправ. Почему то рассматривал вставку 100 и 1000 элементов как атомарные операции, хотя происходит вставка 1 элемента. И для этого тратится +- одинаковое время


            1. terrapod
              17.02.2022 16:17
              +1

              Да, речь о сложности добавления одного элемента конкретно здесь. Вот этот "+- одинаковое время", конечно, на практике часто выбивает цифры, особенно на тестах "запустил десяток раз с сотней элементов". Но в среднем о1.


  1. Korobei
    17.02.2022 18:17

    Было бы интересно переопределить GetHashCode, чтобы он всегда выдавал 1 (т.е. ситуация когда кто-то накосячил в реализации) и посмотреть как изменится производительность в случаях когда будет очень много коллизий.


  1. namee
    17.02.2022 19:22

    тема не раскрыта.

    в итоге ведь Dictionary это наследник HashTable

    +картина не полная без прочих таблиц аки List, Queue, e.t.c.


    1. EvgenyKlenov Автор
      17.02.2022 19:40

      List/Stack/Queue/LinkedList/ etc
      Это вообще другие структуры и к словарям отношения не имеют.


  1. NikolayPyanikov
    17.02.2022 21:33

    Dictionary<TKey,TValue> внутри себя использует массивы. ConcurrentDictionary<TKey, TValue> существенно медленней чем Dictionary<TKey,TValue> так как там есть еще дополнительный объект для хранения текущего состояния и в нем еще дополнительно массив для синхронизаций. И бакеты у него это не структуры как в Dictionary<TKey,TValue> а ссылочный тип. Поэтому, теоретически, он должен работать медленнее и создавать значительно больше трафика памяти, что будет напрягать GC.


    1. NikolayPyanikov
      17.02.2022 22:07
      +3

      Dictionary<TKey,TValue> - быстрый, но есть реализации, которые работают быстрее в плане Get, например здесь - там нет перебора по массиву и виртуальных вызовов для разрешения коллизий (в таблице он FastDictionary). Вот я померил на 1 миллионе элементов <string, int>:

      BenchmarkDotNet=v0.12.1, OS=Windows 10.0.22000
      Intel Core i7-10875H CPU 2.30GHz, 1 CPU, 16 logical and 8 physical cores
      .NET Core SDK=6.0.101
      
      |               Method |     Mean |    Error |   StdDev |   Median |
      |--------------------- |---------:|---------:|---------:|---------:|
      |       FastDictionary | 12.70 ns | 0.281 ns | 0.234 ns | 12.63 ns |
      |           Dictionary | 13.32 ns | 0.291 ns | 0.398 ns | 13.09 ns |
      | ConcurrentDictionary | 16.39 ns | 0.289 ns | 0.365 ns | 16.25 ns |
      

      А в вашем репо

      for (int i = 0; i < Target; i++)
      {
          var key = Guid.NewGuid();
          if (_concurrentDictionary.ContainsKey(key))
          {
              result = _concurrentDictionary[key];
          }
      }
      

      цикл, создаени ключа, вызов ContainsKey - очень дорогие операции, вы их и мерили скорее всего


  1. funny_falcon
    18.02.2022 13:09

    Как-то странно сравнивать с ConcurrentDictionary и с ImmutableDictionary, и не использовать потоков. Смысл в таком сравнении? "Если вам нужно нарезать хлеб, нет смысла брать швейцарский нож" - спасибо, кэп.

    А сравните в конкурентном доступе. 2/8/32/128 потока. 95/5 чтения/записи, 50/50 ч/з, 99.9/0.1, 1/99 - это всё разные паттерны, реально встречающиеся в жизни (ну, может кроме 1/99: обычно, даже если "только пишем", то всё равно читаем перед этим).

    Простите за недогование.