寻找散列函数 /Ordered Int/ 到 /Shuffled Int/

Question

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

生成使用PRNG，而不是洗牌洗牌范围的答案被 erikkallen线性反馈移位寄存器貌似正确类的事情。我刚刚尝试过，但它会产生重复和漏洞。

问候大卫·艾伦·芬奇

Answer 1

现在的问题是你是否需要一个真正随机的映射，或者只是一个“弱”排列。假设是后者，如果您在 2 的补码算术上使用无符号 32 位整数（例如）进行运算，则乘以任何奇数是一个双射和可逆映射。当然，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 与乘法混合使映射成为非线性。