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

Question

我正在研究 .NET 的字典实现，发现了一个我很好奇的函数:HashHelpers.GetPrime。

它所做的大部分工作都非常简单，它会寻找一个大于某个最小值的质数，并将其作为参数传递给它，显然是为了在类似哈希表的结构中用作多个桶的特定目的。但有一个神秘的部分:

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

(j - 1) % 101 != 0 检查的目的是什么？即，为什么我们显然希望避免使用比 101 的倍数多 1 的桶？

Answer 1

comments解释得很好:

‘InitHash’ is basically an implementation of classic DoubleHashing (see http://en.wikipedia.org/wiki/Double_hashing)

1) The only ‘correctness’ requirement is that the ‘increment’ used to probe a. Be non-zero b. Be relatively prime to the table size ‘hashSize’. (This is needed to insure you probe all entries in the table before you ‘wrap’ and visit entries already probed)

2) Because we choose table sizes to be primes, we just need to insure that the increment is 0 < incr < hashSize

Thus this function would work: Incr = 1 + (seed % (hashSize-1))

While this works well for ‘uniformly distributed’ keys, in practice, non-uniformity is common. In particular in practice we can see ‘mostly sequential’ where you get long clusters of keys that ‘pack’. To avoid bad behavior you want it to be the case that the increment is ‘large’ even for ‘small’ values (because small values tend to happen more in practice). Thus we multiply ‘seed’ by a number that will make these small values bigger (and not hurt large values). We picked HashPrime (101) because it was prime, and if ‘hashSize-1’ is not a multiple of HashPrime (enforced in GetPrime), then incr has the potential of being every value from 1 to hashSize-1. The choice was largely arbitrary.