ПРИМЕЧАНИЕ

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

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

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

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

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

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