Dictionary и SortedDictionary

Dictionary и SortedDictionary.

Всем привет. Сегодня я планирую рассказать в общих чертах о Dictionary и SortedDictionary в .NET - как они устроены и в чем различие между ними.

Зачем?

Во-первых, меня пару раз об этом спросили на собеседованиях и в первый раз я вообще потерялся с ответом, что было не самым приятным опытом, от которого я хочу вас избавить. Во-вторых, словарь - одна из самых часто используемых структур данных и при разработке бывает полезно понимать, какие у нее есть подводные, а также знать, когда использование SortedDictionary оправдано.

Dictionary.

Внутреннее устройство.

Для начала разберемся с Dictionary<TKey, TValue>. Это коллекция пар ключ-значение. Ключ должен быть уникальным. В среднем получение, добавление, удаления элемента из нее происходит за . Как же это происходит? Давайте разбираться.
Внутри словарь использует структуру под названием Entry и два массива buckets и entries.

private struct Entry {
  public int hashCode; // хеш код, вычисленный для ключа
  public int next;     // индекс следующего элемента с тем же хешем, -1, если текущий элемент последний 
  public TKey key;
  public TValue value;
}

private int[] buckets;   // индексы начала бакетов
private Entry[] entries; // элементы словаря

Каждый элемент хранится в бакете, который соответствует остатку от деления хеша от ключа на размер массива buckets. Отметим, что у нас возможны коллизии, когда два разных ключа дают одинаковый хеш. В этом случае у нас в бакете будет связный список элементов.

Коллизии

Пока мы поддерживаем размеры бакетов небольшими (0-3 элемента) и само их количество соразмерно числу элементов (в идеале каждый бакет содержит 0 или 1 элемент), мы получаем усредненный доступ за , так как внутри мы берем элемент из массива по его индексу. Для реализации подобной структуры (массив, содержащий связные списки) используются два массива buckets и entries. В массиве bucket индекс - номер бакета, а значение - начало связного списка с элементами из entries.

Пример, как может выглядеть массив

По мере роста числа элементов, размер массивов так же увеличивается. В каждый момент времени размер массива buckets является простым числом. Причем тут простые числа? Сейчас узнаем.
Чтобы определить, в какой бакет положить добавляемую пару, внутри словаря вычисляется хеш от ключа [1]. Затем мы берем остаток от деления этого хеша на размер массива buckets и кладем нашу пару в индекс с полученным значением. Таким образом мы гарантируем, что любой результат хеш функции будет в пределах размера массива buckets [2].

Однако, если мы будем случайно подбирать размеры массива, мы можем плохо распределять загрузку значений. Например, увеличивать размер массива бакетов всегда в два раза будет плохой идеей и не только по памяти. А вот простые числа подойдут отлично. Связано это с паттернами, которые возникают у обычных чисел, но сильно реже встречаются у простых.

Пример

Для чисел: 16, 32, 48, 64, 80, 96, 112, 128. Если взять 32 бакета, распределение будет следующее:

• 16 % 32 = 16

• 32 % 32 = 0

• 48 % 32 = 16

• 64 % 32 = 0

• 80 % 32 = 16

• 96 % 32 = 0

• 112 % 32 = 16

• 128 % 32 = 0

Если же мы возьмем 31 бакет, то несмотря на меньший размер, мы полчим более равномерное распределение:

• 16 % 31 = 16

• 32 % 31 = 1

• 48 % 31 = 17

• 64 % 31 = 2

• 80 % 31 = 18

• 96 % 31 = 3

• 112 % 31 = 19

• 128 % 31 = 4

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

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

На этом я закончу с разбором механизма работыDictionary. Тут я не упомянул о том, как обрабатывается удаление и затем вставка элементов, но для понимания того, почему в среднем словарь работает за это не нужно.

Потокобезопасность Dictionary.

Сейчас поговорим немного о потокобезопасности. Пока разные потоки только читают данные из словаря, он будет потокобезопасным. Если же мы хотим как-то модифицировать словарь, то нам надо использовать ConcurrentDictionary, или ImmutableDictionary, или свой собственный механизм синхронизации доступа к данным. Важный момент, если при параллельном проходе по словарю через Parallel.ForEach (или каким-то другим способом) мы как-то модифицируем текущее значение, то такая операция не будет потокобезопасной.

Итоги и рекомендации по Dictionary:

• Эффективность работы словаря зависит от качества хеш функции ключа. Если хеш функция дает много коллизий, словарь нас не спасет. При переопределении GetHashCode для использования объектов класса в качестве ключа следует помнить об этом.

• Если у нас постоянно растет число элементов в словаре, имеет смысл сразу задать какое-то простое число в качестве начальной вместимости словаря. Это поможет избежать нагрузки связанной с пересозданием массивов buckets и entries при расширении.

• Если два ключа имеют одинаковый результат хеш функции, то дальше они сравниваются по Equals.

• Сам Dictionary является потокбезопасным, пока разные потоки только читают данные из него. В других случаях следует обеспечить синхронизацию или использовать ConcurrentDictionary, ImmutableDictionary.

SortedDicitonary.

Внутреннее устройство.

Как следует из названия SortedDictionary<TKey, TValue> - коллекция пар ключ-значение, которая все время отсортирована по ключам. Ключ, как и в случае с обычным словарем, должен быть уникальным. Однако дальше идут различия. Скорость работы с элементами отсортированного словаря равна , где - количество элементов в словаре, при этом иногда это будет быстрее, чем для обычного словаря. С чем это связано? Со внутренней реализацией.

Внутри SortedDictionary представляет собой бинарное дерево поиска. Здесь уже не используется GetHashCode и остатки от деления. Сравнение происходит через стандартный IComparable<TKey> для TKey или через переданный в конструкторе для SortedDictionary объект IComparer<TKey>. Поэтому SortedDictionary не страдает от частых коллизий, что даст нам более эффективное взаимодействие нежели с обычным словарем в данном сценарии. Само бинарное дерево поиска - структура данных, для которой верно следующее утверждение:

Каждая вершина имеет от 0 до 2 потомков, все элементы в левом поддереве меньше или равны значению в родительской вершине, а все элементы в правом поддереве больше значения в родительской.

Существуют разные виды бинарных деревьев поиска, отличающихся по подходу к балансировке, в частности в SortedDictionary используется красно-черное дерево. Но в особенности построения деревьев в данной статье я углубляться не буду, может быть в другой раз.
Для нас главное понимать временную сложность операций в SortedDictionary, а так же с чем она связана.

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

Итоги и рекомендации по SortedDictionary:

• Если для нас важен порядок ключей в словаре, следует использовать SortedDictionary. Главное помнить, что сложность выполнения операций в среднем .

• Если нам нужен только отстортированный вывод, а все остальное время порядок ключей не играет роли, можно подумать в сторону обычного словаря.

• Если нам нужна коллекция пар ключ-значение, но хеши ключей часто дают коллизии, имеет смысл использовать SortedDictionary вместо обычного. Так же это важно, когда речь идет о предсказуемости сложности операций, для хеша она зависит от хеш функции, а порой нам важнее предсказуемость сложности, нежели скорость выполнения операций.

• Так как SortedDictionary поддерживает порядок ключей постоянным, операции выборки диапазонов ключей из него могут выполняться быстрее, нежели для обычного словаря.

Заключение.

После того, как мы узнали, как работают внутри Dictionary и SortedDictionary, мы можем понять особенности работы с каждой из этих структур данных. Надеюсь, эта статья была вам полезна и вы смогли чуть лучше понять, как и когда стоит использовать эти структуры данных.