c++ - 如何使用现有的哈希整数来索引哈希表？

Question

我目前正在使用 Boost for C++，并尝试使用 CRC32 实现无序映射(又名哈希表)。据我所知，它将一个字符串作为初始键，对其进行哈希处理，然后应用另一个操作，使其适合桶的数量。

虽然在我的情况下，我想预先散列字符串键(在 Boost 中使用单独的 CRC 函数)，然后使用该 ID 为表编制索引。我需要帮助的问题是 CRC32 散列有 2^32 个潜在值，我怀疑我是否需要一个包含 2^32 个元素的表。遇到这种情况怎么办？

在此感谢您的帮助!

Answer 1

在基于 C 的语言中使用取模运算符 -- %:

int hashtableIndex = hashValue % hashtableSize;

但请注意，在 C++ 中，结果的符号是“实现定义的”，如果 hashValue 为负，则结果的符号可以为负。因此，在执行 % 操作之前，可能需要关闭 hashValue 中的符号位。

另请注意，如果已知 hashtableSize 是 2 的幂，则可以简单地屏蔽 hashValue 以获取索引:

int hashtableIndex = hashValue & (hashtableSize - 1);