Eine Hashfunktion ist eine Funktion, die eine große Eingabemenge, die Schlüssel, auf eine kleinere Zielmenge, die Hashwerte abbildet. Hashfunktionen sind im allgemeinen nicht injektiv.
Dynamische Datenspeicherung
Hashing kann zur dynamischen Datenspeicherung verwendet werden. Die Grundidee dabei ist es, jeden Schlüssel an der Position seines Hashwertes zu speichern.
Bei Hashtabellengröße
Damit die Anzahl der Kollision klein bleibt, sollte die Anzahl der Positionen in einer Hashtabelle quadratisch in der Anzahl der einzufügenden Werte sein.
Der Belegungs- oder Lastfaktor einer Hashtabelle ist
Verfahren
Anmerkungen
- Kollisionen sind relativ schnell sehr wahrscheinlich, siehe Geburtstagsparadoxon
- Zur Kollisionsvermeidung kann man quadratische viele Positionen in Abhängigkeit der einzufügenden Werte einplanen (unpraktikabel)
- Zeit-Platz-Tradeoff
- In der Praxis reicht weniger Platz aus, weil es nur konstant viele Kollisionen an genau einer Stelle gibt, wenn jede Position mit gleicher Wahrscheinlich
- Im vergleich zu balancierten Suchbäumen erlauben Hashfunktionen keine Bereichsabfragen, haben dafür aber eine sehr gute Komplexität