c++ - 具有特殊键的 2 个整数的良好哈希函数

Question

我正在尝试确定 map<double, double> 的 key 类型。但问题是我要的key会由一对2的数字生成。有什么好的函数可以为 (0, 1), (2, 3), (4, 2) (0, 2) 等对生成这样的 key 吗？

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。然后，hash(a, b) = a * 10 + b，反之亦然，要获得第一个数字，您必须将数字除以 10，第二个数字 - 取模 10。

为什么我们不能选择任何 N，也许小于 a/b 的最大值？答案是:避免碰撞。
如果您选择任何数字并且它恰好小于您的最大数字，则很有可能不同的数字对会提供相同的哈希函数。例如，如果您为 (10, 10) 和 (0, 11) 对选择 N = 10，则它们的哈希值都将等于 110，这在这种情况下对您不利。