std::unordered_map 的散列函数有什么限制
What are the limitations for hash functions with std::unordered_map
我正在使用 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。
我的问题是，我的散列函数的无碰撞 space 是否有任何限制？或者我可以将 a 和 b 设置为大数，注意如果全部分配，这很容易超过我的系统内存？
干杯
首先，哈希表操作的一些背景知识：
哈希表没有分配足够的桶来容纳哈希函数的 整个 space。那确实是浪费（而且可能也是不可能的）。他们分配一定数量的桶（比如 16 个），然后将每一对存储在桶中，密钥散列到 modulo 桶的数量。
当地图达到一定的阈值（通常是75-85%）占用的桶时，桶的数量会增加。这会强制重新散列所有密钥，以便将它们应用于新的 modulo。
因此，如果特定键的哈希函数 returns 50，并且哈希表有 16 个桶，则该键的对存储在桶 (50 mod 16) = 2 中。
如果桶的数量后来增加到 32，则该对将移动到桶 (50 mod 32) = 18。
can I set a and b to be large numbers
当然，因为散列 modulo 分配的桶数用于查找特定键的桶。
我正在使用 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。 我的问题是，我的散列函数的无碰撞 space 是否有任何限制？或者我可以将 a 和 b 设置为大数，注意如果全部分配，这很容易超过我的系统内存？
干杯
首先，哈希表操作的一些背景知识：
哈希表没有分配足够的桶来容纳哈希函数的 整个 space。那确实是浪费（而且可能也是不可能的）。他们分配一定数量的桶（比如 16 个），然后将每一对存储在桶中，密钥散列到 modulo 桶的数量。
当地图达到一定的阈值（通常是75-85%）占用的桶时，桶的数量会增加。这会强制重新散列所有密钥，以便将它们应用于新的 modulo。
因此，如果特定键的哈希函数 returns 50，并且哈希表有 16 个桶，则该键的对存储在桶 (50 mod 16) = 2 中。
如果桶的数量后来增加到 32，则该对将移动到桶 (50 mod 32) = 18。
can I set a and b to be large numbers
当然，因为散列 modulo 分配的桶数用于查找特定键的桶。