Детали двойного хеширования

Question

В настоящее время я готовлюсь к выпускному экзамену для своего класса алгоритмов, и я наткнулся на несколько вопросов в практическом тесте, в которых я не был уверен. Любая помощь будет оценена!

Что из нижеперечисленного не относится к последовательностям зондов для реализации двойного хеширования?

A. Два ключа могут иметь одинаковую последовательность проб

B. Все слоты в хеш-таблице появляются в каждой последовательности проб

С. Элементы последовательности проверки являются возможными ключами для хэш-таблицы

D. Последовательность зондов для ключа не может измениться

Я верю, что A, B и D верны, поэтому я думаю, что C - правильный ответ.

---

Наихудший случай двойного хэширования:

а. Все сохраненные ключи имеют одинаковый h1.

B. Все сохраненные ключи имеют одинаковый h2.

C. Все сохраненные ключи имеют одинаковые h1 и h2.

D. Для вставки каждой клавиши требуется прорезать слоты для всех ранее вставленных клавиш

Я полагаю, что этот ответ будет C. Я не совсем уверен в этом, поэтому объяснение было бы неплохо.

Answer 1

1. Вы говорите «А, В и D истинны» и думаете, что С ложно. В то время как C неясно заявлен, это кажется верным, потому что последовательность тестов состоит из попытки серии ключей. Посмотрите на B более внимательно и подумайте, что произойдет, если h2 (v) является делителем m, размера таблицы.
2. C и D очень похожи, так как C вызовет D. Однако могут быть и другие случаи, вызывающие D, поэтому, вероятно, это и есть ответ.