c++ - HASH 函数和实现多键哈希映射

Question

目标：创建一个带有 2 个整数键的哈希映射（使用无符号整数转换将指针转换为整数，是的，这是可行的）并将其映射到单个值。

尝试的解决方案：所以我已经有一个哈希映射，它采用单个键并将其成功映射到值。我现在将它扩展到使用“配对功能”来获取两个键。所以我拿了两个密钥，使用 Cantor 配对函数将它们配对，然后对这个组合密钥进行哈希处理。

瓶颈：所以两个键的问题是康托尔配对函数进行乘法运算，导致整数溢出，因此“不”给我唯一的输出，因为它应该在数学上做。

问题：

1. 我看到很多散列函数做乘法。整数溢出是散列中的正常现象还是很糟糕？
2. 我还考虑将另一个键附加到一个新的 64 位整数中。就像 aaaaaaaabbbbbbbb 一样，然后将其传递给哈希映射。但是我担心这可能会由于浮点表示而导致出现像 NaN 这样的异常数字，这可能很糟糕。
3. 欢迎任何更好的想法。

如果某些部分不清楚，请告诉我。

Answer 1

你可能想看看boost::hash_combine

Answer 2

1. 整数溢出并不是那么糟糕。确实，它可能会导致冲突，但是对于哈希映射的哈希来说，很少有冲突是可以的。

2. 也许是个坏主意。它可能会导致太多的冲突。

3. 如果您的输入是N位宽，那么您的输出必须至少是2N位宽。所以为了适应uint输入，你需要一个ulong大小的输出。如果输入高于该值，则会导致溢出。如果输出小于该值，则会出现冲突/重复。

但确实没有多少功能适合内部2N尺寸。你可以试试

a * uint.MaxValue + b

或者这个

a >= b ? a * a + a + b : a + b * b

这两个都是无符号长的。这两个是它可以获得的最节省空间的。

另请参阅以唯一且确定的方式将两个整数映射为一个。