寻找散列函数/有序内部/到/混洗智力/ [英] Looking for a Hash Function /Ordered Int/ to /Shuffled Int/

问题描述

我找了一定时间的算法能够有序整数索引值更改为随机哈希索引。它会很好，如果是可逆的。我需要一个散列关键字是唯一的每个索引。我知道，这可能是一个表进行查找在一个大文件。 I.E.创建所有整数的有序集合，然后洗牌他们随机写入随机序列的文件。然后，您可以阅读他们回来，你需要他们。但是这将需要寻求成一个大的文件。我不知道是否有使用说需要一个伪随机生成器来创建序列一个简单的方法？

I am looking for constant time algorithm can change an ordered integer index value into a random hash index. It would nice if it is reversible. I need that hash key is unique for each index. I know that this could be done with a table look up in a large file. I.E. create an ordered set of all ints and then shuffle them randomly and write to a file in random sequence. You could then read them back as you need them. But this would require a seek into a large file. I wonder if there is a simple way to use say a pseudo random generator to create the sequence as needed?

<一个href="http://stackoverflow.com/questions/464476/generating-shuffled-range-using-a-prng-rather-than-shuffling">Generating利用PRNG，而不是洗牌中的<一个洗牌的范围href="http://stackoverflow.com/questions/464476/generating-shuffled-range-using-a-prng-rather-than-shuffling/515755#515755">answer通过 erikkallen的线性反馈移位寄存器看起来正确的事情。我只是想它，但它产生的重复和漏洞。

Generating shuffled range using a PRNG rather than shuffling the answer by erikkallen of Linear Feedback Shift Registers looks like the right sort of thing. I just tried it but it produces repeats and holes.

问候 大卫·艾伦·芬奇

Regards David Allan Finch

推荐答案

现在的问题是，如果你需要一个真正的随机映射，或只是一个弱的置换。假设后者，如果操作与2的补码运算的无符号32位整数（比如说），乘以任意奇数是一个双射和可逆的映射。当然，同样适用于异，所以你可能会尝试使用一个简单的模式就是如

The question is now if you need a really random mapping, or just a "weak" permutation. Assuming the latter, if you operate with unsigned 32-bit integers (say) on 2's complement arithmetics, multiplication by any odd number is a bijective and reversible mapping. Of course the same goes for XOR, so a simple pattern which you might try to use is e.g.

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

没有什么神奇的数字。所以，你可以改变他们，他们甚至可以随机。唯一的一点是，被乘数必须是奇数。而你必须用rollaround（忽略溢出）计算。这可以被反转。要实现反转，则需要能够计算出正确的互补被乘数A和B，之后反转为

There is nothing magical in the numbers. So you can change them, and they can be even randomized. The only thing is that the multiplicands must be odd. And you must be calculating with rollaround (ignoring overflows). This can be inverted. To do the inversion, you need to be able to calculate the correct complementary multiplicands A and B, after which the inversion is

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

您可以计算出A和B数学，但对你就越容易的事情就是运行一个循环，并寻找他们（一次下线，这是）。

You can calculate A and B mathematically, but the easier thing for you is just to run a loop and search for them (once offline, that is).

的等式使用异或与乘法混合以使映射非线性

The equation uses XORs mixed with multiplications to make the mapping nonlinear.

这篇关于寻找散列函数/有序内部/到/混洗智力/的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！