В прошлой статье мы с Вами начали помогать моему ученику решать лабораторную работу по хэшированию данных. Мы провели анализ и выбрали подходящую хэш-функцию. Теперь же нам нужно применить ее на практике для реализации программы по работе с хэш-таблицей.
Задание на лабораторную работу:
Используя полученную хеш-функцию разработать программу, которая должна выполнять следующие функции:
* создавать хеш-таблицу;
* просматривать хеш-таблицу;
* добавлять/удалять элементы в хеш-таблицу;
* искать элементы в хеш-таблице по номеру сегмента/по ключу;
* при удалении элементов из хэш-таблицы, реализовать алгоритм, позволяющий искать элементы, вызвавшие коллизию с удаленным;
* реализовать алгоритм, обрабатывающий ситуации с переполнением хэш-таблицы.
Начнем по порядку, с создания и просмотра хэш-таблицы. Как вы уже знаете, в хэш-таблицах мы храним пару значений: ключ плюс сами данные. Объявим структуру для хранения такой пары:
Количество сегментов будущей хэш-таблицы у нас хранится в переменной NumOfSegments (для отладки сделаем 30 элементов). Структурой для реализации хэш-таблицы я бы выбрала vector, но помним, что по правилам лабораторной работы, использовать STL-кие контейнеры запрещено. Поэтому используем стандартный массив указателей на новую структуру:
Функция FillHashTableWithRandomData генерирует указанное количество случайных ключей, а в качестве данных мы решили использовать просто номер по порядку.
Результат работы программы (1й столбец – индекс ячейки хэш-таблицы, 2й – ключ, 3й - данные):
На скриншоте видно, что у нас остались две свободные ячейки с индексами 4 и 5. Мы специально заполнили таблицу не полностью, чтобы протестировать различные случаи добавления новых записей в нашу хэш-таблицу.
Теперь рассмотрим подробнее функцию добавления элемента в таблицу:
Здесь у нас реализована проверка уникальности добавляемых ключей, вычисление адреса по ключу (наша хэш-функция, нормализованная, чтобы вычисляемый адрес лежал в диапазон индексов нашего массива), проверка переполнения таблицы, а также обработка возможных коллизий. По заданию лабораторной работы разрешение коллизий мы должны выполнять методом линейного опробования.
Ознакомившись детальнее с нужным нам методом, мы с учеником сделали вывод, что нам придется использовать его также при поиске и удалении элементов. Поэтому давайте вынесем этот кусочек кода, связанный с методом разрешения коллизий, в отдельную функцию и модифицируем функцию вставки:
Результат работы тестов на вставку:
А так выглядит функция поиска:
И результаты поиска в хэш-таблице по ключу и по номеру сегмента:
Теперь нам осталось написать функцию удаления элемента из хэш-таблиц, не забывая после удаления обрабатывать элементы, вызывающие коллизию с удаленным:
Осталось потестировать удаление:
А теперь выведем на экран хэш-таблицу после удаления элементов:
Обратите внимание на элементы с 25 и до конца таблицы: благодаря тому, что мы корректно написали функцию удаления с учетом коллизий, все элементы после удаленного сдвинулись вверх по таблице.
Ну что же, программа для лабораторной работы готова, с темой хэширования ученик ознакомился и закрепил новые знания на практике.
Если у Вас появились вопросы на эту тему и не только - Вы всегда можете задать их мне в комментариях или в группе в ВК.