寻找哈希函数/有序Int/to/Shuffled Int/

现在的问题是,你是需要一个真正的随机映射,还是仅仅需要一个“弱”置换。假设是后者,如果你在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,但对你来说更容易的事情就是运行一个循环并搜索它们(一旦离线)。

你可以试着建造一个合适的 Feistel network

假设你的目标是在整个范围内分散分组值,
似乎以某种预定义的顺序洗牌可能会奏效。
即,给定8位ABCDEFGH,将它们排列成EGDBHCFA或某种这样的模式。

代码将只是一个简单的掩码、移位和加法序列。

bool
nonsort(int i, int j)
{
    return  random() & 31 >16 ? true : false;
}

std::list<int> li;
// insert elements
li.sort(nonsort);

然后,您可以使用普通迭代器获取所有整数。记住用srand()和time或任何其他伪随机值初始化random。

对于这组约束,确实没有解决方案。尝试将32位无符号哈希转换为32位无签名哈希,会导致冲突,除非你做一些简单的事情,比如1到1的映射。每个数字都是自己的哈希值。