c++ - 使用 std::unordered_map 的散列函数有什么限制

Question

我正在使用 std::unordered_map 来表示 3 维空间排列中的数据。我的哈希函数是:

unsigned int x,y,z;
unsigned int a =1000;
unsigned int b = 1000*a;
unsigned int Hash = x + a*y + b*z;

在发生任何碰撞之前，应该允许最多 1000 个单位的 x，1000 个单位的 y。 我的问题是，我的哈希函数的无碰撞空间是否有任何限制？或者我可以将 a 和 b 设置为较大的数字，注意如果全部分配，这很容易超过我的系统内存？

干杯

Answer 1

首先，哈希表操作的一些背景:

哈希表没有分配足够的桶来容纳哈希函数的整个空间。那确实是浪费(而且可能也是不可能的)。他们分配一定数量的桶(比如 16 个)，然后将每一对存储在桶中， key 散列为模桶的数量。

本地图达到一定阈值(通常为 75-85%)占用的桶时，桶的数量会增加。这会强制重新散列所有 key ，以便将它们应用于新的模数。

因此，如果您的哈希函数针对特定键返回 50，并且哈希表有 16 个桶，则该键的对存储在桶 (50 mod 16) = 2 中。

如果桶的数量后来增加到 32，则该对将移动到桶 (50 mod 32) = 18。

can I set a and b to be large numbers

当然可以，因为哈希对分配的桶数取模用于查找特定键的桶。