Warum ist es am besten, eine Primzahl als Mod in einer Hashing-Funktion zu verwenden?

57

Wenn ich eine Liste mit Schlüsselwerten von 1 bis 100 habe und diese in einem Array von 11 Buckets organisieren möchte, wurde mir das Bilden einer Mod-Funktion beigebracht

H=kmod 11

Jetzt werden alle Werte nacheinander in 9 Zeilen platziert. Zum Beispiel gibt es im ersten Bucket . In der Sekunde wird es usw. geben.0,11,221,12,23

Nehmen wir an, ich habe mich entschieden, ein böser Junge zu sein und eine Nicht-Primzahl als Hash-Funktion zu verwenden - nehmen wir 12. Die Hashing-Funktion verwenden

H=kmod 12

Dies würde zu einer Hash-Tabelle mit den Werten im ersten Bucket, usw. im zweiten Bucket usw. führen.0,12,241,13,25

Im Grunde sind sie dasselbe. Ich habe Kollisionen nicht reduziert und die Dinge nicht besser mit dem Hash-Code der Primzahl verteilt, und ich kann nicht erkennen, wie vorteilhaft es jemals ist.

CodyBugstein
quelle
Relevante Frage, warum wir xor in der Hash-Funktion stackoverflow.com/questions/5889238/…
shuva

Antworten:

62

Betrachten Sie die Menge der Schlüssel und eine Hash-Tabelle, in der die Anzahl der Eimer . Da ein Faktor von , werden die Schlüssel, die ein Vielfaches von sind, in Eimer gehasht, die ein Vielfaches von :K={0,1,...,100}m=1231233

  • Die Schlüssel werden in Bucket gehasht .{0,12,24,36,...}0
  • Die Schlüssel werden in Bucket gehasht .{3,15,27,39,...}3
  • Die Schlüssel werden in Bucket gehasht .{6,18,30,42,...}6
  • Die Schlüssel werden in Bucket gehasht .{9,21,33,45,...}9

Wenn gleichmäßig verteilt ist (dh jeder Schlüssel in ist gleich wahrscheinlich), ist die Wahl von nicht so kritisch. Aber was passiert, wenn nicht gleichmäßig verteilt ist? Stellen Sie sich vor, dass die wahrscheinlichsten Schlüssel ein Vielfaches von . In diesem Fall sind alle Buckets, bei denen es sich nicht um Vielfache von , mit hoher Wahrscheinlichkeit leer (was in Bezug auf die Leistung der Hash-Tabelle wirklich schlecht ist).KKmK33

Diese Situation ist häufiger, als es scheint. Stellen Sie sich zum Beispiel vor, Sie verfolgen Objekte anhand ihres Speicherorts. Wenn die Wortgröße Ihres Computers vier Bytes beträgt, werden Sie Hashing-Schlüssel haben, die ein Vielfaches von . Es erübrigt sich zu erwähnen, dass es eine schreckliche Wahl wäre , als Vielfaches von zu wählen : Sie hätten Eimer komplett leer und alle Ihre Schlüssel kollidieren in den verbleibenden Eimern.4m43m/4m/4

Im Allgemeinen:

Jeder Schlüssel in , der einen gemeinsamen Faktor mit der Anzahl der Buckets wird in einen Bucket gehasht, der ein Vielfaches dieses Faktors ist.Km

Um Kollisionen zu minimieren, ist es daher wichtig, die Anzahl gemeinsamer Faktoren zwischen und den Elementen von zu reduzieren . Wie kann das erreicht werden? Indem Sie als eine Zahl wählen , die nur wenige Faktoren hat: eine Primzahl .mKm

Mario Cervera
quelle
Ich habe gerade gesehen, dass meine Anfrage mit Ihrer Antwort übereinstimmt. Denken Sie, dass die Hash-Funktion in meiner Abfrage funktioniert?
Überaustausch
@overexchange: Ich habe auf Ihre Frage geantwortet . Diese Antwort könnte Sie auch interessieren.
Mario Cervera
warum ist es so, dass die Wahl von m nur wichtig ist, wenn K schief ist? Stimmt es nicht, dass wir mit schlechtem m eine schlechtere Leistung haben, selbst wenn K gleichmäßig verteilt ist?
Vorou
Es kommt darauf an, was du mit "schlechtes " meinst . Wenn Sie "klein im Vergleich zur Anzahl der Elemente in der Hash-Tabelle" (dh hoher Lastfaktor ) meinen , ist die Leistung schlecht. Wenn Sie jedoch "nicht prim" meinen, ist diese Tatsache nicht so wichtig, wenn alle Schlüssel gleich wahrscheinlich sind, da sie gleichmäßig in der Hash-Tabelle verteilt werden. Die Frage selbst liefert ein Beispiel. m
Mario Cervera
16

Ob eine Kollision mit Primzahlen weniger wahrscheinlich ist, hängt von der Verteilung Ihrer Schlüssel ab.

Wenn viele Ihrer Schlüssel die Form und Ihre Hash-Funktion , dann gehen diese Schlüssel zu einer kleinen Teilmenge der Buckets, wenn teilt . Sie sollten also die Anzahl solcher minimieren , die durch Auswahl einer Primzahl erreicht werden können.a+kbH(n)=nmodmbnb

Wenn Sie hingegen bis Eimer haben möchten und wissen, dass Unterschiede, bei denen es sich um Vielfache von handelt, wahrscheinlicher sind als Unterschiede, bei denen es sich um Vielfache von und , können Sie für Ihre ganz spezielle Anwendung auswählen .1112112312

frafl
quelle
1
Aber wenn meine Schlüssel nicht die Form dann keine Rolle? Ist das richtig? a+k×bm
CodyBugstein
1
@lmray, wenn deine Schlüssel gleichmäßig verteilt sind, ist egal. Wenn dies nicht der Fall ist, hängt es von der Präzisionsverteilung ab, ob eine Rolle spielt oder nicht. mm
AProgrammer
Gerade die letzte Bearbeitung zurückgesetzt, habe ich vergessen, dass . 12>11
Freitag,
3
Meinten Sie, dass "zu einer kleinen Teilmenge der Eimer gehen, wenn teilt "? bm
Mikhail Dubov
8

Ob dies (auch) Auswirkungen hat, hängt davon ab, wie Sie mit Kollisionen umgehen. Wenn Sie einige Varianten von Open Hashing verwenden , wird durch die Verwendung von Primzahlen sichergestellt, dass leere Slots gefunden werden, solange die Tabelle ausreichend leer ist.

Versuchen Sie beispielsweise Folgendes zu zeigen:

Angenommen, wir möchten ein Element einfügen, das Hashes enthält, um zu adressieren und Kollisionen aufzulösen, indem wir anschließend die Positionen für versuchen .aa+i2i=1,2,

Zeigen , dass dieses Verfahren immer eine leere Position ergibt sich, wenn der Hash - Tabelle der Größe ist , eine Primzahl größer als , und mindestens die Hälfte aller Positionen frei sind.pp3

Hinweis: Verwenden Sie die Tatsache, dass die Restklasse ring modulo ein Feld ist, wenn prim ist und daher höchstens Lösungen hat.ppi2=c2

Raphael
quelle
2

Wenn Ihre Hash-Funktion die Form wobei eine Primzahl ist und zufällig ausgewählt wird, ist die Wahrscheinlichkeit, dass zwei verschiedene Schlüssel zu demselben Bucket gehasht werden, . Für ist was sehr klein ist.h(k)=a×kmodmma1mm=1009Pr{h(x)=h(y),xy}=0.00099108027

Dieses Schema ist bekannt als: Universal Hashing.

Saadtaame
quelle