\begin{slide}{Hash-Tabellen}

bieten andere Implementierung von Abbildungen
(oft die schnellste)
\begin{verbatim}
class HashMap<K,V> implements Map<K,V> { ... }
\end{verbatim}

\bigskip

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

\begin{verbatim}
class Object { int hashCode () { .. } }
\end{verbatim}

Idee: Deklariere Array $t[0 \dots m-1]$, 
speichere $x$ in $t [h(x)]$.

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

\bigskip

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

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

\bigskip

benötigt Methode \verb|boolean equals(Object o)|


\end{slide}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "y"
%%% End: 
