Словари. ContainsKey()

Словари

Еще один распространенный тип коллекции представляют словари. Словарь хранит объекты, которые представляют пару ключ-значение. Каждый такой объект является объектом структуры KeyValuePair<TKey, TValue>. Благодаря свойствам Key и Value, которые есть у данной структуры, мы можем получить ключ и значение элемента в словаре.

На следующем рисунке представлена упрощенная модель словаря. Здесь ключами словаря служат идентификаторы сотрудников, такие как В4711. Ключ трансформируется в хеш. В хеше создается число для ассоциации индекса со значением. После этого индекс содержит ссылку на значение. Изображенная модель является упрощенной, поскольку существует возможность того, что единственное вхождение индекса может быть ассоциировано с несколькими значениями, и индекс может храниться в виде дерева.

В .NET Framework предлагается несколько классов словарей. Главный класс, который можно использовать — это Dictionary<TKey, TValue>.

Тип ключа

Тип, используемый в качестве ключа словаря, должен переопределять метод GetHashCode() класса Object. Всякий раз, когда класс словаря должен найти местоположение элемента, он вызывает метод GetHashCode().

Целое число, возвращаемое этим методом, используется словарем для вычисления индекса, куда помещен элемент. Мы не станем углубляться в подробности работы этого алгоритма. Единственное, что следует знать — это то, что он использует простые числа, так что емкость словаря всегда выражается простым числом.

Реализация метода GetHashCode() должна удовлетворять перечисленным ниже требованиям:

Один и тот же объект должен всегда возвращать одно и то же значение.

Разные объекты могут возвращать одно и то же значение.

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

Он не должен генерировать исключений.

Он должен использовать как минимум одно поле экземпляра.

Значения хеш-кода должны распределяться равномерно по всему диапазону чисел, которые может хранить int.

Хеш-код не должен изменяться на протяжении времени существования объекта.

Чем вызвана необходимость равномерного распределения значений хеш-кода по диапазону целых чисел? Если два ключа возвращают хеш-значения, дающие один и тот же индекс, класс словаря вынужден искать ближайшее доступное свободное место для сохранения второго элемента, к тому же ему придется выполнять некоторый поиск, чтобы впоследствии извлечь требуемое значение. Понятно, что это наносит ущерб производительности, и если множество ключей дают одни и те же индексы, куда их следует поместить, вероятность конфликтов значительно возрастает. Однако благодаря способу, которым работает часть алгоритма, принадлежащая Microsoft, риск снижается до минимума, когда вычисляемое значение хеш-кода равномерно распределено между int.MinValue и int.MaxValue.

Помимо реализации GetHashCode() тип ключа также должен реализовывать метод IEquatable<T>.Equals() либо переопределять метод Equals() класса Object. Поскольку разные объекты ключа могут возвращать один и тот же хеш-код, метод Equals() используется при сравнении ключей словаря. Словарь проверяет два ключа А и В на эквивалентность, вызывая A.Equals(В). Это означает, что потребуется обеспечить истинность следующего утверждения:

Если истинно А.Equals(В) , значит, А.GetHashCode() и В.GetHashCode() всегда должны возвращать один и тот же хеш-код.

Класс Dictionary<TKey, TValue>

В классе Dictionary<TKey, TValue> реализуются интерфейсы IDictionary, IDictionary<TKey, TValue>, ICollection, ICollection<KeyValuePair<TKey, TValue>>, IEnumerable, IEnumerable<KeyValuePair<TKey, TValue>>, ISerializable и IDeserializationCallback. В двух последних интерфейсах поддерживается сериализация списка. Словари имеют динамический характер, расширяясь по мере необходимости.

В классе Dictionary<TKey, TValue> предоставляется немало конструкторов. Ниже перечислены наиболее часто используемые из них:

public Dictionary()

public Dictionary(IDictionary<TKey, TValue> dictionary)

public Dictionary(int capacity)

В первом конструкторе создается пустой словарь с выбираемой по умолчанию первоначальной емкостью. Во втором конструкторе создается словарь с указанным количеством элементов dictionary. А в третьем конструкторе с помощью параметра capacity указывается емкость коллекции, создаваемой в виде словаря. Если размер словаря заранее известен, то, указав емкость создаваемой коллекции, можно исключить изменение размера словаря во время выполнения, что, как правило, требует дополнительных затрат вычислительных ресурсов.

В классе Dictionary<TKey, TValue> определяется также ряд методов:

Add()

Добавляет в словарь пару "ключ-значение", определяемую параметрами key и value. Если ключ key уже находится в словаре, то его значение не изменяется, и генерируется исключение ArgumentException

ContainsKey()

Возвращает логическое значение true, если вызывающий словарь содержит объект key в качестве ключа; а иначе — логическое значение false

⇐ Предыдущая 1 234 Следующая ⇒