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);