Варианты задания
1. Тип ключа - строка текста произвольной длины. Преобразование строки - конкатенация битовых образов символов. Метод хеширования - модульный. Метод разрешения коллизий - линейный.
2. Тип ключа - вещественное число на интервале [-10 000.00 , +10 000.00]. Метод хеширования - мультипликативный. Метод разрешения коллизий - квадратичный.
3. Тип ключа - целое число на интервале [0 , +1 000 000 000]. Метод хеширования - выбор цифр. Метод разрешения коллизий - двойное хеширование.
4. Тип ключа - строка текста произвольной длины. Метод хеширования - модульный. Метод разрешения коллизий - линейное хеширование.
5. Тип ключа - вещественное число на интервале [100 000.00 , +150 000.00]. Метод хеширования - модульный. Метод разрешения коллизий - двойное хеширование.
6. Тип ключа - строка текста произвольной длины. Преобразование строки - конкатенация битовых образов символов. Метод хеширования - мультипликативный. Метод разрешения коллизий - квадратичный.
7. Тип ключа - вещественное число на интервале [-5 000.000 , +5 000.000]. Метод хеширования - свёртка. Метод разрешения коллизий - квадратичный.
8. Тип ключа - 12-значное натуральное число. Метод хеширования - свёртка, комбинированная с выбором цифр. Метод разрешения коллизий - квадратичный.
Методические указания по выполнению задания
1. Коллекции "Хеш-таблица с цепочками коллизий" и "Хеш-таблица с открытой адресацией" разрабатываются, как отдельные шаблонные классы-контейнеры.
2. Параметрами шаблона являются тип ключа, тип данных и класс-функция преобразования значения ключа в натуральное число.
Размер хеш-таблицы вычисляется конструктором коллекции в зависимости от заданного количества элементов с учётом типа хеш-таблицы, метода хеширования, указанного в варианте задания, и рекомендуемой величины ?. Рекомендуемые размеры хеш-таблицы (числа Мерсенне) для модульного хеширования:
2n |
d |
2n- d |
8 |
5 |
251 |
9 |
3 |
509 |
10 |
2 |
1 021 |
11 |
9 |
2 039 |
12 |
3 |
4 093 |
13 |
1 |
8 191 |
14 |
3 |
16 381 |
15 |
19 |
32 749 |
16 |
15 |
65 521 |
17 |
1 |
131 071 |
18 |
5 |
262 139 |
19 |
1 |
524 287 |
20 |
3 |
1 048 573 |
21 |
9 |
2 097 143 |
22 |
3 |
4 194 301 |
23 |
15 |
8 388 593 |
24 |
3 |
16 777 213 |
25 |
39 |
33 554 393 |
3. Для тестирования разработанного класса - контейнера разрабатываются две программы - программа тестирования операций через меню, и программа тестирования трудоёмкости операций поиска, вставки и удаления.
4. Тестирование операций через меню выполняется для небольшого размера таблицы (до 7-8 элементов). Тип данных, хранящихся в нём, задаётся с клавиатуры перед началом тестирования. После выполнения операции необходимо выводить на экран содержимое структуры хеш-таблицы с помощью операции вывода её структуры. При выводе структуры следует отражать состояние, как свободных, так и занятых позиций хеш-таблицы, содержимое цепочек коллизий.
5. В результате тестовых испытаний хеш - функции получить функцию распределения ключей по пространству:
где P - количество ключей, использованных для получения распределения,
m- размер хеш - таблицы,
fi - количество ключей с хеш-значением, равным i [8].
Если использованные ключи являются
случайными на всём пространстве значений
ключей U, значение функции c2 должно
быть равно
с
вероятностью 1 - 1/c, где c=U/m.
6. Для получения оценки c2 использовать количество ключей, минимум в 20 раз превышающее размер хеш-таблицы.
7. Перед тестированием эффективности операций для обеих коллекций задаются тип данных и количество элементов в таблице.