c++ - 哈希函数到无序容器的桶大小？

Question

要将元素放入无序集合中，我们计算其哈希值并将其放入相应的桶中。然而，我们的桶通常比散列函数的值范围少得多。 buckets和hash值的对应关系是怎么计算出来的？似乎使用了一些函数来反射(reflect) (0 ... size_t) -> (0 ... size_of_buckets - 1)。但是即使是好的散列函数，使用这样的函数也可能导致大量冲突。

Answer 1

我不确定标准中是否定义了 std::unordered_map 确切的行为。然而，基本原则是这样的:始终保持桶数大于容器大小乘以一个小数(这个小数是 1.0/load_factor)。这样，碰撞应该很少见。

对于哈希表，通常有两种计算bucket_index的方法:

1. 桶的数量选择为 2 的幂:计算哈希值，然后通过位操作提取它的一些低位/高位位。这个方法需要一个“好的”散列函数，其中每一位都是随机的
2. 桶的数量选择一个质数:计算散列，然后通过模运算，计算 bucket_index。这种方法不需要“太好”的哈希函数

对于方法 1.，如果哈希函数质量不好，您可能会遇到很多冲突。对于方法 2.，即使使用质量不太好的哈希函数，通常也很少发生冲突。但是，方法 1. 通常更快，因为位操作比 mod 快得多(但有技术可以做到 faster )，而且质量足够好的哈希函数通常很便宜。