%% -*- mode: latex; TeX-master: "compilerbau.tex"; -*-

\begin{slide}{Re-Hashing}

\kopf{$ $Id: rehash.tex,v 1.1 2006-10-09 13:24:16 waldmann Exp $ $}

\begin{itemize}
\item Tabelle zu klein $\to$ zu voll $\to$ viele Kollisionen $\to$ langsam.
\item Tabelle zu groß: Platz verschenkt.
\end{itemize}

Lösung: falls Tabelle gewissen Füllstand erreicht,
dann zu neuer, größerer Tabelle wechseln ($=$ re-Hashing).

am einfachsten: Tabellengröße ist immer Potenz von 2;
dann: vergrößern $=$ verdoppeln.

Beim re-Hashing müssen alle Einträge betrachtet werden,
das findet aber nur selten statt,
so daß die amortisierte Laufzeit trotzdem konstant ist


\end{slide}
