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

Question

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

Answer 1

选择 N'ary 数值系统，其中 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，在这种情况下这对您不利。

Answer 2

You should ideally have a KeyValuePair<int, int> as your key. I don't think writing more code than that can be helpful. If you cant have that for some reason, then hashing the pair to give a single key depends on what you're trying to achieve. If hashes are meant for hash structures like Dictionary, then you have to balance collision rate and speed of hashing. To have a perfect hash without collision at all it will be more time consuming. Similarly the fastest hashing algorithm will have more collisions relatively. Finding the perfect balance is the key here. Also you should take into consideration how large your effective hash can be and if hashed output should be reversible to give you back the original inputs. Typically priority should be given to speed up pairing/hashing/mapping than minimizing collision probability (a good hash algorithm will have less collision chances). To have perfect hashes you can see this thread for a plethora of options..