Normalerweise funktioniert eine einfache Hash-Funktion, indem die "Bestandteile" der Eingabe (Zeichen im Falle einer Zeichenkette) mit den Potenzen einer Konstante multipliziert und in einem ganzzahligen Typ zusammengerechnet werden. Ein typischer (wenn auch nicht besonders guter) Hash-Wert für eine Zeichenkette könnte zum Beispiel so aussehen:
(first char) + k * (second char) + k^2 * (third char) + ...
Wenn dann eine Reihe von Zeichenketten mit demselben ersten Zeichen eingegeben wird, sind die Ergebnisse alle gleich modulo k, zumindest bis der Ganzzahltyp überläuft.
[Die Java-Zeichenfolge hashCode ist diesem Beispiel unheimlich ähnlich - sie führt die Zeichen in umgekehrter Reihenfolge aus, mit k=31. So erhält man auffällige Beziehungen modulo 31 zwischen Zeichenketten, die auf die gleiche Weise enden, und auffällige Beziehungen modulo 2^32 zwischen Zeichenketten, die bis auf das Ende identisch sind. Das bringt das Verhalten von hashtable nicht ernsthaft durcheinander].
Eine Hashtabelle funktioniert, indem der Modulus des Hashes über die Anzahl der Eimer genommen wird.
Es ist wichtig, dass in einer Hashtabelle keine Kollisionen für wahrscheinliche Fälle entstehen, da Kollisionen die Effizienz der Hashtabelle verringern.
Nehmen wir nun an, jemand gibt eine ganze Reihe von Werten in eine Hashtabelle ein, die in irgendeiner Beziehung zueinander stehen, z. B. alle das gleiche erste Zeichen haben. Das ist ein ziemlich vorhersehbares Nutzungsmuster, würde ich sagen, also wollen wir nicht, dass es zu viele Kollisionen gibt.
Es stellt sich heraus, dass "wegen der Natur der Mathematik", wenn die Konstante, die in der Hash verwendet wird, und die Anzahl der Eimer, sind koprimieren werden Kollisionen in einigen häufigen Fällen auf ein Minimum reduziert. Wenn sie es nicht sind koprimieren dann gibt es einige recht einfache Beziehungen zwischen den Eingaben, bei denen die Kollisionen nicht minimiert werden. Alle Hashes kommen modulo des gemeinsamen Faktors gleich heraus, was bedeutet, dass sie alle in den 1/n-ten der Buckets fallen, die diesen Wert modulo des gemeinsamen Faktors haben. Man erhält n-mal so viele Kollisionen, wobei n der gemeinsame Faktor ist. Da n mindestens 2 ist, würde ich sagen, dass es für einen relativ einfachen Anwendungsfall inakzeptabel ist, mindestens doppelt so viele Kollisionen wie normal zu erzeugen. Wenn ein Benutzer unsere Verteilung in Eimer zerlegt, dann soll es ein Unfall sein und nicht eine einfache vorhersehbare Nutzung.
Hash-Table-Implementierungen haben natürlich keine Kontrolle über die darin enthaltenen Elemente. Sie können nicht verhindern, dass sie miteinander in Beziehung stehen. Es muss also sichergestellt werden, dass die Anzahl der Konstanten und der Eimer gleich groß ist. Auf diese Weise verlässt man sich nicht allein auf die "letzte" Komponente, um den Modulus des Buckets in Bezug auf einen kleinen gemeinsamen Faktor zu bestimmen. Soweit ich weiß, müssen sie dazu nicht primär sein, sondern nur koprimal.
Wenn aber die Hash-Funktion und die Hashtabelle unabhängig voneinander geschrieben werden, dann weiß die Hashtabelle nicht, wie die Hash-Funktion funktioniert. Sie könnte eine Konstante mit kleinen Faktoren verwenden. Wenn man Glück hat, funktioniert sie vielleicht ganz anders und ist nicht linear. Wenn der Hash gut genug ist, dann ist jede beliebige Anzahl von Buckets in Ordnung. Eine paranoide Hashtabelle kann jedoch nicht von einer guten Hash-Funktion ausgehen und sollte daher eine Primzahl von Buckets verwenden. Ebenso sollte eine paranoide Hash-Funktion eine große Primzahlkonstante verwenden, um die Wahrscheinlichkeit zu verringern, dass jemand eine Anzahl von Buckets verwendet, die zufällig einen gemeinsamen Faktor mit der Konstante hat.
In der Praxis ist es meiner Meinung nach ziemlich normal, eine Potenz von 2 als Anzahl der Eimer zu verwenden. Das ist praktisch und erspart die Suche oder die Vorauswahl einer Primzahl der richtigen Größenordnung. Man verlässt sich also darauf, dass die Hash-Funktion keine geraden Multiplikatoren verwendet, was im Allgemeinen eine sichere Annahme ist. Dennoch kann es bei Hash-Funktionen wie der obigen gelegentlich zu fehlerhaftem Verhalten kommen, und die Anzahl der Primzahlen könnte hier weiterhelfen.
Das Prinzip "alles muss primär sein" ist meines Wissens eine ausreichende, aber keine notwendige Bedingung für eine gute Verteilung über Hashtabellen. Es erlaubt jedem, zu interagieren, ohne davon ausgehen zu müssen, dass die anderen dieselbe Regel befolgt haben.
[Edit: Es gibt noch einen anderen, spezielleren Grund, eine Primzahl von Buckets zu verwenden, nämlich wenn man Kollisionen mit linearer Sondierung behandelt. Dann berechnen Sie einen Stride aus dem Hashcode, und wenn dieser Stride ein Faktor der Bucket-Anzahl ist, dann können Sie nur (Bucket-Anzahl / Stride) Sondierungen durchführen, bevor Sie wieder da sind, wo Sie angefangen haben. Der Fall, den Sie am meisten vermeiden wollen, ist stride = 0, natürlich, die special-case werden muss, aber zu vermeiden, auch special-casing bucket_count / stride gleich eine kleine ganze Zahl, können Sie einfach die bucket_count Primzahl und nicht kümmern, was die stride ist, solange es nicht 0 ist].
