Hash-Tabellen

bieten andere Implementierung von Abbildungen (oft die schnellste)

class HashMap<K,V> implements Map<K,V> { ... }

benutze schnelle Hashfunktion h : K$\to${0...m - 1}

class Object { int hashCode () { .. } }

Idee: Deklariere Array t[0...m - 1], 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?

benötigt Methode boolean equals(Object o)