Метод хеш-поиска с разрешением конфликтов методом цепочек

Реализовать программно метод хеш-поиска с разрешением конфликтов методом цепочек.

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

Программа должна выполнять следующие действия:

- добавление нового ключа в таблицу с подсчетом сделанных при этом сравнений;

- поиск заданного ключа в таблице с подсчетом сделанных при этом сравнений;

- вывод текущего состояния таблицы на экран;
- удаление заданного ключа из таблицы.

Алгоритм удаления:

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

- если удаляемый элемент найден в списке, то производится его удаление с изменением указателей.

После отладки программы необходимо выполнить ее для разных соотношений числа исходных ключей и размерности таблицы: взять 20 ключей и разместить их поочередно в таблице размерности 9, 17 и 23. Для каждого случая найти суммарное число сравнений, необходимое для размещения ключей и их поиска. Сделать вывод о влиянии размерности таблицы на эффективность поиска.