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