寻找哈希函数 /Ordered Int/ 到 /Shuffled Int/

我正在寻找可以将有序整数索引值更改为随机哈希索引的恒定时间算法。如果是可逆的就太好了。我需要每个索引的哈希键都是唯一的。我知道这可以通过在大文件中查找表来完成。 IE。创建所有整数的有序集合，然后随机打乱它们并以随机顺序写入文件。然后您可以在需要时读回它们。但这需要查找大文件。我想知道是否有一种简单的方法可以使用伪随机生成器来根据需要创建序列？

使用 PRNG 而不是打乱生成打乱范围 the answer by 埃里卡伦线性反馈移位寄存器看起来是正确的。我刚刚尝试过，但它会产生重复和空洞。

问候 大卫·艾伦·芬奇

现在的问题是您是否需要真正的随机映射，或者只是一个“弱”排列。假设后者，如果您使用无符号 32 位整数（例如）进行 2 的补码算术运算，则乘以任何奇数都是双射且可逆的映射。当然，XOR 也是如此，因此您可能尝试使用的简单模式是例如

unsigned int hash(int x) {
   return (((x ^ 0xf7f7f7f7) * 0x8364abf7) ^ 0xf00bf00b) * 0xf81bc437;
}

数字并没有什么神奇之处。所以你可以改变它们，它们甚至可以是随机的。唯一的问题是被乘数必须是奇数。并且您必须使用回滚进行计算（忽略溢出）。这可以反过来。要进行求逆，您需要能够计算出正确的互补被乘数 A 和 B，然后求逆

unsigned int rhash(int h) {
    return (((x * B) ^ 0xf00bf00b) * A) ^ 0xf7f7f7f7;
}

您可以用数学方法计算 A 和 B，但对您来说更简单的事情就是运行一个循环并搜索它们（即离线后）。

该方程使用 XOR 与乘法混合来使映射非线性。