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.