HashHelpers.GetPrime中这一行的目的是什么？

Question

我在.NET的Dictionaries实现中挖掘,发现了一个我很好奇的函数:HashHelpers.GetPrime.

它所做的大部分工作都非常简单,它会查找超过某个最小值的素数,并将其作为参数传递给它,显然是出于在哈希表结构中用作多个桶的特定目的.但有一个神秘的部分:

if (HashHelpers.IsPrime(j) && (j - 1) % 101 != 0)
{
    return j;
}

(j - 1) % 101 != 0检查的目的是什么？也就是说,为什么我们显然想要避免使用多于101的倍数的多个桶？

Answer 1

该意见解释相当不错:

'InitHash'基本上是经典DoubleHashing的实现(参见http://en.wikipedia.org/wiki/Double_hashing)

1)唯一的"正确性"要求是用于探测a的"增量".不为零b.相对于表大小'hashSize'是主要的.(这是为了确保您在"包装"之前探测表中的所有条目并访问已探测的条目)

2)因为我们选择表大小为素数,我们只需要确保增量为0 <incr <hashSize

因此这个函数可以工作:Incr = 1 +(种子%(hashSize-1))

虽然这适用于"均匀分布"的键,但在实践中,非均匀性很常见.特别是在实践中,我们可以看到"大多数顺序",在这里您可以获得"打包"的长串密钥.为避免不良行为,您希望情况是即使对于"小"值,增量也是"大"(因为在实践中小值往往会发生更多).因此,我们将"种子"乘以一个数字,使这些小值变大(并且不会损害大值).我们选择了HashPrime(101)因为它是素数,如果'hashSize-1'不是HashPrime的倍数(在GetPrime中强制执行),那么incr有可能成为从1到hashSize-1的每个值.选择主要是武断的.