c++ - 重复播种随机数生成器是合理的哈希函数吗？

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_hash 是二元组 (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 的实现是什么。随机数生成器被设计为在几个生成的 mnumbers 的周期内提供近似均匀分布的数字。它们并非旨在为一组(32 位)种子提供均匀分布的数字。在您假设的 mersenne_twister 情况下，随机数生成器的状态比您提供给 srand 的整数大得多(具体来说，624*sizeof(int)). RNG 确保其输出是随机和统一的大部分能力都来自那个额外的状态，而你把它拿走了。 (种子只能是2^32种状态之一)
2. 如果你升级了你的编译器或库或类似的东西，你可能已经序列化到磁盘的任何东西都将变得不可读。 (如果 rand 是一个黑盒子，没有人会说明天的实现与今天的相匹配)。
3. 对于 srand 的相同输入，您的哈希函数的输出返回相同的结果。因此，您已经有了一个散列——srand 的输入。 RNG 为 srand 的给定输入生成相同的输出。因此，您可能获得的哈希数不大于仅返回您已经计算出的哈希数。如果您对 srand 的初始哈希对于哈希表的分布不佳，请适当缩放哈希，使其在您的表中表现良好。

4. 对于 rand 的一些实现，这表现得非常差。考虑一个 linear congruential生成器(这在 C 库中更常见，因为它具有 sizeof(int) 的状态——例如 the BSD generator )。 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;
   }
   

   请注意，这种(常见)类型的生成器生成的哈希值很容易与您的输入值相关联。