Dictionary и SortedDictionary
Всем привет. Сегодня я планирую рассказать в общих чертах о Dictionary и SortedDictionary в .NET — как они устроены и в чем различие между ними.
Зачем?
Во-первых, меня пару раз об этом спросили на собеседованиях и в первый раз я вообще потерялся с ответом, что было не самым приятным опытом, от которого я хочу вас избавить. Во-вторых, словарь — одна из самых часто используемых структур данных и при разработке бывает полезно понимать, какие у нее есть подводные, а также знать, когда использование SortedDictionary оправдано.
Dictionary.
Для начала разберемся с Dictionary. Это коллекция пар ключ-значение. Ключ должен быть уникальным. В среднем получение, добавление, удаления элемента из нее происходит за 
. Как же это происходит? Давайте разбираться.
Внутри словарь использует структуру под названием 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 или другую степень этого замечательного числа. В противовес этому, у простых чисел по определению только два делителя единица и само число, поэтому вероятность, что остаток от деления двух разных чисел на третье простое число окажется одинаковым очень мала. За счет этого мы гарантируем, что при нормально работающей хеш функции, бакеты будут заполнены равномерно.
На этом я закончу с Dictionary. Тут я не упомянул о том, как обрабатывается удаление и затем вставка элементов, но для понимания того, почему в среднем словарь работает за 
это не нужно.
SortedDicitonary.
Как следует из названия SortedDictionary — коллекция пар ключ-значение, которая все время отсортирована по ключам. Ключ, как и в случае с обычным словарем, должен быть уникальным. Однако дальше идут различия. Скорость работы с элементами отсортированного словаря равна 
, где 
— количество элементов в словаре. С чем это связано? Со внутренней реализацией.
Внутри SortedDictionary представляет собой бинарное дерево поиска. Здесь уже не используется GetHashCode и остатки от деления. Сравнение происходит через стандартный IComparable для TKey или через переданный в конструкторе для SortedDictionary объект IComparer. Само бинарное дерево поиска — структура данных, для которой верно следующее утверждение:
Каждая вершина имеет от 0 до 2 потомков, все элементы в левом поддереве меньше или равны значению в родительской вершине, а все элементы в правом поддереве больше значения в родительской.
Существуют разные виды бинарных деревьев поиска, отличающихся по подходу к балансировке, в частности в SortedDictionary используется красно-черное дерево. Но в особенности построения деревьев в данной статье я углубляться не буду, может быть в другой раз.
Для нас главное понимать временную сложность операций в SortedDictionary, а так же с чем она связана.
Заключение.
После того, как мы узнали, как работают внутри Dictionary и SortedDicionary, мы можем понять особенности работы с каждой из этих структур данных. Если нам не важен порядок ключей в коллекции ключ-значение, мы используем Dictionary. Если мы хотим на полную использовать словарь, нам нужно обеспечить хорошую хеш функцию для ключа, а так же постараться избегать постоянного переопределения числа бакетов, поэтому для изначально больших словарей имеет смысл задать размер сразу. Если же нам важно поддерживать порядок ключей в словаре ВСЕ ВРЕМЯ работы с ним, то нам следует использовать SortedDictionary, но помнить о том, что его скорость работы 
.
Надеюсь, эта статья была вам полезна и вы смогли чуть лучше понять, как и когда стоит использовать эти структуры данных.
