Hashtables: двойное хеширование, когда вторая хеш-функция возвращает кратное размеру таблицы

Question

Я реализую HashTable в C ++, используя открытую адресацию через двойное хеширование.

Я понимаю, что основной принцип двойного хеширования заключается в следующем:

indexInProbingSequence = (originalIndex + i * hashFunction2(key)) % tableSize

Я думаю, что реализовалэта часть правильно.Это для домашнего задания, и в соответствии с политикой класса я не могу просить совета по какому-либо конкретному коду, поэтому вам придется доверять мне в этой части.

Что, кажется, вызывает у меня проблемы, так это то, что иногда некоторые ключи при воздействии второй хэш-функции возвращают значение, кратное (простому) размеру таблицы.В этих случаях все индексы в последовательности зондирования одинаковы.Например, когда:

originalIndex = 32
hashFunction2(key) = 3035446
tableSize = 211

Последовательность проверки:

(32 + 1 * 3035446) % 211 == 32
(32 + 2 * 3035446) % 211 == 32

и т. Д.

Чего мне не хватает?

Answer 1

Я не думаю, что вы что-то пропустили, и, в частности, проблема возникает независимо от размера таблицы, когда hashFunction2(key) == 0.

Используйте (hashFunction2(key) % (tableSize - 1) + 1) вместо hashFunction2(key). Желательно, чтобы шаг был генератором кольца по модулю размера таблицы (что является шикарным способом сказать, что ваш зонд в конечном итоге покрывает всю таблицу), или, если он по крайней мере имеет большой период. Поскольку ваш размер таблицы прост, это означает, что вы должны избегать 0.