\documentclass[a4paper,11pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage[swedish]{babel}
\usepackage{a4dutch}

\lhead{Informationsteknologi \\
       Tom Smedsaas}
\chead{}
\rhead{\today}

\setlength{\fboxrule}{1pt}
\usepackage{parskip}

\begin{document}
\selectlanguage{swedish}
\thispagestyle{fancy}
\vspace*{-2\baselineskip}
\section*{Hashmetoder}
Detta papper beskriver så kallade hashtabeller. 
Det innehåller också en beskrivning av 
\textit{ordnad hashning} som är en metod att förbättra prestanda vid
misslyckade sökningar.

\subsection*{Inledning}
%
Hashtabeller är en implementation av en abstrakt datatyp som lagrar
poster med unika \textit{nycklar} och som stöder operationer för
\textit{sökning}, \textit{inläggning} och, ofta också, \textit{uttag}.

\begin{center}
\fbox{%
\begin{tabular}{l|c|c}

               & \multicolumn{2}{|c}{Tidskomplexitet för} \\[2pt]
                 \cline{2-3}
Struktur       &                                         & \textit{inlägg} \\
               &  \raisebox{1.5ex}[0pt]{\textit{sökning}} & (när platsen känd) \\
\hline

länkad lista   & $\Theta(n)$       & $\mathrm{O}(1)$ \\
sorterad array & $\Theta(\log n)$  & $\Theta(n)$ \\
binärt sökträd & $\Theta(\log n)$  & $\mathrm{O}(1)$ \\
hashtabell     & $\mathrm{O}(1)$   & $\mathrm{O}(1)$ \\

\end{tabular}}
\end{center}

\vspace*{\baselineskip}
I hashtabeller kan man således söka, lägga in och ta bort poster med konstant tid
\textit{oavsett hur många poster som är lagrade i tabellen}!

Man kan bevisa att det, i genomsnitt, krävs $\Omega(\log n)$ operationer
att lokalisera en given nyckel bland $n$ om den enda tillåtna
operationerna på nycklarna är storleksjämförelser. Med den begränsningen
kan man säga att binärsökning i array och sökning i binärt (balanserat) sökträd
är optimala -- det går helt enkelt inte att göra bättre.

Knepet för att komma vidare är att använda nyckeln för att bättre förutsäga 
platsen. Om man t.ex. har en array med 500 sorterade heltal mellan 200 och 1000 och
letar efter 220 så är det dumt att, som i binärsökning, börja att titta i mitten.
Genom att i stället använda interpolationen
\begin{equation*}
  \frac{220 - 200}{1000-200} \cdot 500 = 12
\end{equation*}
som startpunkt kommer man förmodligen mycket närmare. Detta kan upprepas och
leder fram till en metod som brukar kallas \textit{interpolationssökning}
och som tar $\mathrm{O}(\log\log n)$ operationer. För alla praktiska ändamål kan
detta betraktas som konstant. Tyvärr så kräver fortfarande 
inlägg $\Theta(n)$ operationer
vilket gör att denna metod inte passar för mer dynamiska mängder.

\subsection*{Direktadressering}
%
Vid interpolationssökning använder man ett sätt att lägga in nycklar (stoppas in
i storleksordning) och ett annat att söka (beräkna plats med en interpolation).
Man kan använda samma metod för att beräkna plats vid lagring som vid sökning.
I ovanstående exempel med de 500 heltalen i intervallet $[200,1000]$ skulle man
kunna använda en array $A[801]$ och lagra nyckel $k$ på plats $k-200$. Varje
nyckel får på detta sätt en unik plats. I själva verket behöver vi ej ens lagra nyckeln --
bara information om att den finns med. Det räcker alltså med en array med logiska
värden.
Om värdet på plats $k$ är $true$ så finns nyckel $k+200$ med, annars ej.
I denna metod krävers således sökning, lagring och borttagning endast en
subtraktion eller addition samt en kopiering av värdet. Tyvärr så
förutsätter den att varje \textit{möjlig} nyckel får en egen, unik adress vilket betyder
att tabellen som krävs blir orimligt stor i de flesta tillämpningar. (Antag
t.ex. att nycklarna är variabelnamn i ett programmeringsspråk. Hur många
möjliga namn finns det?)


\subsection*{Hashtabeller}
%
För att försöka hålla kvar effektiviteten i direktadressering men få
en tabell som dimensioneras efter \textit{förväntat} i
stället för \textit{möjligt} antal nycklar, släpper man kravet på att varje nyckel
skall garanteras en egen plats.

Precis som vid direktadressering används en array $T$ med $m$ platser
samt en funktion $h(k)$ som avbildar mängden nycklar på intervallet
$[0,m-1]$.
Arrayen $T$ kallas \textit{hashtabell} och funktionen $h$ \textit{hashfunktion}.
Tabellstorleken $m$ väljes efter förväntat antal nycklar. Det värde (den adress)
som en nyckel får av hashfunktionen $h$ kallas dess 
\textit{hashadress} eller \textit{hashkod}.

Två väsentliga frågor finns: hur skall hashfunktionen se ut och hur skall
man göra om två olika nycklar får samma plats?

\begin{sloppypar}
Tills vidare antar vi att nycklarna är heltal. Som hashfunktion $h$
kan vi då använda modulofunktionen
\begin{equation*}
  h(k) = k \bmod m
\end{equation*}
Modulo-operationen garanterar ju att funktionsvärdet kommer i intervallet 
\mbox{$[0,m-1]$}.
\end{sloppypar}

Om två olika nycklar $k_1$ och $k_2$ får samma plats så kallas detta för en 
\textit{kollision}. Det finns två huvudprinciper för att hantera kollisioner:

\begin{enumerate}
\item 
  Element med samma hashadress länkas samman i en linjär lista. Vanligen låter
  man då hashtabellen $T$ innehålla pekare till listelement. Detta kallas
  \textit{länkad kollisionshantering}.
\item
  Välj en annan plats i samma tabell enligt någon algoritm. Olika algoritmer
  ger olika bra resultat.
  Detta kallas (ofta) för \textit{öppen adressering}.
\end{enumerate}

\subsubsection*{Länkad kollisionshantering}

Antag att nycklarna 14, 15, 5, 7, 90, 23 och 9 skall läggas in
i en hashtabell med 5 platser ($m=5$) och med länkad kollisionshantering.

\begin{center}
\begin{tabular}{lccccccc}
$k$    & 14 & 15 & 5 & 7 & 90 & 23 & 9\\
$h(k)$ & 4  &  0 & 0 & 2 &  3 &  3 & 4
\end{tabular}
\end{center}

\setlength{\unitlength}{1cm}
\begin{picture}(12,6)
  \put(1,4.5){\framebox(1,1){}} \put(2,5){\vector(1,0){1.5}}
  \put(1,3.5){\framebox(1,1){}}
  \put(1,2.5){\framebox(1,1){}} \put(2,3){\vector(1,0){1.5}}
  \put(1,1.5){\framebox(1,1){}} \put(2,2){\vector(1,0){1.5}}
  \put(1,0.5){\framebox(1,1){}} \put(2,1){\vector(1,0){1.5}}

  \put(0.5,4.9){0}
  \put(0.5,3.9){1}
  \put(0.5,2.9){2}
  \put(0.5,1.9){3}
  \put(0.5,0.9){4}

  \put(3.5,4.7){\framebox(1.5,0.6){15}} \put(5,5){\vector(1,0){1.5}}
  \put(6.5,4.7){\framebox(1.5,0.6){5}}  \put(8,5){\vector(1,0){1.5}}
  \put(9.5,4.7){\framebox(1.5,0.6){90}}

  \put(3.5,2.7){\framebox(1.5,0.6){7}}

  \put(3.5,1.7){\framebox(1.5,0.6){23}}

  \put(3.5,0.7){\framebox(1.5,0.6){14}} \put(5,1){\vector(1,0){1.5}}
  \put(6.5,0.7){\framebox(1.5,0.6){9}}

\end{picture}

Om vi antar att varje inlagd nyckel är lika sannolik att bli eftersökt
så kräver en lyckad sökning i denna tabell
\begin{equation}
s = \frac{4\cdot 1 + 2\cdot 2 + 1\cdot 3  }{7} = \frac{11}{7} = 1.57
\end{equation}
i genomsnitt.

Om vi inför en misslyckad sökning antar att varje lista är lika
sannolik att bli genomsökt så kräver en misslyckad sökning
\begin{equation}
  u = \frac{4 + 1 + 2 + 2 + 3}{5} = \frac{12}{5} = 2.4
\end{equation}
i genomsnitt (att leta i en tom lista kräver ett försök -- för att upptäcka
att listan är tom)

\subsubsection*{Analys av länkad kollisionshantering}
%
För att analysera hashmetoder antar vi att en given nyckel har lika stor
sannolikhet att hamna på var och en av de $m$ platserna.

Om $n$ nycklar lagrats så är de $m$ listorna i genomsnitt $n/m$ långa.
För att upptäcka att en given nyckel \textit{inte} finns 
(s.k. \textit{misslyckad} sökning) så krävs då i genomsnitt 
\begin{equation}
  u(n,m) = 1+n/m 
\end{equation}
försök (att leta i en tom lista kräver, som sagt, ett försök).

Sökning av nyckel som finns (\textit{lyckad} sökning) är något svårare att
analysera eftersom genomsnittet skall bildas över de $n$ nycklarna - inte
över antalet tabellplatser. Antagandet är att varje nyckel söks med lika stor
sannolikhet. Vi kan här använda samma observation som vid analys av binära 
sökträd: \textit{det krävs lika många försök att finna en existerande nyckel
som det krävdes för att lägga in den nyckeln} vilket är samma som 
\textit{antalet försök som krävdes för att söka den nyckeln innan den var
inlagd}.

Sålunda är det genomsnittliga arbetet att söka en existerande nyckel lika stort
som arbetet för att bygga upp tabellen
\begin{eqnarray}
  s(n,m) & = & \frac{1}{n} \left((1 + \frac{0}{m}) + (1 + \frac{1}{m}) + (1 + \frac{2}{m}) + 
             \cdots + (1 + \frac{n-1}{m}) \right) \nonumber\\
         & = & \frac{1}{n}\left(n +\frac{1}{m}\sum_{i=0}^{n-1}{i}\right) \nonumber\\
         & = & 1 + \frac{n(n-1)}{2mn} \nonumber\\
         & = & 1 + \frac{n-1}{2m} =  
               1 + \frac{\alpha}{2} - \frac{1}{2m} 
                   \approx 1 + \frac{\alpha}{2}
\end{eqnarray}
där $\alpha = n/m$ är tabellens \textit{fyllnadsgrad}.

\subsubsection*{Öppen kollisionshantering}
%
Alla nycklar (poster) i tabellen. Om en kollision uppstår provar man en annan plats.
En enkel men ganska dålig metod är följande som brukar kallas \textit{linjär}
kollisionshantering:

\textbf{Algoritm:} Linjär kollisionshantering
\begin{tabbing}
\hspace*{1cm}\=\hspace*{1cm}\=\hspace*{1cm}\=\hspace*{1cm}\=\hspace*{1cm}\= \kill
 Hash-insert( k, T ) \\
   \> i $\leftarrow$ h(k) \\
   \> \textbf{while} T[i]$\neq$\textbf{nil} \textbf{do} \\
   \>   \>i $\leftarrow$ (i+1) \textbf{mod} m \\
   \> T[i] $\leftarrow$ k
\end{tabbing}
(En verklig implementation måste också hantera fallet att tabellen redan är full)

\textbf{Exempel}

Antag att vi har en tabell med $m=11$ platser och använder hashfunktionen
$h(k) = k \bmod m$ samt att vi har följande nycklar:
\begin{center}
\begin{tabular}{lccccccccc}
  Nycklar $k$ & 14 & 7 & 96 & 6 & 412 & 3 & 16 & 25 & 22 \\
  $h(k)$      &  3 & 7 &  8 & 6 &   5 & 3 &  5 &  3 & 0  
\end{tabular}
\end{center}
Om dessa läggas in i tabellen med algoritmen ovan erhålles följande tabell
\begin{center}
\begin{tabular}{lrrrrrrrrrrr}
  Index        & 0  &  1 &  2 &  3 & 4 &  5 &  6 &  7 &  8 &  9 & 10 \\
  Innehåll     & 22 &    &    & 14 & 3 &412 &  6 &  7 & 96 & 16 & 25 \\[0.8ex]
  Antal försök & 1  &    &    &  1 & 2 &  1 &  1 &  1 &  1 &  5 &  8 
\end{tabular}
\end{center}
Totala antalet försök vid uppbyggnaden är 21 vilket innebär att
sökning lyckad sökning i tabellen kräver $21/9 \approx 2.2$ försök. 

Problemet med den linjära metoden är att de nycklar som en gång kolliderat
kommer att använda samma strategi för att hitta en ledig plats dvs de
kommer att fortsätta att kollidera med varandra. Detta gör att de bildas
klumpar (s.k. kluster) med kolliderande nycklar. 
För att motverka detta kan man använda olika sätt att välja nästa plats
för olika nycklar.
Boken tar upp kvadratisk kollisionshantering men det finns egentligen
ingenting som talar för denna. En mycket bra metod är däremot
så kallad \textit{dubbel hashning}. Idén är att i stället
för att man vid kollision provar nästa, tar ett steg framåt där stegets längd
beror på nyckeln via en ny funktion $g(k)$.

\textbf{Algoritm:} Dubbelhashning
\begin{tabbing}
\hspace*{1cm}\=\hspace*{1cm}\=\hspace*{1cm}\=\hspace*{1cm}\=\hspace*{1cm}\= \kill
 Hash-insert( k, T ) \\
   \> i $\leftarrow$ h(k) \\
   \> \textbf{while} T[i]$\neq$\textbf{nil} \textbf{do} \\
   \>   \>i $\leftarrow$ (i+g(k)) \textbf{mod} m \\
   \> T[i] $\leftarrow$ k 
\end{tabbing}
(En verklig implementation måste också hantera fallet att tabellen redan är full)

Samma metod används naturligtvis för sökning.

\textbf{Exempel}
\begin{center}
\begin{tabular}{lccccccccc}
  $k$     & 14 & 7 & 96 & 6 & 412 & 3 & 16 & 25 & 22 \\
  $h(k) = k \bmod 11$  &  3 & 7 &  8 & 6 &   5 & 3 &  5 &  3 & 0   \\
  $g(k) = (k \bmod 9) + 1$  &  6 & 8 &  7 & 7 &   8 & 4 &  8 &  8 & 5   
\end{tabular}
\end{center}
Om dessa läggas in i tabellen med algoritmen ovan erhålles följande tabell
\begin{center}
\begin{tabular}{lrrrrrrrrrrr}
  Index        & 0  &  1 &  2 &  3 & 4 &  5 &  6 &  7 &  8 &  9 & 10 \\
  Innehåll     & 3  &    & 16 & 14 &22 &412 &  6 &  7 & 96 &    & 25 \\[0.8ex]
  Antal försök & 3  &    &  2 &  1 & 4 &  1 &  1 &  1 &  1 &    &  6 
\end{tabular}
\end{center}
Totala antalet försök vid uppbyggnaden är 21 vilket innebär att
sökning lyckad sökning i tabellen kräver $20/9 \approx 2.0$ försök. 
(Det här exemplet gör inte metoden riktig rättvisa)

Är man säker på att alla platser besöks? 
Ja, om steget $g(k)$ och tabellstorleken $m$ inte har några gemensamma primfaktorer
vilket enklast garanteras genom att välja $m$ till ett \textit{primtal}.

Hur skall man välja $g(k)$?
Vettiga steg är tal i intervallet $[1,m-1]$. En vanlig rekommendation är
att använda $g(k) = (k \bmod m-2) + 1$ som skall vara speciellt bra om
förutom $m$, även $m-2$, är ett primtal (s.k. \textit{primtalstvillingar}).

\subsubsection*{Likformig hashning - en idealiserad modell}
%
Likformig hashning (eng. \textit{uniform hashing}) är en modell för en
idealiserad öppen hashmetod som vi använder för att analysera metoden.

När vi söker eller lagrar en nyckel provar vi en följd av olika adresser.
Vi bygger analysen på följande antagande:

\textit{Vid varje försök har var och en av de oprövade platserna lika stor 
chans att bli vald.}

Det förväntade antalet försök vid en misslyckad sökning är
%
\begin{eqnarray*}
  u(m,n) & = &\sum_{c>0}{c Pr(c \mbox{ försök})} \\
         & = &\sum_{c\ge 1}Pr(c \mbox{ försök}) + 
              \sum_{c\ge 2}Pr(c \mbox{ försök}) +
              \sum_{c\ge 3}Pr(c \mbox{ försök}) + \cdots \\
         & = & Pr( \ge 1 \mbox{ försök} ) + 
               Pr( \ge  2 \mbox{ försök} ) + Pr( \ge 3 \mbox{ försök} ) + \cdots \\
         & = & \sum_{c\ge 1}Pr(\ge c \mbox{ försök})
\end{eqnarray*}
%
För att det skall bli minst $c$ försök måste det bli kollision i 
de $c-1$ första försöken
%
\begin{equation*}
  Pr( \ge c \mbox{ försök}) = \frac{n}{m} \cdot \frac{n-1}{m-1} 
                              \cdot \dots \cdot \frac{n-(c-2)}{m-(c-2)}  \approx 
                                \left(\frac{n}{m}\right)^{c-1}
\end{equation*}
%
Detta ger
%
\begin{equation*}
  u(n,m) = \sum_{c \ge 1}\left(\frac{n}{m}\right)^{c-1} =
  \sum_{c \ge 0}\left(\frac{n}{m}\right)^{c} =
           \frac{1}{1-\frac{n}{m}}
\end{equation*}

Eftersom en sökning efter ett existerande element kräver lika många försök som det
tog att lägga in det elementet vilket är tar lika lång tid som att söka elementet
innan det är inlagt så blir antalet försök vid lyckas sökning
%
\begin{equation*}
  s(n,m) = \frac{1}{n} \sum_{i=0}^{n-1}{\frac{1}{1 - \frac{i}{m}}} = 
           \frac{m}{n} \sum_{i=0}^{n-1}{\frac{1}{m - i}}
\end{equation*}
%
Summan, som ju är besläktad med den harmoniska summan, kan approximeras med
en integral:
%
\begin{equation*}
\sum_{i=0}^{n-1}{\frac{1}{m - i}} \approx  
\int_0^n\frac{dx}{m-x} = \ln \frac{m}{m-n}
\end{equation*}
vilket ger
\begin{equation}
s(\alpha) = s(m,n) = \frac{m}{n} \ln\left(\frac{m}{m-n}\right) = 
           \frac{1}{\alpha} \ln\left(\frac{1}{1-\alpha}\right)
\end{equation}
där $\alpha=n/m$ är tabellens fyllnadsgrad. Dessa funktioners
värden är tabulerade nedan. Sista raden i tabellen innehåller
de exakta värdena för $n=100$. Denna visar att approximationer
ger en liten överskattning av antalet erforderliga försök.
{\small
\begin{center}
\fbox{%
\begin{tabular}{r|rrrrr|rrrrr}
Metod &\multicolumn{5}{l}{Lyckad sökning} & \multicolumn{5}{|l}{Misslyckad sökning}\\
\hline
Fyllnadsgrad      & 50 & 75 & 85 & 90 & 95 & 50 & 75 & 85 & 90 & 95 \\
\hline
Linjär            & 1.5 & 2.5 &  3.8  &  5.5 &  10.5 &
                    2.5 & 8.5 & 22.7  & 50.5 & 200.5 \\
Dubbelhashning    & 1.4 & 1.9 &  2.2  &  2.6 &   3.2 & 
                    2.0 & 4.0 &  6.7  & 10.0 &  20.0 \\
Exakt för $m=100$ & 1.4 & 1.9 &  2.1  &  2.4 &   2.9 &
                    2.0 & 3.9 &  6.3  &  9.2 &  16.8 \\
\end{tabular}}
\end{center}
}

\subsubsection*{Ordnad hashning}
%
Som framgår av tabellen ovan så kräver misslyckad sökning betydligt fler
försök än lyckad när fyllnadsgraden börjar bli stor. Den finns en enkel metod
att råda bot på detta som brukar kallas \textit{ordnad hashning}.

Vi utgår från dubbelhashning (även om man det går lika bra att använda vilken
öppen metod som helst) och modifierar sökalgoritmen något:

\textbf{Algoritm:} Sökning i ordnad tabell
\begin{tabbing}
\hspace*{1cm}\=\hspace*{1cm}\=\hspace*{1cm}\=\hspace*{1cm}\=\hspace*{1cm}\= \kill
 Hash-search( k, T ) \\
   \> i $\leftarrow$ h(k) \\
   \> \textbf{while} k < T[i] \textbf{do} \\
   \>   \>i $\leftarrow$ (i+g(k)) \textbf{mod} m \\
   \> \textbf{if} $T(i)=k$ \>\> \textbf{then} \textit{lyckad} \\
   \>                      \>\> \textbf{else} \textit{misslyckad} 
\end{tabbing}
%
Vi har alltså ändrat iterationsvillkoret; iterationen avbryts när det lagrade är
mindre än eller lika med den sökta nycken.
För att detta skall fungera måste dock tabellen byggas upp på ett särskilt sätt.

Antag att vi använder den vanliga inläggningsalgoritmen men lägger in nycklarna i
storleksordning med den största först.
Då kommer sökalgoritmen ovan att fungera eftersom vi provar exakt samma platser
vid sökning som vid inlägg och allt som lades in före $k$ var större än $k$.

Detta är naturligtvis inget realistiskt sätt att fylla tabellen i de flesta
tillämpningar men man kan få samma effekt med följande algoritm:

\textbf{Algoritm:} Inlägg i ordnad tabell
\begin{tabbing}
\hspace*{1cm}\=\hspace*{1cm}\=\hspace*{1cm}\=\hspace*{1cm}\=\hspace*{1cm}\= \kill
 Hash-insert( $k$, $T$ ) \\
   \> $i \leftarrow h(k)$ \\
   \> \textbf{while} $T[i] \neq$ \textbf{nil} \textbf{do} \\
   \>   \> \textbf{if} $T[i] < k$ \textbf{then} swap( $k$, $T[i]$ ) \\
   \>   \>$ i \leftarrow (i+g(k))$ \textbf{mod} $m$ \\
   \> $T[i] \leftarrow k$ 
\end{tabbing}

(En implementation måste också hantera fallen att nyckeln redan finns och att 
tabellen är full)

Om tabellen är ordnad så gäller att när vi söker efter en nyckel $k$
så passerar vi bara nycklar som är större än $k$. Ovanstående inläggningsalgoritm
minskar aldrig en nyckel på en plats.

Den slutliga ordningen är oberoede av inläggningsordning!

Förväntat antal försök vid inlägg och lyckad sökning är oförändrat men
för misslyckad sökning väsentligt förbättrad:
\begin{equation*}
  u(m,n) = s(m,n+1)
\end{equation*}

{\small
\begin{center}
\fbox{%
\begin{tabular}{r|rrrrr|rrrrr}
Metod &\multicolumn{5}{l}{Lyckad sökning} & \multicolumn{5}{|l}{Misslyckad sökning}\\
\hline
Fyllnadsgrad    & 50 & 75 & 85 & 90 & 95 & 50 & 75 & 85 & 90 & 95 \\
\hline
Linjär          & 1.5 & 2.5 &  3.8  &  5.5 &  10.5 &
                  2.5 & 8.5 & 22.7  & 50.5 & 200.5 \\
Dubbelhashning & 1.4 & 1.9 &  2.2  &  2.6 &   3.2 & 
                  2.0 & 4.0 &  6.7  & 10.0 &  20.0 \\
Ordnad hashning  & 1.4 & 1.9 &  2.2  &  2.6 &   3.2 & 
                  1.4 & 1.9 &  2.2  &  2.6 &   3.2 \\
\end{tabular}}
\end{center}
}

\subsubsection*{Hashfunktioner}
%
Funktionen
\begin{equation*}
  h(k) = k \bmod m
\end{equation*}
som vi genomgående har använt i exemplen är inte alls dålig under 
förutsättning att $m$ är ett primtal. Om $m$ inte är ett primtal blir
funktionen mer känslig för systematik i nycklarna.

En mer generell funktion är
\begin{equation*}
  h(k) = ((c_1 k + c_2) \bmod p) \bmod m
\end{equation*}
där $p > m$ är ett stort primtal, $p>2^{20}$ (t. ex. $p=1048583$, 
$c_1$ ett positivt heltal mindre än $p$
och $c_2$ ett icke-negativt heltal mindre än $p$.
Konstanten $c_2$ väljs ofta till 0.
Olika $c_1$ ger helt olika hashfunktioner!

Om nyckeln är en sträng $s_1 s_2 s_3 \cdots s_k$
så beräkna ett tal t.ex. genom
\begin{equation*}
  (((s_1\cdot 37 + s_2)\cdot 37 + s_3) + \cdots ) + s_k 
\end{equation*}
och använder sedan någon av ovanstående hashfunktioner.

Det finns mer avancerade hashfunktioner som kan sprida även mycket ojämnt
fördelade nycklar jämnt. Ofta bygger dessa på någon form av bitvis
xor-operation med slumptal.

\end{document}

