2015-05-10
1017
Тема: Хеширование для организации быстрого поиска данных.
Цель: Получить навыки по разработке хеш таблиц.
Задание
1. Разработайте шаблонный класс – хеш таблица, для поиска информации в коллекциях данных с помощью хеш функции. Хеш функцию подберите самостоятельно.
2. Разработайте приложение, которое использует хеш таблицу для организации прямого доступа к элементам множества (массив данных), структура элементов которого приведена в варианте. Множество реализуйте через класс - шаблон с операциями вставки, удаления, поиска, вывода и включите в него хеш таблицу. Предусмотрите возможность создания наследников хеш-таблицы.
3. Разработайте такие тесты, чтобы возникли коллизии.
4. Выведите список индексов, которые формируются при вставке элементов в таблицу.
ВАРИАНТЫ
| № | Метод хеширования (способ реализации коллизий) | Структура элемента множества(ключ – подчеркнутое поле) |
| С открытой адресацией (увеличение на 1) | Читательский абонемент: номер читательского - целое пятизначное число, ФИО, Адрес | |
| С открытой адресацией(увеличение на номер выполняемого подбора) | Счет в банке: номер счета 7 разрядное число, ФИО, Адрес | |
| С открытой адресацией (двойное хеширование) | Владелец телефона: номер телефона – последовательность символов, адрес | |
| Цепное хеширование | Владельцев автомобилей. номер машины, марка, сведения о владельце. | |
| Цепное хеширование | Пациент поликлиники: номер карточки, код хронического заболевания, Фамилия лечащего врача | |
| Цепное хеширование | Товар: название, код – шестиразрядное число | |
| Цепное хеширование | Специализация вуза: код специальности, название вуза | |
| Открытый адрес(двойное хеширование) | Книга: ISBN – двенадцатизначное число, Автор, Название | |
| Цепное хеширование | Страховой полис: номер, компания, фамилия владельца | |
| Открытый адрес(увеличение на 1) | Англо – русский словарь: английское слово, русское слово | |
| Открытый адрес(двойное хеширование) | Железнодорожная справка: номер поезда, пункт отправления, пункт назначения, время отправления | |
| Цепное хеширование | Регистрация малого предприятия: номер лицензии, название, учредитель | |
| Открытый адрес(двойное хеширование) | Студент: номер зачетной книжки, номер группы ФИО | |
| Цепное хеширование | Справочная межгорода: код города, название города | |
| Открытый адрес(увеличение на 1) | Проверка проавописания по словарю правильных слов: слово (в тексте найти слова с орфографическими ошибками) | |
| Цепное хеширование | Частотный словарь: слово, количество вхождений в текст | |
|
|
|
