сказать, что это таблица, состоящая из пар ключ-значение (табл. 13.1). Хеш-таблица эффективно реализует операцию поиска значения по ключу. При этом ключ преобразуется в число (хеш-код), которое используется для быстрого нахождения нужного значения в хеш-таблице.

Таблица 13.1. Пример хеш-таблицы Ключ Значение

boy мальчик

girl девочка

dog собачка

Преобразование выполняется с помощью хеш-функции, или функции расстановки. Эта функция обычно производит какие-либо преобразования внутреннего представления ключа, например, вычисляет среднее арифметическое кодов составляющих его символов (английское слово hash означает перемалывать, перемешивать). Если хеш-функция распределяет совокупность возможных ключей равномерно по множеству индексов массива, то доступ к элементу по ключу выполняется почти так же быстро, как в массиве. Если хеш-функция генерирует для разных ключей одинаковые хеш-коды, время поиска возрастает и становится сравнимым со временем поиска в списке.

ПРИМЕЧАНИЕ-

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

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

Граф - это совокупность узлов и ребер, соединяющих различные узлы. Например, можно представить себе карту автомобильных дорог как граф с городами в качестве узлов и шоссе между городами в качестве ребер. Множество реальных практических задач можно описать в терминах графов, что делает их структурой данных, часто используемой при написании программ.

Множество - это неупорядоченная совокупность элементов. Для множеств определены операции проверки принадлежности элемента множеству, включения и исключения элемента, а также объединения, пересечения и вычитания множеств.

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

В библиотеках большинства современных объектно-ориентированных языков программирования представлены стандартные классы, реализующие основные

Пространство имен System.Collections

В пространстве имен System.Collections определены наборы стандартных коллекций и интерфейсов, которые реализованы в этих коллекциях. В табл. 13.2 приведены наиболее важные интерфейсы, часть из которых мы уже изучали в разделе Стандартные интерфейсы .NET (см. с. 198).

Таблица 13.2. Интерфейсы пространства имен System.Collections Интерфейс Назначение

ICol 1 ecti on Определяет общие характеристики (например, размер)

для набора элементов

I Compare г Позволяет сравнивать два объекта

IDictionary Позволяет представлять содержимое объекта в виде пар

имя-значение

IDictionaryEnumerator Используется для нумерации содержимого объекта, поддерживающего интерфейс IDictionary

абстрактные структуры данных. Такие классы называются коллекциями, или контейнерами. Для каждого типа коллекции определены метод1 работы с ее элементами, не зависящие от конкретного типа данных, которые хранятся в коллекции, поэтому один и тот же вид коллекции можно использовать для хранения данных различных типов. Использование коллекций позволяет сократить сроки разработки программ и повысить их надежность.

ВНИМАНИ Е-:-

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

В библиотеке .NET определено множество стандартных классов, реализующих большинство перечисленных ранее абстрактных структур данных. Основные пространства имен, в которых описаны эти классы, - System.Collections, System. Col 1 ecti ons. Speci al i zed и System. Col 1 ecti ons. Generi с (начиная с версии 2.0). В следующих разделах кратко описаны основные элементы этих пространств имен.

ПРИМЕЧАНИЕ-

Класс System. Array, представляющий базовую функциональность массива, описан в разделе Класс System.Array (см. 6. 133).

Таблица 13.2 Интерфейс IEnumerable IEnumerator

(продолжение)

Назначение

Возвращает интерфейс IEnumerator для указанного объекта

Обычно используется для поддержки оператора foreach в отношении объектов

IHashCodeProvider

I Li st

Возвращает хеш-код для реализации типа с применением выбранного пользователем алгоритма хеширования

Поддерживает методы добавления, удаления и индексиров элементов в списке объектов

В табл. 13.3 перечислены основные коллекции, определенные в пространс System. Collections .

Таблица 13.3. Коллекции пространства имен

Класс Назначение

ArrayList Массив, динамически

изменяющий свой размер

Bit.Array Компактн1й массив ддля

хранения битовых значений

Hashtable Хеш-таблица2 Queue Очередь

SortedList Коллекция, отсортированная по ключам. Доступ к элементам - по ключу или по индексу

System.Collections

Важнейшие из реализованных интерфейс IList, ICollection, IEnumerable, ICloneabl

I Col lection, IEnumerable, ICloneable

IDictionary, ICollection, IEnumerable, ICloneable

ICollection, ICloneable, IEnumerable

IDictionary, ICollection, IEnumerable, ICloneable

Stack

Стек

ICollection, IEnumerable

Пространство имен System.Collections.Specialized включает специализиро ные коллекции, например коллекцию строк StringCollection и хеш-таблицу строковыми ключами StringDictionary.

В качестве примера стандартной коллекции рассмотрим класс ArrayLi st.

Класс ArrayList

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

Таблицы 13.2 и 13.3 приводятся по [27] и документации. У типов, экземпляры которгх преддназначен! ддля хранения в объекте класса Hashtabl должен бгть замещен метод System.Object.GetHashCode.