

\begin{slide}{Kollisionen behandeln:}

\begin{itemize}
\item außerhalb der Tabelle: 
  $t[i] =$ \emph{Liste aller} $x$ mit $h(x)=i$.
  Nachteil: Extraplatz für Listenzeiger
\item innerhalb der Tabelle:
  \begin{itemize}
  \item speichere $y$ in $t[h(y)+1]$ oder$t[h(y)+2]$ oder \dots
    
    Nachteil: Tabelle \glqq verklebt\grqq \\
    (belegte Blöcke erzeugen weitere Kollisionen)

  \item doppeltes Hashing: benutze $h_1, h_2$
    und benutze Indizes $h_1(y), h_1(y) + h_2(y), h_1(y) + 2 h_2(y), \ldots$.

    Vorteil: kein Verkleben (Schrittweiten sind verschieden!)
  \end{itemize}
\end{itemize}

Übung: diskutiere Löschen aus einer Hashtabelle

\end{slide}


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "~/edu/ws03/informatik/folien/informatik"
%%% End: 
