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

58

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

H=kmod 11

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,221,12,23

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

H=kmod 12

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,241,13,25

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.

CodyBugstein
la source
Question pertinente, pourquoi nous utilisons xor dans stackoverflow.com/questions/5889238/ ...
shuva

Réponses:

63

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 3K={0,1,...,100}m=1231233

  • Les clés seront hachées dans le compartiment .0{0,12,24,36,...}0
  • Les clés seront hachées au compartiment .3{3,15,27,39,...}3
  • Les clés seront hachées au compartiment .6{6,18,30,42,...}6
  • Les clés seront hachées dans le compartiment .9{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 3KKmK33

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 / 44m43m/4m/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.mKm

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 mmKm

Mario Cervera
la source
Je viens de voir que ma requête correspond à votre réponse. Pensez-vous que la fonction de hachage dans ma requête est valable?
Surexchange
@overexchange: j'ai répondu à votre question. Cette réponse pourrait également vous intéresser.
Mario Cervera
pourquoi est-ce que le choix de m n’a d’importance que si K est biaisé? N'est-il pas vrai que nous aurons de moins bonnes performances avec m mal même si K est uniformément distribué?
vorou
Cela dépend de ce que vous entendez par "mauvais ". Si vous voulez dire "petit comparé au nombre d'éléments dans la table de hachage" (c.-à-d . Facteur de charge élevé ), les performances seront médiocres. Cependant, si vous voulez dire "non primordial", alors ce fait n'est pas très important si toutes les clés ont la même probabilité, car elles seront distribuées également dans la table de hachage. La question elle-même fournit un exemple. m
Mario Cervera
16

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+kbH(n)=nmodmbnb

1112112312

frafl
la source
1
a+k×bm
1
mm
12>11
3
bm
8

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:

aa+i2i=1,2,

pp3

ppi2=c2

Raphaël
la source
2

h(k)=a×kmodmma1mm=1009Pr{h(x)=h(y),xy}=0.00099108027

Ce schéma s'appelle: Universal Hashing.

Saadtaame
la source