Hash-Tabellen

bieten andere Implementierung von Mengen (oft die schnellste)

class HashSet implements Set { ... }


benutze schnelle Hashfunktion h : $ \Sigma^{*}_{}$$ \to${0...m - 1}

Idee: Deklariere Array t[...], speichere x in t[h(x)].

Parameter (Tabellengröße, Hashfunktion) geeignet wählen, dann ``praktisch konstante'' Laufzeit für alle Operationen.


Hash-Kollision: x $ \neq$ y und h(x) = h(y).

x ist schon in t[h(x)], wo soll y hin?



Johannes Waldmann 2006-01-26