Warum nimmt ein Hashtable -Eimer eine Primzahl?
Eine Hash -Funktion haben
H (c) = c % n;
Wenn n eine zusammengesetzte Zahl nimmt, besteht das einfachste Beispiel darin, 2^N zu diesem Zeitpunkt 2^3 = 8 zu nehmen
H (11100 (binär)) = H (28) = 4
H (10100 (binär)) = H (20) = 4
Zu diesem Zeitpunkt schlägt das vierte Bit binär (von rechts nach links) von C "scheitern", was bedeutet, dass unabhängig davon, welcher Wert im 4. Stück C genommen wird, zu demselben Wert von H (c) führt. Zu diesem Zeitpunkt beteiligt sich das vierte Bit C C überhaupt nicht an der Funktionsweise von H (c), so dass H (c) die Eigenschaften von C nicht vollständig widerspiegeln kann, wodurch die Wahrscheinlichkeit von Konflikten erhöht wird.
Bei anderen zusammengesetzten Zahlen werden einige C -Teile von C in unterschiedlichem Maße "fehlgeschlagen", was zu Konflikten in einigen gemeinsamen Anwendungen führt.
Das Eingehen von Primzahlen kann jedoch grundsätzlich sicherstellen, dass jedes Bit C am Betrieb von H (c) teilnimmt, wodurch die Wahrscheinlichkeit von Konflikten in gemeinsamen Anwendungen verringert wird. ．
(Persönliche Meinung: Manchmal ist die Effizienz, keine Primzahlen zu nehmen, nicht schlecht ... aber es ist zweifellos sicherer, Primzahlen zu nehmen ...)
Das obige ist mein Verständnis
Dies bedeutet, dass in gemeinsamen Anwendungen einige Daten häufig ähnlich sind. Es ist besser, Primzahlen zu diesem Zeitpunkt zu verwenden. Beispielsweise befinden sich die zu gespeicherten Daten in einem komprimierten Zustand, z. B. das Speichern einer Tabelle, in der der aktuelle Suchzustand beschrieben wird. Zu diesem Zeitpunkt ist die Wahrscheinlichkeit, ohne Primzahlen Hashhing zu haben, relativ hoch.
Wenn es sich um eine zufällig verteilte Ganzzahl handelt, ist der Hash -Modul der gleiche, solange er groß genug genommen wird, aber dies ist offensichtlich nicht praktisch.
Was Sie gesagt haben, ist eine besondere Situation, denn wenn eine relativ kleine Primzahl ausgewählt wird, kann die große Primzahl N nur in einem bestimmten Bit des n-Digit-Systems fehlschlagen. In Kombination mit den Eigenschaften des Computersystems ist die n-Digit-Darstellung häufig nicht kritisch, während das häufig verwendete 2^n-Digit-System kritischer ist, sodass Konflikte vermieden werden können.
Tatsächlich habe ich einige große Zahlen verwendet, um es zu testen, um eine Adjazenzmatrix zu speichern, die in Binärdatei komprimiert wurde. Wenn der Modul groß genug ist, kann selbst die zusammengesetzte Zahl sehr eng die Primzahl auswirken, aber in einigen (mehreren Dutzend) Verbundzahlen wird die Effizienz stark reduziert, sodass die Primzahlen relativ sicher sind.
Sie können auch Ihre eigenen Experimente durchführen, keine zufälligen Ganzzahlen wählen, sondern einige gängige Anwendungen, verwenden Sie Primzahlen und zusammengesetzte Zahlen zum Testen, wobei Sie den durchschnittlichen Ladefaktor hauptsächlich untersuchen. Die Schlussfolgerung, die Sie erhalten, kann dieselbe wie meine sein: Die Verbundzahlen sind höchstens gut gut, aber der Effekt ist in einigen zusammengesetzten Zahlen und fast alle Primzahlen haben gute Ergebnisse.
Ich persönlich denke, dass es im Allgemeinen, wenn Sie keine Primzahlen nehmen, eine gewisse Gefahr besteht. Die Gefahr tritt auf, wenn die Nicht-Primes-Zahl m = x*y als ausgewählt angenommen wird, und wenn der Schlüssel des Hashs mit diesem Divisor X zusammenhängt, wird er unglücklich sein. Im schlimmsten Fall gehen alle davon aus, dass es sich um ein Vielfaches von X handelt, dann können Sie sich vorstellen, dass das Ergebnis von Hash: 1 ~ y, nicht 1 ~ m ist. Wenn jedoch die Größe des Eimers als Primzahl ausgewählt wird, wird es kein Problem geben.
Danke fürs Lesen, ich hoffe, es kann Ihnen helfen. Vielen Dank für Ihre Unterstützung für diese Seite!