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

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

Что из следующего не верно в отношении последовательностей зондов для реализации двойного хеширования?

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

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

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

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

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

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

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

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

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

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

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

Источник

1 ответ

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