math - 这个加法总是会产生一个唯一的数字吗？

Question

我不知道如何详尽地测试以下内容，而不是强制它，所以我只想问这个概念是否合理。

我有两个 64 位 unsigned int 变量，它们都用作位字段。这两个变量最多可以设置 60 位，从 1 到 60。可以设置任意数量的 60 位，并且可以按任意顺序设置它们。位 61、62 和 63 不会在任一变量中设置。此外，只有一个变量总是设置第 64 位。

鉴于上述描述，我认为哈希对于 field1 和 field2 的所有可能组合都是唯一的是否正确？

uint64_t field1 = ...;
uint64_t field2 = ...;
uint64_t hash   = field1 + field2;

标签： math

Answer 1

没有。简单的例子：

0b0011 + 0b0100 = 0b0111
0b0010 + 0b0101 = 0b0111

不可能为所有长度为 n 的值对提供长度为 n 的唯一散列。请注意，有一些2^60 * 2^60 = 2^120组合，因此2^60哈希不能适合所有组合。