Заполнение всей харш-таблицы с открытым адресом функцией двойного хеширования

Question

Может ли двойное хеширование заполнить все записи в хеш-таблице в открытом хешировании адресов, основанном на простом числе?

Answer 1

Тривиально, да. Если хеш-таблица имеет n ведра, просто вставьте n элементы.

Последовательность зонда с двойным хешированием должна быть спроектирована таким образом, чтобы он попадал в каждое ведро (если это не так, это будет недостатком схемы). В частности, это означает, что вторая хеш-функция никогда не должна иметь значение 0 mod n, что может быть гарантировано путем принудительной установки ее в 1, если в противном случае она будет равна 0.