一个适用于特定键的好的哈希函数，使用两个整数。

Question

我正在尝试确定map<double, double>类型的键。但问题是，我想要的键将由2个数字对生成。是否有任何好的函数可以为像(0, 1)、(2, 3)、(4, 2)、(0, 2)等这样的数对生成这样的键。

- Chen Li

---

请参考这个类似的问题：https://dev59.com/iXE85IYBdhLWcg3wvGKm - pilotcam

为什么不直接使用 std::pair<int, int> 作为你的键类型呢？ - tenfour

是的，std::map<std::pair<int, int>, int> 是有效的选择。 - andre

Answer 1

采用N进制数字系统，其中N是一对数字中可能的最大值。

例如：

hash(a, b) = a + b * N

那么

a = hash(a, b) % N
b = hash(a, b) / N

这将确保每对(a, b)都有自己独特的哈希值(a, b)。在十进制中同样也是如此：想象一下从0（我们将它们写为00、01、02等）到99（包括）的所有数字都是你的配对ab。然后，哈希(a，b)=a* 10 + b，反过来用除以10取整数部分得到第一个数字，用取余数得到第二个数字。

为什么我们不能选择任何N，甚至小于a/b的最大值？答案是：为了避免冲突。
如果你选择任意一个数字，它恰好比你的最大数字要小，那么不同数字对应的哈希函数很可能会相同。例如，如果你选取N=10,对于配对(10，10)和(0，11)，它们的哈希值都将等于110，在这种情况下对你来说并不好。

- dreamzor

---

类似这样的东西：pair (1, 3) = hash(1, 3) = 1 + (3*181.312) - Chen Li

如果 181.312 == 181312 == 181 千加 312，那么这就是你的 N，是正确的。 :) - dreamzor

为什么我需要跟踪N，不能使用任意数字？但是，我将用相同的数字乘以每个条目。 - Chen Li

Answer 2

理想情况下，你的键应该是一个 KeyValuePair<int, int>。我认为写更多的代码并没有什么帮助。如果由于某种原因你不能这样做，那么将这对数哈希成单个键取决于你想要实现什么目标。如果哈希用于像 Dictionary 这样的哈希结构，则必须平衡碰撞率和哈希速度。要完全避免碰撞的完美哈希将需要更多时间。同样，最快的哈希算法相对而言会有更多的碰撞。在这里找到完美的平衡是关键。此外，你还应该考虑你的有效哈希可以有多大，以及哈希输出是否应该可逆以便让你恢复原始输入。通常应优先考虑加快配对/哈希/映射的速度，而不是最小化碰撞概率（良好的哈希算法将具有较少的碰撞机会）。要获得完美的哈希，你可以参考 this thread 中的众多选项。

- nawfal