\documentclass[10pt,a4paper]{article}
\usepackage[pdftex]{graphicx}
\usepackage{fullpage}
\usepackage{url}
\usepackage{verbatim}
\usepackage[dutch]{babel}

\begin{document}
\begin{center}
{\huge Twee verschillende husseltabellen} \\

Datastructuren, UvA. {\em \today} \\
0440949, Andreas van Cranenburgh \\
\end{center}

%\abstract{ }

\section{Inleiding}
In dit verslag wordt bekeken of een ketting-husseltabel significant beter
presteert dan een aftastende husseltabel, door twee zelfgemaakte implementaties
te vergelijken.

\section{Implementatie}
\subsection{Ketting-husseltabel}
De ketting-husseltabel handelt husselbotsingen af door elementen met dezelfde
husselcode in een gelinkde lijst te plaatsen. Telkens wanneer tijdens het
toevoegen van een element reeds een ander element in de tabel aanwezig is op de
gewenste plek, dan wordt dit element de nieuwe kop van deze lijst.

Het verwijderen van elementen is hetzelfde als het verwijderen van een element
uit een gelinkde lijst: de voorganger van het element word gelinkt aan het
opvolgende element, waarbij de referentie naar het te verwijderen element
verdwijnt.

Als de tabel voor $75\%$ gevuld is wordt de vergrotingsroutine aangeroepen. De
groote wordt verdubbeld, plus \'e\'en, in de hoop dat hier een priemgetal uit
zal komen. Vervolgens worden alle elementen opnieuw in de tabel geplaatst.

\subsection{Aftastende husseltabel}
De aftastende husseltabel handelt botsingen af door het eerstvolgende vrije
vakje op te zoeken, zolang hier nog ruimte voor is. Als er geen vrije ruimte is
na de elementen met dezelfde husselcode en voor elementen met een andere, dan
wordt de husseltabel vergroot (`gegroeid'), waarna er zeker een vrije plek zal
zijn. Het aftasten vormt een routine die door alle operaties wordt aangeroepen.

Het verwijderen is ingewikkelder. Veel implementaties markeren verwijderde
elementen slechts als `beschikbaar.' Dit heeft echter het grote nadeel dat na
verloop van tijd de tabel vol kan komen te staan met lege elementen.

Deze implementatie maakt gebruik van het algoritme van Knuth (1998), om
clusters van elementen te comprimeren nadat er een element verwijderd is. Alle
elementen na het zojuist verwijderde element worden opgeschoven, totdat er een
vrij slot bereikt wordt.

Net als bij de ketting-husseltabel wordt ook deze tabel vergroot, maar dan al
wanneer $50\%$ van de capaciteit gebruikt is.

\section{Prestatiemeting}
Voor de presatiemeting zijn de twee ge\"implementeerde husseltabellen
vergeleken met een beschikbare referentie-implementatie:
\texttt{java.lang.HashMap} \footnote{Er is gekozen voor \texttt{HashMap} omdat
deze, in tegenstelling tot \texttt{Hashtable}, geen synchronisatiebeloftes
doet, en daardoor dus een eerlijkere vergelijking biedt} (een
ketting-husseltabel). Vervolgens worden de drie husseltabellen als experiment
gevuld met $100000$ getallen, welk steeds dezelfde reeks semi-willekeurige
getallen zijn. Dan wordt het vorige getal opgevraagd, en als laatste wordt met
$30\%$ kans het element daarvoor verwijderd. Dit experiment wordt $100$ maal
herhaald, telkens met lege tabellen, en met steeds dezelfde {\em seed} voor de
willekeurige getallen.

De tijdsmeting gebeurd met \texttt{System.currentTimeMillis()}. Deze geeft
helaas niet de werkelijke processortijd weer, maar heeft wel het voordeel dat
deze binnen Java is aan te roepen. Om optimalisaties uit schakelen is
\texttt{java} aangeroepen met de optie \texttt{-Xint}, hierdoor wordt alle
gecode geinterpreteerd, en nooit gecompileerd.

De uitvoer van het programma is dusdanig dat deze meetgegevens direct als
geconcateneerde vectors naar het statistisch programma `R' kunnen worden gevoerd.

\section{Resultaten}
Als nulhypothese stellen we dat de ketting-husseltabel even snel zal zijn als
de aftastende husseltabel, met een significantieniveau van $\alpha = 0.5$.

In het eerste experiment vergelijken we de prestaties van alle drie
fundamentele operaties van de husseltabel, viz.\ \texttt{get, put} en
\texttt{remove}. Een element wordt toegevoegd, opgevraagd en weer verwijderd.

De honderd resultaten van de drie husseltabellen zijn als volgt samen te vatten:

\begin{verbatim}
> summary(referentie)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
  811.0   819.8   822.0   830.2   823.0  1302.0
> summary(ketting)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
  751.0   757.0   763.0   771.5   765.0  1371.0
> summary(aftastend)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
  841.0   845.0   847.0   868.2   849.0  1462.0
\end{verbatim}

Vervolgens kan met een statistische toets bepaald worden of de gemiddelden significant afwijken:

\begin{verbatim}
> wilcox.test(ketting, aftastend)

        Wilcoxon rank sum test with continuity correction

data:  ketting and aftastend
W = 187, p-value < 2.2e-16
\end{verbatim}

\begin{figure}
\includegraphics[scale=0.5]{hist}
\caption{De histogrammen van de resultaten. Uitschieters boven het derde kwartiel zijn weggelaten.}
\end{figure}

Aangezien de p-waarde ruimschoots kleiner is dan $\alpha = 0.05$, moet de
nulhypothese verworpen worden, de twee implementaties hebben dus wel degelijk
een verschillende gemiddelde snelheid.


\section{Conclusie}
De hier ge\"implementeerde ketting-husseltabel is sneller gebleken dan zowel
een aftastende husseltabel, alsook de referentie implementatie van de
Javabibliotheek. De aftastende husseltabel is gemiddeld langzamer dan
ketting-husseltabellen. 

Dit is intu\"itief te verklaren doordat het afhandelen
van botsingen bij de aftastende husseltabel verdere bostingen kan veroorzaken,
omdat plaatsen worden ingenomen die voor andere husselwaarden bestemd zijn. De
ketting-husseltabel laat in vergelijking daarmee meer ruimte over, en zal dus
minder last hebben van botsingen.

\section{Referenties}
De broncode: \url{https://unstable.nl/andreas/ai/ds/opdr4/}, opstarten als
\texttt{java -Xint Assignment4} \\
\\
Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 6.4: Hashing, pp.513–558.

\end{document}