Hash Table

Zweck

Zugriff auf Schlüssel-Wert-Paare in durchschnittlich konstanter Zeit bieten und Wörterbücher und Mengen effizient implementieren.

Mechanismus

hash(key) % capacity lokalisiert den Bucket. Kollisionsbehandlung: Separate Chaining (Bucket hält eine Liste) oder offene Adressierung (Sondieren des nächsten freien Slots). Lastfaktor = Elemente / Buckets; Überschreiten der Schwelle löst Resize und Rehash aus. Eine gute Hashfunktion verteilt Schlüssel gleichmäßig.

Anwendungsfälle

• Wörterbuch- und Map-Implementierungen
• Datenbankindizes
• Caches (LRU)
• Deduplizierung und Mengen

Beispiele

• Eingabe

  {"name":"Ada"} → hash("name")=5

  Output

  Value stored in bucket 5

  O(1) on average

Häufige Fehler

A poorly distributed hash function causes collision pile-ups

Use a high-quality hash function and a suitable load factor