是否反复为随机数生成器播种合理的哈希函数？

我希望生成大量的随机数据，这些数据对于给定的key是可重现的，包括一个数字列表：

 [a, b, c, d, e, ...] 

以下是使RNG进入状态以生成随机数据的良好或明智的方式，对于每个n元组[a, b, c, ..., n] ，该数据与该数据不相关。输出“相邻”n元组[a+1, b, c, ..., n] ， [a, b+1, c, ..., n]等。

 srand(a); srand(rand() * b); srand(rand() * c); ... srand(rand() * n); # generate random data: for (int i=0; i < 100; +i) printf("%d", rand()); 

我认为这个问题归结为以下几点： rand_hash是2元组(a, b)的良好哈希函数吗？

 int rand_hash(int a, int b) { srand(a); srand(rand() * b); return rand(); } 

注意：我不希望暗示srand和rand是RNG的任何特定实现。 假设为了论证我们使用了一个好的Mersenne Twister代码。

编辑 ：如果不清楚，通过“合理的哈希函数”我的意思是以下。 在2元组[a, b]的受限情况下， rand_hash的输出应该在int的范围内是均匀的，并且（通常） a或b的变化幅度与之间不应该相关。返回值变化的幅度。

Answer 1

不，这不是一个合理的方法。

1. 你不知道rand的实现是什么。 随机数发生器被设计成在几个生成的数字的周期内提供近似均匀分布的数字。 它们的设计不是为了在（32位）种子集上提供均匀分布的数字。 在您假设的mersenne_twister情况下，随机数生成器的状态远大于您为srand提供的整数（特别是624*sizeof(int) ）。 RNG必须确保其输出随机且均匀的大部分功率来自该附加状态，并且您将其取消。 （种子只能是2 ^ 32个状态中的一个）
2. 如果您曾经升级过您的编译器或库或类似的东西，那么您可能序列化到磁盘的任何内容都将变得不可读。 （如果rand是一个黑盒子，没有人说明天的实施与今天相符）。
3. 您的散列函数的输出对于srand的相同输入返回相同的内容。 因此，您已经有一个哈希 – srand的输入。 RNG为给定的srand输入生成相同的输出。 因此，您可能获得的哈希数不会超过返回您已经计算过的哈希值。 如果您对srand的初始哈希值很难分配给哈希表，那么请适当地缩放哈希值，使其在表中表现良好。

4. 对于rand一些实现，这表现得非常糟糕。 考虑一个线性同余生成器（它更常见于C库，因为它具有sizeof(int) – 例如BSD生成器 ）。 LCG遵循formsxNext = a*xCurrent + b 。 考虑：

    static int seed = 0; void srand(int newSeed) { seed = newSeed; } int rand() { seed = (int) ((1103515245 * ((unsigned int)seed) + 12345) & 0x7fffffffUL); return seed; } 

   请注意，此（常见）类型的生成器会生成易于与输入值相关的哈希值。

Answer 2

使用boost::hash_combine http://www.boost.org/doc/libs/1_33_1/doc/html/hash_combine.html来创建初始种子怎么样？ 不止一次使用srand总会在我脑海中触发红旗。

Answer 3

潜在问题：

如果另一个线程在哈希函数中调用rand()怎么办？