c++ - 寻找哈希函数/Ordered Int/to/Shuffled Int/

Question

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

Generating shuffled range using a PRNG rather than shuffling answer经过 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 与乘法混合使映射非线性。