Hash-Tabelle Lastfaktor
Füllgrad einer Hash-Tabelle: alpha = Elemente / Tabellengroesse. Werte α ≈ 0,7 gelten als guter Kompromiss zwischen Speicher und Kollisionsrate.
Hash-Tabelle Lastfaktor berechnen
Füllgrad einer Hash-Tabelle: alpha = Elemente / Tabellengroesse. Werte α ≈ 0,7 gelten als guter Kompromiss zwischen Speicher und Kollisionsrate.
- alpha — Lastfaktor
- Elemente — Elemente
- Tabellengroesse — Tabellengröße
Worum geht es?
Der Lastfaktor α (alpha) einer Hash-Tabelle gibt das Verhältnis von gespeicherten Elementen n zur Anzahl Slots m an: α = n / m. Er ist der zentrale Stellhebel zwischen Speicherverbrauch und durchschnittlicher Operationszeit.
Bei Chaining (verkettete Buckets) ist die erwartete Suchzeit etwa 1 + α/2, bei Open Addressing wächst die Suchzeit dagegen schnell gegen unendlich, wenn α → 1. In der Praxis wird daher bei α ≈ 0,7 (Java HashMap: 0,75, Python dict: ≈ 0,67) ein Resize auf die doppelte Größe ausgelöst.
Die Formel
α = Elemente / Tabellengröße
Umstellungen:
Elemente = α · Tabellengröße
Tabellengröße = Elemente / αDie Variablen
| Symbol | Bedeutung | Einheit | Erklärung |
|---|---|---|---|
| Elemente | Elemente | — | Anzahl gespeicherter Einträge. |
| Tabellengröße | Tabellengröße | — | Anzahl Slots in der Hash-Tabelle. |
| alpha | Lastfaktor | — | Füllgrad α (typisch 0,5 … 0,75). |
Minimal-Beispiel
Eine Tabelle mit 16 Slots speichert 12 Elemente:
α = 12 / 16
= 0,75Praxis-Beispiele
Beispiel 1 — Resize-Schwelle bestimmen
Java HashMap löst Resize bei α ≥ 0,75 aus. Wie viele Elemente passen in eine Tabelle mit 1024 Slots?
Elemente = 0,75 · 1024
= 768Beispiel 2 — Zielgröße für 1 Mio. Elemente
Für n = 10⁶ Elemente bei Ziel-α = 0,6:
m = 10⁶ / 0,6
≈ 1 666 667 SlotsIn der Praxis wird auf die nächste Zweierpotenz (2²¹ = 2 097 152) aufgerundet.
Beispiel 3 — Open Addressing vs. Chaining
Bei α = 0,9 sind die erwarteten Sondierungsschritte für eine erfolglose Suche:
Linear Probing: 1 / (1 − α)² = 100 Schritte
Double Hashing: 1 / (1 − α) = 10 Schritte
Chaining: 1 + α/2 ≈ 1,45 Schritte