Hashtabelle-Fächerzahl

Eine Hashtabelle ist nur so schnell wie das Array dahinter gut bemessen ist. Speichern Sie n Schlüssel in m Fächern, entscheidet der Auslastungsfaktor α = n / m, wie lang Ketten wachsen, wann offenes Adressieren klumpt und wie oft eine Vergrößerung zündet. Wählen Sie m zu klein, läuft jede Suche durch einen Haufen Kollisionen. Wählen Sie m viel zu groß, zahlen Sie RAM für leere Plätze, die der Latenz nicht helfen. Dieser Rechner für die Fächerzahl einer Hashtabelle nimmt die erwartete Elementzahl, einen Ziel-Auslastungsfaktor wie den Java-HashMap-Standard 0.75 und eine Rundungsstrategie und liefert die kleinste zuweisbare Tabelle, die die Belegung bei oder unter diesem Ziel hält. Zuerst berechnet er die rohe Decke ceil(n / α) und rundet diese Untergrenze auf die nächste Zweierpotenz oder die nächste Primzahl — die zwei Größen, die Produktionsmaps tatsächlich anlegen. Zweierpotenzgrößen passen zu maskenbasierten Maps, die mit dem bitweisen UND des Hashs und (m minus eins) indizieren. Primzahlen passen zu modulobasierten Maps, die mit hash mod m indizieren.

Warum der Auslastungsfaktor, nicht eine runde Schätzung, die Fächerzahl bestimmen soll

Der Auslastungsfaktor ist die einzige Belegungszahl, die zwischen Sprachen wandert. Java HashMap steht standardmäßig bei 0.75 und vergrößert, wenn die Größe die Kapazität mal diesen Faktor übersteigt. Rust hashbrown und viele Swiss-table-Portierungen liegen nahe 0.875, bevor sie wachsen.

Klassischer Lehrcode mit getrennter Verkettung zielt oft auf 0.5 oder 1.0. In jedem Fall gilt dieselbe Planungsidentität: Sie brauchen mindestens ceil(n / α) Plätze, wenn n Schlüssel bei oder unter dem Ziel α bleiben sollen. Diese rohe Decke ist fast nie die Zahl, die Sie zuweisen.

Maskenbasierte Implementierungen verlangen, dass m eine Zweierpotenz ist, damit der Index ein einziges bitweises UND ist; deshalb werden aus 1 000 Schlüsseln bei 0.75 genau 2 048 Fächer statt 1 334. Modulobasierte Implementierungen bevorzugen eine Primzahl, damit ein schwacher Hash sich weiter über Restklassen verteilt; deshalb werden dieselben 1 000 Schlüssel zur nächsten Primzahl bei oder über 1 334. Nutzen Sie diese fünf Kennzahlen gemeinsam.

Eine Tabelle, die weit zur nächsten Zweierpotenz hochgerundet hat, hat eine bequeme tatsächliche Last und großen headroom; eine, die auf einer nahen Primzahl landete, sitzt enger und näher an einer Vergrößerung. 1 024 oder 4 096 zu raten, weil diese Zahlen nach Informatik aussehen, ist der Weg, auf dem Dienste entweder eine RAM-Seite verschwenden oder in der ersten Verkehrsminute eine Vergrößerung auslösen.

Wann sich diese Dimensionierung lohnt, und ihre Grenzen

Nutzen Sie das Browser-Werkzeug, wenn Sie die Anfangskapazität einer HashMap wählen, einen Kommentar schreiben, der begründen muss, warum das Array 2 048 und nicht 1 334 ist, oder eine Prüfung durch den Unterschied zwischen Maskentabelle und Modulo-Tabelle führen. Streichen Sie den Auslastungsfaktor, bis der headroom die nächste Wachstumsspitze deckt, und behalten Sie das gerundete m. Stellen Sie das Ergebnis einem Rechner für erwartete Kollisionen gegenüber, sobald m bekannt ist: jener Geschwister beantwortet, wie viele Schlüssel ein Fach teilen, während diese Seite beantwortet, wie viele Fächer Sie zuerst zuweisen.

Die zwei Suchen sind verschiedene Tickets und dürfen einander nicht kannibalisieren. Die Ergebnisse sind vollständig deterministisch: dieselben items, Lastfaktor und Rundung ergeben stets denselben Vektor, sodass Sie Beispiele in Tests und Unterrichtsmaterial festnageln können. Es gibt kein Sprachmodell, keinen externen Statistikdienst und keine Zufälligkeit.

Verdrahten Sie den Endpunkt in Hashtabellen-Tutorien, Compiler-Backends, die eine statische Tabelle ausgeben, und Dienstvorlagen, die eine Kapazität vor dem ersten Einfügen wählen müssen.