Introduktion til Hashing Applet

Allan Grønlund Jørgensen, 2007

Introduktion til Problemstilling

I denne applet arbejdes der med hash-funktioner. Det man ønsker at konstruere funktioner der kan mappe tal fra et stort talområde, til et mindre talområde, således at tallene bliver spredt så meget som muligt i det mindre talområde. Dette er en generel teknik som går under navnet hashing.

Antag at du har n forskellige tal(nøgler) fra en mængde

S = {1, 2, ... , m}

hvor m >> n, dvs. m er meget større end n.

Man ønsker at bruge de nøglerne til at indeksere i et array(tabel). Hvis man indekserer direkte ved hjælp af nøglens værdi, skal man bruge et array(tabel) med m indgange, til at indeksere de n tal.

Figur 1: Simpelt eksempel, med n = 3 hvor S = {2, 6 ,19} og m = 20. En indgang med - benyttes ikke, og der indekseres fra 0
\begin{figure}\begin{tabular}{\vert c\vert c\vert c\vert c\vert c\vert c\vert c\... ...& - &- & - & - & - & - 19 & - \\ \hline \end{tabular}\centering\end{figure}

Så i stedet for at bruge nøglen som direkte indeksering, vil vi nu lave en mindre tabel hvor vi indekserer efter nøgle x i indgangen h(x). Vi laver en tabel af størrelse 3, og indekserer efter funktionen h(x) = x mod 3, hvor "mod" betyder modulo.

Hvis i ikke har hørt om modulo før, så se efter her. Vi ønsker at beregne x mod y. Som i måske husker fra jeres unge dage, så kan x skrives som.

x = p*y + r

hvor p er heltallig og r < y er en rest. Dvs. at hvis du tager heltalsdivision x / y så får man p og der er r til rest. Modulo er defineret til at være denne rest. Dvs. her er

x mod y = r

som defineret ovenfor.

Lad os se resultatet af det ovennævnte eksempel med tabelstørrelse 3 og den simple funktion h(x) = x mod 3.

Figur 2: Simpelt eksempel fortsat, med n = 3 hvor S = {2, 6, 19} og h(x) = x mod 3.
\begin{figure}\begin{tabular}{\vert c\vert c\vert c\vert} \hline h(6)=0 & h(19)=1 & h(2) = 2\\ \hline \end{tabular}\centering\end{figure}
Så hvis man afslutter sin funktion med at tage modulo med tabelstørrelsen, så får man et tal mellem 0 og tabelstørrelsen, og kan derfor indeksere. Udover dette viser ovennævnte exempel at modulo også hjælper med at sprede funktionsværdierne.

Generalt behøves man ikke lade tabellen have n indgange. Oftest vil man lave den lidt større såldes at man har lettere ved at lave en funktion der spreder nøglerne pænt udover tabellen. Det er også lovligt at lave en funktion der sender flere nøgler over i samme tabelindgang, men så skal essentielt løse samme problem på denne mindre mængde.

Generelt eksempel

Figur 3: Simpelt eksempel fortsat, med n = 3 hvor S = {53, 145, 233} og h(x)= (5*x) mod 6.

Som man kan se her, er der to nøgler der sendes til den samme værdi. Et mål for hvor godt en funktion virker er det maximale antal nøgler der sendes til samme værdi, og dette mål bliver brugt her.

Opgaven går i sin simpelthen ud på, at man er givet en mængde S og en tabelstørrelse, og så handler det om at designe en funktion der sender færrest mulige værdier til den samme tabel indgang.

Til dette formål er der lavet en applet, hvis funktionalitet vil blive beskrevet i det følgende.

Forklaring af Brugergrænseflade

Figur 4: Udseende af applet når den startes
\includegraphics[width=14cm, height=10cm]{Images/StartApplet.eps}

På dette 4 kan man se hvordan appleten ser ud. Den er nærmest selvforklarende, men vi gennemgår den lige kort alligevel Øverst ses den mængde der skal bruges til at indeksere. Det vil sige den mængde der skal mappes ind i en lille tabel. Under dette felt kommer hash funktionen h(x) som man så kan ændre på. Under det kan man så en grafisk præsentation af tabellen, som bruges til at vise hvad der sker hvis man bruger den nuværende hash-funktion. I bunden er der knapper og et beskedfelt.

Hash Funktion

Til hash funktionen kan i bruge følgende operatorer.
Figur 5: Operatorer der kan benyttes til hash funktioner
\begin{figure}\par \begin{tabular}{\vert c\vert c\vert} \hline $+$\ & addition... ...line $\%$\ & modulo\\ \hline \end{tabular}\centering \par\par \end{figure}

Alle hash-funktioner vil slutte af med at tage den beregnede værdi, og tage modulo med tabelstørrelsen, så funktionen altid giver et resultat der passer med tabelstørrelsen. Udover det gælder der at for operatorerne, at + og - binder mindst, og %, *, og / binder mest. Det vil sige at

2 + 3*5 = 2 + (3*5) = 17

Hvis man ønsker

(2+3)*5 = 25

bruges paranteser som ovenover. Den eneste variabel man kan bruge er x. Så den simple hash-funktion som skrevet tidligere vil have udseendet.

x % 3


Evaluate

Knappen evaluate bruges til at evaluere den indtastede hash-funktion på mængden vist i toppen. Resultatet vises i den store tabel i midten hvor hvert element fra mængden i toppen bliver indsat i listen for den værdi den hasher til. Et eksempel på dette kan ses på figur 6. Som det kan ses farves en af tabelindgangene med rød. Det er den værdi som flest værdier bliver hashet til.

Figur 6: Evaluer hash-funktion
\includegraphics[width=14cm,height=10cm]{Images/Evaluate.eps}


Upload

For at man indbyrdes kan sammenligne hvor god en løsning man har fundet til problemet er der mulighed for at uploade resultatet til en high-score liste. Denne high-score eksisterer for 3 forskellige instanser af problemet. Der sammenlignes efter hvor mange elementer der maximalt indsættes i en tabel indgang.


Applet

Bare følg link for at starte applet.

Links til High-Score