Как использовать существующее хешированное целое число для индексации хеш-таблицы?

Question

В настоящее время я использую Boost для C ++ и пытаюсь реализовать неупорядоченную карту (хэш-таблицу) с использованием CRC32.Насколько мне известно, он будет принимать строку в качестве исходного ключа, хэшировать ее и применять другую операцию, чтобы она вписывалась в число сегментов.

Хотя в моей ситуации я хотел бы заранее хешировать строковый ключ (используя отдельную функцию CRC в Boost), а затем использовать этот идентификатор для индексации таблицы.Проблема, с которой мне нужна помощь, состоит в том, что хеш CRC32 имеет 2 ^ 32 потенциальных значения, и я сомневаюсь, что мне когда-нибудь понадобится таблица с 2 ^ 32 элементами.Что мне делать в этой ситуации?

Спасибо за любую помощь здесь!

Answer 1

Используйте оператор модуля - % на языках C:

int hashtableIndex = hashValue % hashtableSize;

Но обратите внимание, что знак результата в C ++ является "определенным реализацией" и может быть отрицательным, если hashValue отрицательный. Поэтому перед операцией % может потребоваться отключить знаковый бит в hashValue.

Также обратите внимание, что если известно, что hashtableSize является степенью двойки, можно просто замаскировать hashValue, чтобы получить индекс:

int hashtableIndex = hashValue & (hashtableSize - 1);