Какова цель этой строки в HashHelpers.GetPrime?

Я искал в .NET реализацию словарей и нашел одну функцию, которая мне интересна: HashHelpers.GetPrime.

Большая часть того, что он делает, довольно проста, он ищет простое число выше некоторого минимума, которое передается ему как параметр, по-видимому, с конкретной целью использования в качестве количества ведер в хэш-табличной структуре. Но есть одна загадочная часть:

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

Какова цель проверки (j - 1) % 101 != 0? Т.е. почему мы, по-видимому, хотим избежать наличия нескольких ковшей, которая на 1 больше, чем кратное 101?

Ответы

Ответ 1

Комментарии объясняют это довольно хорошо:

'InitHash - это в основном реализация классического DoubleHashing (см. http://en.wikipedia.org/wiki/Double_hashing)

1) Единственное требование "правильности" состоит в том, что "приращение, используемое для зонд a. Будьте ненулевыми b. Быть относительно простым размером стола" HashSize. (Это необходимо для обеспечения того, чтобы вы исследовали все записи в таблицу перед тем, как вы завернете и заходите в уже проверенные записи)

2) Потому что мы выбираем размеры таблиц как простые, мы просто должны гарантировать, что приращение равно 0 < incr < hashSize

Таким образом, эта функция будет работать: Incr = 1 + (seed% (hashSize-1))

Хотя это хорошо работает для "равномерно распределенных ключей", на практике, неравномерность распространена. В частности, на практике мы можем видеть "В основном последовательный, где вы получаете длинные кластеры ключей, которые" упаковываются ". Чтобы избежать плохого поведения, вы хотите, чтобы это было так, что приращение" Большие даже для "малых значений (поскольку небольшие значения, как правило, происходят больше на практике). Таким образом, мы умножаем" семя на число, которое будет эти небольшие значения больше (и не повреждают большие значения). Мы выбрали HashPrime (101), потому что он был простым, и если hashSize-1 не является кратное HashPrime (принудительное в GetPrime), тогда incr имеет потенциал каждого значения от 1 до hashSize-1. Выбор был в значительной степени произвольный.