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
Jetzt werden alle Werte nacheinander in 9 Zeilen platziert. Zum Beispiel gibt es im ersten Bucket . In der Sekunde wird es usw. geben.
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
Dies würde zu einer Hash-Tabelle mit den Werten im ersten Bucket, usw. im zweiten Bucket usw. führen.
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.
quelle
Antworten:
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=12 3 12 3 3
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).K K m K 3 3
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.4 m 4 3m/4 m/4
Im Allgemeinen:
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 .m K m
quelle
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+k⋅b H(n)=nmodm b n b
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 .11 12 11 2 3 12
quelle
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:
quelle
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×kmodm m a 1m m=1009 Pr{h(x)=h(y),x≠y}=0.00099108027
Dieses Schema ist bekannt als: Universal Hashing.
quelle