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

Question

我希望生成大量的随机数据,这些数据对于给定的数据是可重现的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_hash2元组是一个很好的哈希函数(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遵循表格xNext = 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;
   }
   

   请注意,此(常见)类型的生成器会生成易于与输入值相关的哈希值.