Реализация функций расстановки (хеширование) и различных методов разрешения коллизий

Постановка задачи

Хеш-таблица представляет базу данных предметной области, соответствующей варианту. Реализовать:

• · Выбор ключа для соответствующей базы данных.
• · По крайней мере, 3 различных функции хеширования для конкретных данных.
• · Заполнение таблицы для каждой функции.
• · Добавление новых данных для каждой функции.
• · Удаление данных.
• · Поиск данных по ключу.
• · Оценку качества хеширования для каждой функции.
• · Сравнение функций хеширования.

Краткое теоретическое положение

Хеш-таблица — структура данных, которая реализует интерфейс ассоциативного массива, т. е., хранит пары: ключ и значение и выполняет основные операции: добавление пары, удаление по ключу и поиск по ключу.

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

Метод разрешения коллизий: двойное хеширование. Двойное хеширование — основан на использовании двух хеш-функций. Коллизии возникают при открытой адресации. Берется значение hash1, если значение уже использовано, то вычисляется вторая вспомогательная функция, и берется значение hash1+hash2, hash1+2*hash2 и т. д.

Описание сферы практического применения используемого типа данных

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

Результаты работы программы

Рис 7. Пример работы 5-ой части программы

Таблица 3. Зависимость количества элементов от количества коллизий

Рис. 8. Зависимость количества элементов от количества коллизий