Double hachage en utilisant des nombres premiers dans la deuxième fonction de hachage

Question

Je réalise que la meilleure pratique est d'utiliser le plus grand nombre premier (plus petit que la taille du tableau) dans la fonction modulo de la deuxième fonction de hachage est la meilleure pratique.

Mais ma question concerne l'utilisation de nombres qui ne sont pas des nombres premiers. Je ne suis pas intéressé par un pseudo-code, juste l'idée derrière le concept.

Disons que j'ai un tableau m=20, et que je dois choisir entre 6,9,12 et 15 comme les valeurs qui seront entrées dans la deuxième fonction de hachage. Lequel d'entre eux me donnera la meilleure 'répartition' ?

Ma première idée est d'aller dans la même direction que le choix d'un nombre premier, légèrement modifié, ce qui signifie l'utilisation du plus grand nombre ayant le minimum de permutations :

6 -> 2,3

9 -> 3,3 = 3

12 -> 2,3,4,6

15 -> 3,5

Je peux d'emblée éliminer 6 (un nombre plus grand avec le même nombre de permutations existe) et 12 (trop de permutations).

Maintenant la question se pose, devrais-je utiliser 9 - a le moins de permutations, ou devrais-je choisir 15 - bien qu'il ait plus de permutations, il est beaucoup plus grand que 9 et beaucoup plus proche de la taille du tableau (m=20).

Suis-je correct en utilisant cette approche ? ou existe-t-il une meilleure façon de choisir un nombre, étant donné que je ne peux choisir que parmi les nombres indiqués ci-dessus ?

Answer 1

J'ai trouvé la réponse que je cherchais, donc je laisse la question ici avec la réponse correcte au cas où quelqu'un d'autre en aurait besoin.

Si nous sommes obligés de choisir un nombre qui n'est pas un nombre premier comme le nombre à utiliser dans la deuxième fonction de hachage (dans le modulo de cette fonction) :

L'approche correcte est d'utiliser la fonction PGCD (Plus Grand Commun Diviseur), pour trouver des nombres qui sont "premiers entre eux". Cela signifie que nous cherchons n'importe quel nombre tel que son pgcd avec 20 sera égal à 1.

Dans ce cas :

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

Comme on peut le voir, le pgcd entre 20 et 9 est 1, ce qui signifie qu'ils n'ont aucun facteur commun autre que 1. Par conséquent, 9 est la réponse correcte.