РК2 - wcdbmv/ADS GitHub Wiki
1. Опишите хеш-функцию целочисленных ключей, реализованную методом деления. Какие значения параметров приемлемы?
2. Опишите хеш-функцию целочисленных ключей, реализованную методом умножения. Как вычислять ее значения для целочисленных ключей без использования операций над числами с плавающей точкой?
3. Опишите классическую хеш-функцию для строк и метод Горнера для ее реализации. Какие значения параметров приемлемы?
// Хеш-функция строки.
int Hash(const char* str, int m) {
int hash = 0;
for (; *str; ++str)
hash = (hash * a + *str) % m;
return hash;
}
4. Опишите операции поиска, добавления и удаления ключей в хеш-таблицу, реализованную методом цепочек.
Добавление ключа.
- Вычисляем значение хеш-функции добавляемого ключа – h.
- Находим A[h] – указатель на список ключей.
- Вставляем в начало списка (в конец списка дольше). Если запрещено дублировать ключи, то придется просмотреть весь список.
Время работы:
- В лучшем случае – O(1).
- В худшем случае
- если не требуется проверять наличие дубля, то O(1),
- иначе – O(N).
Удаление ключа.
- Вычисляем значение хеш-функции удаляемого ключа – h.
- Находим A[h] – указатель на список ключей.
- Ищем в списке удаляемый ключ и удаляем его.
Время работы:
- В лучшем случае – O(1).
- В худшем случае – O(N).
5. Оцените среднее время работы операции поиска в хеш-таблице, реализованной методом цепочек.
6. Опишите операции поиска, добавления и удаления ключа в хеш-таблицу, реализованную методом открытой адресации.
Вставка ключа.
- Вычисляем значение хеш-функции ключа – h.
- Систематически проверяем ячейки, начиная от A[h], до тех пор, пока не находим пустую ячейку.
- Помещаем вставляемый ключ в найденную ячейку.
В п.2 поиск пустой ячейки выполняется в некоторой последовательности. Такая последовательность называется «последовательностью проб».
Последовательность проб зависит от вставляемого в таблицу ключа. Для определения исследуемых ячеек расширим хеш-функцию, включив в нее номер пробы (от 0).
h: U × {0, ..., M-1} -> {0, ..., M-1}
Важно, чтобы для каждого ключа k последовательность проб
[h(k, 0), h(k, 1), ..., h(k, M-1)]
представляла собой перестановку множества [0, 1, ..., M-1], чтобы могли быть просмотрены все ячейки таблицы.
Поиск ключа.
Исследуется та же последовательность, что и в алгоритме вставки ключа.
Если при поиске встречается пустая ячейка, поиск завершается неуспешно, поскольку искомый ключ должен был бы быть вставлен в эту ячейку в последовательности проб, и никак не позже нее.
Удаление ключа. Алгоритм удаления достаточен сложен. Нельзя при удалении ключа из ячейки i просто пометить ее значением NIL. Иначе в последовательности проб для некоторого ключа (или некоторых) возникнет пустая ячейка, что приведет к неправильной работе алгоритма поиска.
Решение. Помечать удаляемые ячейки спец. значением «Deleted».
Нужно изменить методы поиска и вставки. В методе вставки проверять «Deleted», вставлять на его место. В методе поиска продолжать поиск при обнаружении «Deleted».
7. Опишите способ квадратичного пробирования.
8. Опишите способ пробирования методом двойного хеширования.
