Двойное хеширование с использованием составных чисел во второй хэш-функции

Question

Я понимаю, что лучшая практика - использовать наибольшее простое число (меньшее, чем размер массива) в функции мода второй хэш-функции. Это лучшая практика.

Но мой вопрос касаетсяиспользование чисел, которые не являются простыми числами.Меня не интересует псевдокод, просто идея концепции.

Допустим, у меня есть массив m = 20, и я должен выбрать между 6,9,12 и 15 в качестве значений, которыебудет введен во второй хэш-функции.Какой из них даст мне лучший «спред»?

Моя первая мысль - пойти на ту же идею, что и выбрать простое число, только слегка измененное, что означает использование наибольшего числа с минимальным количествомперестановки:

6 -> 2,3

9 -> 3,3 = 3

12 -> 2,3,4,6

15 -> 3,5

Справа от летучей мыши я могу исключить 6 (существует большее число с таким же количеством перестановок) и 12 (слишком много перестановок).

Теперь вопросвозникает, если я использую 9 - имеет наименьшее количество перестановок, или я должен выбрать 15 - хотя он имеет больше перестановок, он намного больше 9 и намного ближе к размеру массива (m = 20).

Правильно ли я использую этот подход?или есть лучший способ выбора номера, учитывая, что я могу выбрать только из чисел, указанных выше?

Answer 1

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

Если мы вынуждены выбрать номер, который не являетсяпростое число в качестве числа, которое будет использоваться во второй хеш-функции (в моде этой функции):

Правильный подход состоит в том, чтобы использовать функцию GCD (величайший общий знаменатель), чтобы найти числа, которые "премьер по отношению друг к другу ".Это означает, что мы ищем любое число, которое его gcd с 20 приведет к 1.

В этом случае:

gcd(20,6)= 2
gcd(20,9)= 1
gcd(20,12)= 3
gcd(20,15)= 5

Как мы видим, gcd между 20 и 91, что означает, что у них нет общих факторов, кроме 1. Следовательно, 9 является правильным ответом.