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]. Однако, если мы будем случайно подбирать размеры массива, мы можем плохо распределять загрузку значений, например, много чисел имеет одинаковый остаток от деления на 2 или другую степень этого замечательного числа. В противовес этому, у простых чисел по определению только два делителя единица и само число, поэтому вероятность, что остаток от деления двух разных чисел на третье простое число окажется одинаковым очень мала. За счет этого мы гарантируем, что при нормально работающей хеш функции, бакеты будут заполнены равномерно.
Отдельно заметим, что в словаре, чтобы различить два объекта с одинаковым хешем, при запросе значения используется метод Equals.
На этом я закончу с разбором механизма работыDictionary. Тут я не упомянул о том, как обрабатывается удаление и затем вставка элементов, но для понимания того, почему в среднем словарь работает за это не нужно.
Сейчас поговорим немного о потокобезопасности. Пока разные потоки только читают данные из словаря, он будет потокобезопасным. Если же мы хотим как-то модифицировать словарь, то нам надо использовать ConcurrentDictionary, или ImmutableDictionary, или свой собственный механизм синхронизации доступа к данным. Важный момент, если при параллельном проходе по словарю через Parallel.ForEach (или каким-то другим способом) мы как-то модифицируем текущее значение, то такая операция не будет потокобезопасной.
Промежуточные итоги и рекомендации:

• Эффективность работы словаря зависит от качества хеш функции ключа. Если хеш функция дает много коллизий, словарь нас не спасет. При переопределении 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 поддерживает порядок ключей постоянным, операции выборки диапазонов ключей из него могут выполняться быстрее, нежели для обычного словаря.

Заключение.

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