Pourquoi est-il préférable d'utiliser un nombre premier comme mod dans une fonction de hachage?

Si j'ai une liste de valeurs de clé allant de 1 à 100 et que je souhaite les organiser dans un tableau de 11 compartiments, on m'a appris à former une fonction mod

Maintenant, toutes les valeurs seront placées les unes après les autres sur 9 lignes. Par exemple, dans le premier compartiment, il y aura . Dans le second cas, il y aura etc.1 , 12 , 23 $0, 11, 22 \dots$$1, 12, 23 \dots$

Disons que j'ai décidé d'être un mauvais garçon et d'utiliser une fonction non prime comme fonction de hachage - prenez 12. Utilisation de la fonction de hachage

aurait comme conséquence une table de hachage avec les valeurs dans le premier compartiment, etc. dans le second et ainsi de suite.1 , 13 , 25 $0, 12, 24 \dots$$1, 13, 25 \dots$

Ils sont essentiellement la même chose. Je n'ai pas réduit le nombre de collisions et je n'ai pas mieux réparti les choses en utilisant le code de hachage avec un nombre premier et je ne vois pas en quoi il serait bénéfique.

Considérons l'ensemble des clés et une table de hachage où le nombre de compartiments est . Puisque est un facteur de , les clés qui sont des multiples de seront hachées pour des compartiments qui sont des multiples de :m = 12 3 12 3 $K=\{0,1,...,100\}$$m=12$$3$$12$$3$$3$

• Les clés seront hachées dans le compartiment .$\{0,12,24,36,...\}$$0$
• Les clés seront hachées au compartiment .$\{3,15,27,39,...\}$$3$
• Les clés seront hachées au compartiment .$\{6,18,30,42,...\}$$6$
• Les clés seront hachées dans le compartiment .$\{9,21,33,45,...\}$$9$

Si est uniformément distribué (c’est-à-dire que chaque clé de même probabilité de se produire), alors le choix de n’est pas si critique. Mais que se passe-t-il si n'est pas uniformément distribué? Imaginez que les clés les plus susceptibles de se produire soient les multiples de . Dans ce cas, tous les compartiments qui ne sont pas des multiples de seront vides avec une probabilité élevée (ce qui est vraiment mauvais en termes de performances de table de hachage).K m K 3 $K$$K$$m$$K$$3$$3$

Cette situation est plus commune que cela puisse paraître. Imaginez, par exemple, que vous gardiez une trace d'objets en fonction de leur emplacement dans la mémoire. Si la taille des mots de votre ordinateur est de quatre octets, vous utiliserez des clés de hachage multiples de . Inutile de dire que choisir comme un multiple de serait un choix terrible: vous auriez des seaux de complètement vides et toutes vos clés entreraient en collision dans les seaux restants .m 4 3 m / 4 m /$4$$m$$4$$3m/4$$m/4$

En général:

Chaque clé de qui partage un facteur commun avec le nombre de compartiments sera hachée en un compartiment qui est un multiple de ce facteur.$K$$m$

Par conséquent, pour réduire au minimum les collisions, il est important de réduire le nombre de facteurs communs entre et les éléments de . Comment cela peut il etre accompli? En choisissant un nombre qui a très peu de facteurs: un nombre premier .K $m$$K$$m$

Si une collision est moins probable en utilisant des nombres premiers dépend de la distribution de vos clés.

Si beaucoup de vos clés ont la forme et que votre fonction de hachage est H ( n ) = n mod m , ces clés vont dans un petit sous-ensemble des compartiments si et seulement si b divise n . Donc, vous devriez minimiser le nombre de tels b , ce qui peut être réalisé en choisissant un nombre premier.$a+k\cdot b$$H(n)=n \bmod m$$b$$n$$b$

$11$$12$$11$$2$$3$$12$

Que cela ait un impact (aussi) ou non dépend de la manière dont vous traitez les collisions. Lors de l’utilisation de certaines variantes de hachage à ciel ouvert , l’utilisation des nombres premiers garantit la présence d’emplacements vides tant que la table est suffisamment vide.

Essayez de montrer ce qui suit, par exemple:

$a$$a + i^2$$i=1,2,\dots$

$p$$p$$3$

$p$$p$$i^2=c$$2$

$h(k)=a\times k \mod m$$m$$a$$1\over m$$m=1009$$Pr\{h(x)=h(y), x\neq y\}=0.00099108027$

Ce schéma s'appelle: Universal Hashing.