Типы коллекций Hashtable и Dictionary

Статья
08/11/2011

Класс System.Collections.Hashtable, а также универсальные классы System.Collections.Generic.Dictionary<TKey, TValue> и System.Collections.Concurrent.ConcurrentDictionary<TKey, TValue>, реализуют интерфейс System.Collections.IDictionary. Универсальный класс Dictionary<TKey, TValue> также реализует универсальный интерфейс IDictionary<TKey, TValue>. Поэтому каждый элемент в этих коллекциях является парой "значение-ключ".

Объект Hashtable состоит из сегментов, содержащих элементы коллекции. Сегмент — это виртуальная подгруппа элементов внутри объекта Hashtable, позволяющая упростить и ускорить поиск и извлечение элементов по сравнению с большинством коллекций. С каждым сегментом связан хэш-код, который создается с помощью хэш-функции и основан на ключе элемента.

Универсальный класс HashSet<T> — это неупорядоченная коллекция для хранения уникальных элементов. Дополнительные сведения об этой коллекции см. в разделе Тип коллекции HashSet.

Хэш-функция — это алгоритм, вычисляющий числовой хэш-код на основе ключа. Ключом является значение какого-либо свойства хранимого объекта. Хэш-функция всегда должна возвращать один и тот же хэш-код для одного и того же ключа. Возможна ситуация, когда хэш-функция создает один хэш-код для разных ключей. Однако хэш-функция, создающая уникальный хэш-код для каждого уникального ключа, обеспечивает лучшую производительность при извлечении элементов из хэш-таблицы.

Каждый объект, который используется в качестве элемента в Hashtable, должен иметь возможность создать свой хэш-код, используя реализацию метода GetHashCode. Также можно указать хэш-функцию для всех элементов в Hashtable, используя конструктор Hashtable, принимающий реализацию IHashCodeProvider в качестве одного из своих параметров.

Когда объект добавляется в Hashtable, он сохраняется в сегменте, который связан с хэш-кодом, соответствующим хэш-коду объекта. При поиске значения в Hashtable создается хэш-код для этого значения, и поиск осуществляется в сегменте, связанном с этим хэш-кодом.

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

Функциональность классов Dictionary<TKey, TValue> и ConcurrentDictionary<TKey, TValue>аналогична функциональности класса Hashtable. Объект Dictionary<TKey, TValue> конкретного типа (отличного от Object) обеспечивает более высокую производительность, чем Hashtable для типов значений. Это происходит потому, что элементы объекта Hashtable имеют тип Object; следовательно, при сохранении или извлечении типа значения происходит упаковка или распаковка. Класс ConcurrentDictionary<TKey, TValue> следует использовать в случаях, когда к коллекции могут обращаться несколько потоков одновременно.