In verschiedenen Hashtabellen-Implementierungen habe ich "magische Zahlen" gesehen, wenn eine veränderbare Hash-Tabelle die Größe ändern sollte (wachsen). In der Regel liegt diese Zahl zwischen 65% und 80% der Werte pro zugewiesenen Slots. Ich gehe davon aus, dass eine höhere Zahl das Potenzial für mehr Kollisionen und eine geringere Anzahl weniger auf Kosten der Verwendung von mehr Speicher bietet.
Meine Frage ist, wie ist diese Nummer angekommen?
Ist das willkürlich? basierend auf Tests? basierend auf einer anderen Logik?
Bei einer Schätzung starten die meisten Leute von den Zahlen in einem Buch (z. B. Knuth, Band 3), die durch Testen erzeugt wurden. Abhängig von der Situation können einige danach Tests durchführen und entsprechende Anpassungen vornehmen - aber von dem, was ich gesehen habe, sind diese wahrscheinlich in der Minderheit.
Wie ich in einer vorherigen Antwort beschrieben habe hängt die "richtige" Zahl auch stark davon ab, wie Sie Kollisionen lösen. Im besten oder schlechtesten Fall scheint diese Tatsache weitgehend ignoriert zu werden - Menschen wählen häufig keine Zahlen, die für die Kollisionsauflösung, die sie verwenden, besonders geeignet sind.
OTOH, der andere Punkt, den ich in meinen Tests fand, ist, dass es nur selten einen großen Unterschied macht. Sie können Zahlen über einen ziemlich breiten Bereich auswählen und erhalten eine ähnliche Gesamtgeschwindigkeit. Die Hauptsache ist, vorsichtig zu sein, um zu vermeiden, dass die Zahl zu hoch wird, besonders wenn Sie etwas wie lineares Sondieren für die Kollisionsauflösung verwenden.
Ich denke, Sie wollen nicht in Betracht ziehen, "wie voll" die Tabelle ist (wie viele "Buckets" aus den Buckets insgesamt Werte haben), sondern die Anzahl der Kollisionen, die ein Spot für ein neues Objekt benötigt.
Ich habe vor Jahren ein Compiler-Buch gelesen (ich kann mich nicht mehr an Titel oder Autoren erinnern), das nur verlinkte Listen vorgeschlagen hat, bis Sie mehr als 10 bis 12 Elemente haben. Das scheint mehr als 10 Kollisionen zu unterstützen, bedeutet Zeit für die Größenanpassung.
Design und Implementierung von Dynamic. Hashing für Sets und Tabellen in Icon legt nahe, dass eine durchschnittliche Hash-Kettenlänge von 5 (in diesem Algorithmus die durchschnittliche Anzahl von Kollisionen) ausreicht, um einen erneuten Hash auszulösen. Scheint vom Testen unterstützt, aber ich bin mir nicht sicher, ob ich das Papier richtig lese.
Es sieht so aus, als ob die Größenänderungsbedingung hauptsächlich das Ergebnis von Tests ist.
Das hängt von den Schlüsseln ab. Wenn Sie wissen, dass Ihre Hash-Funktion für alle möglichen Schlüssel perfekt ist (zum Beispiel mit gperf ), dann wissen Sie das Sie werden nur wenige Kollisionen haben, daher ist die Anzahl höher.
Aber meistens wissen Sie nicht viel über die Tasten, außer dass sie Text sind. In diesem Fall müssen Sie raten, da Sie nicht einmal Testdaten haben, um im Voraus herauszufinden, wie sich Ihre Hash-Funktion verhält.
Sie hoffen also auf das Beste. Wenn Ihre Hash-Funktion für die Schlüssel sehr schlecht ist, dann werden Sie viele Kollisionen haben und der Punkt des Wachstums wird niemals erreicht werden. In diesem Fall ist die gewählte Zahl irrelevant.
Wenn Ihre Hash-Funktion ausreichend ist, sollten nur wenige Kollisionen auftreten (weniger als 50%), so dass eine Zahl zwischen 65% und 80% sinnvoll erscheint.
Das sagte: Wenn Ihre Hash-Tabelle nicht perfekt sein muss (= riesige Größe oder viele Zugriffe), nicht stören. Wenn Sie, sagen wir, zehn Elemente haben, ist die Berücksichtigung dieser Probleme Zeitverschwendung.
Soweit ich weiß, ist die Zahl eine Heuristik, die auf empirischen Tests basiert.
Bei einer einigermaßen guten Verteilung der Hashwerte scheint der magische Ladefaktor - wie Sie sagen - normalerweise bei 70% liegt. Ein kleinerer Ladefaktor bedeutet, dass Sie Platz verschwenden, um keinen echten Nutzen zu erzielen. Ein höherer Ladefaktor bedeutet, dass Sie weniger Speicherplatz benötigen, aber mehr Zeit mit Hash-Kollisionen verbringen müssen.
(Wenn Sie natürlich wissen, dass Ihre Hash-Werte perfekt verteilt sind, kann Ihr Ladefaktor 100% betragen und Sie haben immer noch keinen verschwendeten Speicherplatz und keine Hash-Kollisionen.)
Kollisionen hängen stark von Daten und der verwendeten Hash-Funktion ab.
Die meisten Zahlen basieren auf Heuristiken oder Annahmen über die normale Verteilung von Hashwerten. (AFAIK-Werte von etwa 70% sind typisch für erweiterbare Hash-Tabellen, aber man kann immer solche Datenströme konstruieren, dass man viel mehr / weniger Kollisionen bekommt)