4)Структуры данных, основанные на хеш-таблицах.

Существует метод реализации словарей, который называется хешированием.

Формы хеширования:

1)открытое, или внешнее хеширование - позволяет хранить множества в потенциально бесконечном пространстве, снимая тем самым ограничения на размер множеств.

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

Открытое хеширование

Основная идея заключается в том, что потенциальное множество (возможно, бесконечное) разбивается на конечное число классов.

Для В классов, пронумерованных от 0 до В-1, строится хеш-функция h, которая для любого элемента х исходного мн-ва h(x) принимает целочисленное значение от 0, ..., В-1, соответствующее классу, кот. принадлежит х.

Элемент х часто называют ключом, h(x) - хеш-значением х, а "классы" - сегментами. Массив, называемый таблицей сегментов и проиндексированный номерами сегментов 0, 1, ..., В-1, содержит заголовки для В списков. Элемент х i-ro списка - это элемент исходного множества, для которого h(x)=i.

Если сегменты примерно одинаковы по размеру, то в этом случае списки всех сегментов должны быть наиболее короткими при данном числе сегментов. Если исходное множество состоит из N элементов, тогда средняя длина списков будет N/B элементов.

Если можно оценить величину N и выбрать В как можно ближе к этой величине, то в каждом списке будет 1-2 элемента. Тогда время выполнения операторов словарей будет малой постоянной величиной, зависящей от N (или, что эквивалентно, от В).

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

Ниже показан простой сп-б построения фун-и h, причем h(x) – случ-е значение.

Введем хеш-функцию, определенную на символьных строках.

В этой функции суммируются все целочисленные коды символов, результат суммирования делится на В и берется остаток от деления, который будет целым числом из интервала от 0 до В-1.

Закрытое хеширование

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

При закрытом хешировании применяется методика повторного хеширования.

Если мы попытаемся поместить элемент х в сегмент с номером h(x), который уже занят другим элементом (такая ситуация называется коллизией), то в соответствии с методикой повторного хеширования выбирается последовательность других номеров сегментов h1(x), h2(x), ..., куда можно поместить элемент х.

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

Если свободных сегментов нет, то, следовательно, таблица заполнена и элемент х вставить нельзя.

Билет №15.

1)Создание и использование статических библиотек в операционной системе Windows. Создание и использование динамических библиотек в операционной системе Windows: раннее и позднее связывание.

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

Динамическая библиотека представляет собой тоже хранилище функции(ий), но используется библиотека уже после компилирования вашего проекта. (она подключается дополнительно к вашему исполняемому модулю во время его работы). Пример динамических библиотек в системной папке windows/system32.

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

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

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

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