hash - 唯一的 int 到 int 哈希

Question

我很好奇是否存在一些具有以下属性的简单和/或众所周知的哈希方法:

1. 它将一个 32 位 int 转换为另一个 32 位 int
2. 没有两个不相等的输入会产生相同的输出
3. 通过查看输出，不应立即明显看出两个输入相似(在差异和位掩码方面)，这意味着 hash(a) 和 hash(a+1) 应该具有截然不同的输出，正如哈希(a)和哈希(a＆0x100000)。 (这排除了与随机值进行简单异或的情况。)

虽然这样的系统在理论上肯定存在，但在实践中存在吗？

Answer 1

实践中有很多!

一个简单的解决方案是将输入乘以任意奇数，并取结果的底部 32 位。即:

y = (x * YOUR_ODD_NUMBER) & 0xffffffff;

不过，这确实有一些弱点。它总是将零映射到零，如果您选择像 3 这样的小数字，那么映射将相当明显(类似地，如果您选择像 0xffffffff 这样的大数字，您将得到另一个明显的映射)，并且最低有效位不会改变。一般低位可以影响高位，高位不能影响低位。

另一种方法是对具有自身移位版本的数字进行多次异或:

x ^= x >> YOUR_FIRST_SHIFT;
x ^= x << YOUR_SECOND_SHIFT;
y = x ^ (x >> YOUR_THIRD_SHIFT);

您可以根据需要叠加任意数量的这些琐碎操作，以尝试隐藏各个阶段的弱点。即使某个操作本身不是很好，它也可以在更复杂的操作链中做出有用的贡献。例如，与某个常数的异或可以避免仅通过乘法将零映射到零的问题，并且移位和异或技术允许低位受到高位的影响。

如果你看PRNGs ，你会发现他们中的很多人的周期几乎与他们的状态相同。他们通过按照您指定的方式排列其状态来实现这一点 - 通过 1:1 映射，其中一个状态与下一个状态之间的关系不太明显 - 然后他们呈现该状态的一些(或全部)作为伪随机数。一些 PRNG 和哈希还会以回火阶段结束，在此阶段它们执行另一种映射以隐藏它们自己的一些弱点。

如果您在循环中运行哈希函数，在每次迭代时将 y 反馈到 x 中，那么您就拥有了一个 PRNG，并且您可以使用 dieharder 等工具来测试它的随机性。 .

并非所有 PRNG 都具有理想的长周期属性，并且该属性对于良好的哈希函数来说并不是必需的，但某些 PRNG 算法可以成为执行操作的有用想法来源，并且它们具有全面的分析。