\documentclass{bschlangaul-aufgabe}
\bLadePakete{mathe}
\begin{document}
\bAufgabenMetadaten{
  Titel = {4. Hashing},
  Thematik = {Hashing mit verketteten Listen und offener Adressierung},
  Referenz = 66115-2016-F.T2-A4,
  RelativerPfad = Examen/66115/2016/03/Thema-2/Aufgabe-4.tex,
  ZitatSchluessel = examen:66115:2016:03,
  ZitatBeschreibung = {Seite 7},
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Streutabellen (Hashing), Separate Verkettung, Offene Adressierung},
  EinzelpruefungsNr = 66115,
  Jahr = 2016,
  Monat = 03,
  ThemaNr = 2,
  AufgabeNr = 4,
}

Betrachte eine Hashtabelle der Größe $m = 10$.
\index{Streutabellen (Hashing)}
\footcite[Seite 7]{examen:66115:2016:03}

\begin{enumerate}

%%
% a)
%%

\item Welche der folgenden Hashfunktionen ist für Hashing mit
verketteten Listen\index{Separate Verkettung} am besten geeignet?
Begründen Sie Ihre Wahl!

\begin{enumerate}
\item $h_1(x) = (4x + 3) \mod m$

\begin{bAntwort}
\begin{description}
\item[1] $h_1(1) = (4 \cdot 1 + 3) \mod 10 = 7$
\item[2] $h_1(2) = (4 \cdot 2 + 3) \mod 10 = 1$
\item[3] $h_1(3) = (4 \cdot 3 + 3) \mod 10 = 5$
\item[4] $h_1(4) = (4 \cdot 4 + 3) \mod 10 = 9$
\item[5] $h_1(5) = (4 \cdot 5 + 3) \mod 10 = 3$
\item[6] $h_1(6) = (4 \cdot 6 + 3) \mod 10 = 7$
\item[7] $h_1(7) = (4 \cdot 7 + 3) \mod 10 = 1$
\item[8] $h_1(8) = (4 \cdot 8 + 3) \mod 10 = 5$
\item[9] $h_1(9) = (4 \cdot 9 + 3) \mod 10 = 9$
\item[10] $h_1(10) = (4 \cdot 10 + 3) \mod 10 = 3$
\end{description}
\end{bAntwort}

\item $h_2(x) = (3x + 3) \mod m$

\begin{bAntwort}
\begin{description}
\item[1] $h_2(1) = (3 \cdot 1 + 3) \mod 10 = 6$
\item[2] $h_2(2) = (3 \cdot 2 + 3) \mod 10 = 9$
\item[3] $h_2(3) = (3 \cdot 3 + 3) \mod 10 = 2$
\item[4] $h_2(4) = (3 \cdot 4 + 3) \mod 10 = 5$
\item[5] $h_2(5) = (3 \cdot 5 + 3) \mod 10 = 8$
\item[6] $h_2(6) = (3 \cdot 6 + 3) \mod 10 = 1$
\item[7] $h_2(7) = (3 \cdot 7 + 3) \mod 10 = 4$
\item[8] $h_2(8) = (3 \cdot 8 + 3) \mod 10 = 7$
\item[9] $h_2(9) = (3 \cdot 9 + 3) \mod 10 = 0$
\item[10] $h_2(10) = (3 \cdot 10 + 3) \mod 10 = 3$
\end{description}
\end{bAntwort}
\end{enumerate}

\begin{bAntwort}
Damit die verketteten Listen möglichst klein bleiben, ist eine möglichst
gleichmäßige Verteilung der Schlüssel in die Buckets anzustreben. $h_2$
ist dafür besser geeignet als $h_1$, da $h_2$ in alle Buckets Schlüssel
ablegt, $h_1$ jedoch nur in Buckets mit ungerader Zahl.
\end{bAntwort}

%%
% b)
%%

\item Welche der folgenden Hashfunktionen ist für Hashing mit offener
Adressierung\index{Offene Adressierung} am besten geeignet? Begründen
Sie Ihre Wahl!

\begin{enumerate}
\item $h_1(x,i) = (7 \cdot x + i \cdot m) \mod m$
\item $h_2(x,i) = (7 \cdot x + i \cdot (m - 1)) \mod m$
\end{enumerate}

\begin{bAntwort}
$h_2(x,i)$ ist besser geeignet. $h_1$ sondiert immer im selben Bucket,
$(i \cdot m) \mod m$ heben sich gegenseitig auf,
zum Beispiel ergibt:

\begin{itemize}
\item $h_1(3,0) = (7 \cdot 3 + 0 \cdot 10) \mod 10 = 1$
\item $h_1(3,1) = (7 \cdot 3 + 1 \cdot 10) \mod 10 = 1$
\item $h_1(3,2) = (7 \cdot 3 + 2 \cdot 10) \mod 10 = 1$
\end{itemize}

Während hingegen $h_2$ verschiedene Buckets belegt.

\begin{itemize}
\item $h_2(3,0) = (7 \cdot 3 + 0 \cdot 9) \mod 10 = 1$
\item $h_2(3,1) = (7 \cdot 3 + 1 \cdot 9) \mod 10 = 0$
\item $h_2(3,2) = (7 \cdot 3 + 2 \cdot 9) \mod 10 = 9$
\end{itemize}
\end{bAntwort}
\end{enumerate}
\end{document}