algorithm - 31位双射(完美)哈希算法

我需要的
我需要一个产生双射输出的算法我有一个31位输入，需要一个伪随机的31位输出。
我所考虑的
crc在其位宽度内是双射的。
我在Google上找到了多项式，但找不到表或算法。
有人能给我指个正确的方向吗？
我需要一个crc-31算法，使用多项式，比如0x737e312b，或者任何双射函数来做我需要的事情。
注意
我找到了下面的代码，但不幸的是我没有工具来编译和运行它。

最佳答案

对于任何哈希函数hash，您可以执行以下操作：

function bijectiveHash31(int val) {
    val &= 0x7FFFFFFF; //make sure it's 31 bits
    for (int i=0; i<5; ++i) {
        // the high bits affect the low bits
        val ^= hash(val>>15) & 32767;
        // rotate bits
        val = ((val&32767)<<16) | ((val>>15)&65535);
    }
    return val;
}

这是一个Feistel结构，它构成了许多密码的基础：https://en.wikipedia.org/wiki/Feistel_cipher
如果你需要它的速度，你不需要它是超级好，那么这个工作很好：

function bijectiveHash31(int val) {
    val = ((val*RANDOM_ODD_NUMBER) + RANDOM_NUMBER) & 0x7FFFFFFF;
    val ^= (val>>15);
    val ^= (val>>8);
    return val;
}

在这两种情况下，找出如何撤消每个基本操作并不太困难，这表明整个散列是双射的。如果您需要帮助建立乘法，请参见https://en.wikipedia.org/wiki/Modular_multiplicative_inverse

关于algorithm - 31位双射(完美)哈希算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/55957869/