Hashing:
Idee: Statt in einer Menge von Datensätzen durch
Schlusselvergleiche zu suchen, ermittle die Position eines Elements im Speicher (bzw. einem Array) durch eine arithmetische Berechnung.
Hashing belegungsfaktor
Fur eine Hashtabelle der Größe m, die aktuell n Schlussel speichert, ist α =n/m der Belegungsfaktor der Tabelle
Hashfunktion:
Wir wählen eine Hashfunktion h : K → {0, . . . , m − 1}, die
jedem Schlussel k ∈ K einen eindeutigen – aber i.A. nicht umgekehrt eindeutigen – Hashwert zuordnet.
Hashing Laufzeit:
Vorteil: Laufzeit fur die Operationen Suchen, Einfügen und Entfernen liegt im Idealfall in Θ(1), wenn wir annehmen, dass h(s) in konstanter Zeit berechnet werden kann.
Einschränkung:
*Gilt h(k) = h(k’) fur k != k’ , d.h., zwei verschiedene Schlussel
haben den gleichen Hashwert, so wird dies Kollision genannt.
*Θ(1) gilt nur unter der Annahme, dass die Anzahl der
Kollisionen vernachlässigbar klein ist.
- Im Erwartungsfall (bei entsprechender Konfiguration)
erreichbar.
Im Worst-Case liegt der Aufwand in O(n).
Was charakterisiert eine gute Hashfunktion?
Vor allem:
* Verwendete Schlussel sollen möglichst gleichmäßig auf alle
Plätze 0, . . . , m − 1 der Hashtabelle aufgeteilt werden.
- Auch kleinste Änderungen im Schlüssel sollen zu einem
anderen, möglichst unabhängigen Hashwert fuhren.
Divisions-Rest-Methode
Annahme: k ∈ N
Berechnung:
h(k) = k mod m
Eigenschaften:
* Die Hashfunktion kann sehr schnell berechnet werden.
* Die richtige Wahl von m ist hier sehr wichtig. Eine gute Wahl
fur m ist eine Primzahl.
Hashtabelle einfügen Laufzeit
0(1)
Hashtabelle suchen Laufzeit
0(n/m) average , 0(n) worst
Lineares Sondieren: Probleme
- Nach dem Einfugen ist die Wahrscheinlichkeit für einen neu
einzufugenden Schlüssel in der Hashtabelle an einer gewissen
Position gespeichert zu werden fur die verschiedenen Positionen unterschiedlich. - Wird ein Platz belegt, dann verändert sich die
Wahrscheinlichkeit fur das Einfügen an seinem nachfolgenden
Platz.
Double Hashing
- Im Allgemeinen ist Double Hashing effizienter als
quadratisches Hashing.
I
*In der Praxis entsprechen die Ergebnisse von Double Hashing
nahezu denen von uniformen Hashing.
