# 4 Hashing

[TOC]

[comment]: # (Zuerst ein paar LaTeX-Makros:)

$\newcommand{\N}{\mathbb{N}}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\ra}{\rightarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\O}{\mathcal{O}}
\newcommand{\norm}[1]{\left| #1 \right|}$

*Disclaimer:* Diese Mitschrift ist als Ergänzung zur Vorlesung gedacht. Wir erheben keinen Anspruch auf Vollständigkeit und Korrektheit. Wir sind jederzeit froh um Hinweise zu Fehlern oder Unklarheiten an [e-mail].

Wenn Sie an dieser Mitschrift mitarbeiten möchten, melden Sie sich [hier](http://doodle.com/poll/hkiky233kxp7rr8n).

> **Hinweis**: Zum Thema Hashing gibt es eine separates, detailliertes Dokument auf der Vorlesungshomepage. Diese Mitschrift hier entspricht daher nicht genau der Vorlesung vom 4. März.

## Einleitung

Wir haben gestern gesehen wie schnell wir nach einem Schlüssel in einer Menge von Schlüsseln suchen können: In unsortierten Arrays in $\O(n)$ mit linearer Suche
und in sortierten Arrays in $\O(\log n)$ mit binärer Suche.

Kann es schneller gehen, wenn wir mit den Schlüsseln rechnen können und nicht nur Vergleiche machen können? Zum Beispiel für eine Studentendatenbank mit Leginummern können wir uns folgendes überlgen:
Wir machen ein Array der Grösse $100'000'000$, sodass alle Leginummern der Form 15-xxx-xxx darin als Zahl Platz haben. Darin hat jeder Studi seinen eigenen Platz und wir können in $\O(1)$ nachschauen, ob es ihn gibt oder nicht.

1 15-123-456 100’000’000
|==============1=================|

Was ist das Problem? Dieser Array braucht riesig viel Platz. Als Verbesserungsidee: Nehmen wir an es gibt nicht mehr als $100'000$ Studenten an der ETH sodass wir annehmen, dass die letzten fünf Zahlen der Leginummer bereits eindeutig sind.

1 23-456 100’000
|==============1=================|

Das Problem jetzt: Diese Kennzahl muss nicht mehr zwingend eindeutig sein.

Ein weiteres Beispiel: Wir schreiben ein Stück Code in Java

void f(int n) {
	int k;
	if(n==1) {
		int k; // Compiler erzeugt Fehler,
		// da die Variable k doppelt vorkommt!
...

Wie merkt sich der Compiler welche Variablen schon definiert wurden?

Ziel der heutigen Vorlesung ist es eine Datenstruktur zu konstruieren, die folgende Operationen unterstützt:
* *INSERT(k)*, um einen neuen Schlüssel $k$ einzufügen.
* *SEARCH(k)*, liefert $1$ zurück, falls $k$ gespeichert, $0$ sonst.
* *DELETE(k)*, entfernt Schlüssel $k$.

Solche Datenstrukturen nennt man Wörterbücher. Wir können eine solche Datenstruktur beispielsweise mit einem Array oder mit einer linearen Liste implementieren.

Naive Lösungen:

| Verfahren | INSERT | SEARCH |
|---|---|---|---|---|
| unsortiertes Array | $\O(1)$ | $\O(n)$ |
| sortiertes Array | $\Omega(n)$ | $\O(\log n)$ |
| lineare Liste | $\O(1)$ | $\Omega(n)$ |

Das alles ist nicht zufriedenstellend, da wir keine Operationen in linearer Zeit wollen.

Die neue Idee ist nun einen Array zu benutzen und die Adresse des Elements (also die Position im Array) direkt aus dem Schlüssel selbst zu ermitteln.

Wir definieren dazu eine *Hashfunktion* $h: K \ra \{0,1,\dots, m-1\}$, wobei $K$ die Menge der möglichen Schlüssel bezeichnet und $\{0,1,\dots, m-1\}$ die verfügbaren Adressen im Array sind. Nun ist $h(k)$ die Adresse für Schlüssel $k$.

| 0 | 1 | 2 | ... | | | m-1 | m-1 |
|---|---|---|---|---|---|---|---|
| | | | | | | | |

Solche Verfahren, die mit dem Schlüssel rechnen, um einen kleineren Kennwert zu bekommen, heissen *Hashverfahren*.

Im Allgemeinen ist $\norm{K} \gg m$. Es gibt also viel mehr potentielle Schlüssel als Plätze im Array. Nach dem Schubfachprinzip gibt es dann zwei Schlüssel $k, k'$ mit $k \neq k'$ und $h(k) = h(k')$. Ein solches Zusammentreffen der Hashadressen nennen wir *Kollision*. Passiert sowas oft?

#### Geburtstagsparadoxon
Sind $23$ Personen in einem Raum, ist es eher wahrscheinlich, dass zwei am gleichen Tag Geburtstag haben.

$P(\text{alle an verschiedenen Tagen geboren})
= \frac{365}{365} \cdot \frac{364}{365} \cdots \frac{365-23+1}{365} < 0.5$

Bezogen auf Hashing bedeutet dies, dass es bei einer Tabelle mit 365 Einträgen und 23 eingefügten Schlüsseln bereits wahrscheinlich ist, dass es zu einer Kollision kommt.

Anforderungen an gute Hashfunktionen:
1) Die Hashfunktion sollte gut streuen, d.h. Kollisionen nach Möglichkeit vermeiden.
2) Kollisionen sollten effizient auflösbar sein.

## Hashfunktionen
Was wollen wir von solchen Hashfunktionen? Es ist unmöglich dass es keine Kollisionen gibt, denn es gibt unendlich viele Schlüssel und nur konstant viele mögliche Hashwerte. Was wir möchten, ist dass die Hashfunktion möglichst gut, also gleichmässig, über die $m$ möglichen Werte streut, also $P[h(k_1) = h(k_2)] = \frac{1}{m}$.
Ausserdem möchten wir, dass Kollisonen effizient auflösbar sind.

Zwei populäre Hashfunktionen sind diese beiden:
1) Divisionsrestmethode: $h(k) = (k\bmod m)$ mit $m$ als Primzahl
2) Multiplikative Methode: $h(k) = \lfloor m\cdot (k\cdot z-\lfloor k\cdot z\rfloor) \rfloor$ mit einer irrationalen Zahl $z$^[Zum Beispiel mit $\phi^{-1}$, als dem Inversen des goldenen Schnitts. Warum das funktioniert wird [hier](http://cstheory.stackexchange.com/questions/9639/how-did-knuth-derive-a) diskutiert.].

Im Fall der Divisionsrestmethode sollte man für $m$ eine Primzahl wählen. Würden wir $m=2^i$ für ein $i\in \N$ wählen, dann würde die Hashfunktion nur die letzten $i$ Bits von $k$ betrachten.

### Perfektes und universelles Hashing
Falls die benutzten Schlüssel $K \subseteq \mathcal{K}$ im Vorfeld bekannt sind, dann ist eine kollisionsfreie Speicherung möglich. Das nennt man *perfektes Hashing*.

In der Realität ist das aber oft nicht möglich. Zum einen sind die Schlüssel oft nicht im Vorfeld bekannt, zum anderen sind sich die Schlüssel in $K$ oft sehr ähnlich.

Für eine einzelne, fixe Hashfunktion können wir das unmöglich erreichen, denn wir können als „böser Gegner“ immer stets Kollisionen finden und nur solche Schlüssel abfragen. Aber wenn die Hashfunktion dem Eingaben-Ersteller nicht bekannt sind, weil wir sie zufällig aus einer grossen Menge an Hashfunktionen auswählen, kann es funktionieren.

Sei $\mathcal{H}$ eine solche Familie von Hashfunktionen mit dieser Eigenschaft $$\norm{\{h \mid h \in \chi, h(k_1) = h(k_2)\}} \leq \frac{1}{m} \norm{\mathcal{H}}.$$
$\mathcal{H}$ ist also eine Familie von Hashfunktionen mit der Eigenschaft dass immer nur ein $m$-tel aller Funktionen zu einer Kollision führen. Man nennt dies *universelles Hashing*.

Eine zufällig gewählte Funktion aus $\mathcal{H}$ verteilt eine *beliebige* Menge von Schlüsseln im Erwartungswert so gleichmässig wie möglich über den Array. Den Beweis dazu finden Sie in den Vorlesungsnotizen auf der Webseite der Vorlesung.

Universelle Hashklassen sind also nützlich, doch bis jetzt haben wir noch keine gesehen. Nun ein Beispiel einer solchen universellen Hash-Familie: Sei $p$ eine Primzahl und $K = \{0, \dots, p-1\}$. Wir wählen $a$ und $b$ zufällig mit $1\leq a,b \leq p-1$ und bilden mit $a$ und $b$ eine affine Abbildung des Schlüssels vor dem Hashing, also
$$h_{a,b}(k) = ((a \cdot k+b)\bmod p) \bmod m$$

Zu zeigen, dass diese Familie eine universelle Hashfunktion ist, ist nicht ganz einfach, aber sie gibt uns ein sehr einfach zu implementierendes Verfahren. Universelle Hashklassen existieren also und sind leicht zu berechnen.

## Kollisionsauflösung

Was zu klären bleibt: Wie behandeln wir die Fälle, wenn mehrere Schlüssel den selben Hashwert haben?

### Direkte Verkettung
Die einfachste Variante ist es, in jeder der $m$ Positionen eine lineare Liste aller Schlüssel mit dieser Hashadresse zu speichern und einfach alle Schlüssel darin zu *verketten* (engl. chaining).

0 i m-1
[ [k] ]
|
[k’]
|
[k’’]

In der Hashtabelle speichern wir also nicht nur ein Ja/Nein, um uns zu merken ob der Platz belegt ist, sondern wir speichern eine Liste mit den gesamten Schlüsseln.

Ein Beispiel: Sei $m=7$ und $K = \{12,53,5,15,2,19
,43\}$.


Wir speichern die Zahlen, die laut unserer Hashfunktion an der gleichen Stellen liegen sollen, in einer verketteten Liste.

- *Search(x)*: Durchlauf in der bei $h(x)$ gespeicherten Liste. Falls $x$ darin nicht gefunden wird, dann ist $x$ nicht in der Tabelle.

- *Insert(x)*: Wir prüfen ob, $x$ bereits vorhanden ist. Falls nicht, fügen wir $x$ am Ende der in $h(x)$ gespeicherte Liste an.

- *Delete(x)*: Wir prüfen ob, $x$ überhaupt vorhanden ist. Falls ja, entfernen wir $x$ aus der in $h(x)$ gespeicherten Liste.

Falls die Datensätze die wir in der Hashtabelle speichern wollen gross sind, macht es wenig Sinn $m$ leere Plätze dieser Grösse vorrätig zu halten. Dann kann man im Array einfach Zeiger speichern, die zuerst alle leer sind. Sobald wir dann was einfügen, ändern wir einfach den Zeiger und speichern den gesamten Datensatz sonstwo im Speicher.

Eine solche Hashtabelle unterstützt die Operationen des abstrakten Datentyps *Wörterbuch*. Man kann also Schlüssel Suchen, Einfügen und Entfernen. Wie schnell ist eine solche Implementierung mit einer Hashtabelle für
$n$ Schlüssel und $m$ Plätze?

#### Laufzeitanalyse

Analysieren wir die mittlere Zeit für eine erfolgreiche und eine erfolglose Suche.

**Für eine erfolgreiche Suche**
Bei einer erfolglosen Suche nach $x$ müssen wir die ganze Liste an der Stelle $h(x)$ durchschauen und die durchschnittliche Listenlänge ist $\alpha := \frac{n}{m}$.

Dieses $\alpha$ nennt man auch Belegungsfaktor, also wie dicht die Speicherzellen des Arrays gefüllt sind. Wenn wir $m$ in der selben Grössenordnung von $n$ wählen, so können wir also *im Mittel* eine konstante Suchzeit erreichen.

Im schlimmsten Fall, kann die Laufzeit aber immer noch $n$ sein, dann nämlich wenn alle Schlüssel bei einem einzigen Hashwert verkettet sind.

**Für eine erfolgreiche Suche**
Wie weit müssen wir im Mittel in der Schlüsselliste suchen, bis wir den Schlüssel finden? Einfach die Hälfte der Listen?

Schauen wir uns die Schlüssel in der Reihenfolge an in der sie eingefügt wurden. Denn wen wir nach dem Schlüssel suchen der als $j$-ter eingefügt wurde, dann spielen nur die Schlüssel eine Rolle, die damals schon dort waren, also nur die $j-1$ ersten Schlüssel. Die durchschnittliche Kettenlänge damals war $\frac{j-1}{m}$, also ist die durchschnittliche Suchtiefe am Ende:

$$\frac{1}{n}\sum_{j=1}^n\left(\frac{j-1}{m}+1\right) = 1 + \frac{1}{m}\left((n-1)\frac{n}{2}\right) \frac{1}{n} < 1 + \frac{\alpha}{2}$$

Unsere Intuition, dass wir im Mittel etwa die halbe Liste pro Platz ablaufen ist also korrekt. Ein Vergleich kommt einfach noch hinzu, da wir mit dem neuesten Element oder einem leeren Platz vergleichen müssen.

Der Worst Case ist natürlich auch hier immer noch $n$ Vergleiche.

Was sind die Vor- und Nachteile dieser Methode?
**Vorteile**
- Ein Belegungsfaktor $> 1$ ist problemlos möglich.
- Das Entfernen von Schlüsseln ist unkompliziert und ohne negative Konsequenzen möglich.

**Nachteile**
- Für die Listen ist Extraplatz ausserhalb des Arrays erforderlich.

### Kollisionsauflösung direkt im Array
Wir verzichten nun auf die verlinkten Listen pro Speicherplatz. Solche Hashverfahren, die bei Kollisionen direkt im Array nach freien Plätzen suchen, nennt man *offenes Hashverfahren* (vom englischen open addressing).

Wie suchen wir nach solchen freien Plätzen? Suchen wir einfach nach links oder nach rechts oder springen wir wild umher? Die Reihenfolge wie wir nach solchen freien Plätzen suchen nennt man *Sondierungsfolge*.

Eine Sondierungsfunktion $s(j,k)$, soll so gewählt sein, dass $(h(k) - s(j,k))\bmod m$ für $j=0,\dots,m-1$ eine Permutation aller Hashadressen darstellt, das heisst, dass wir beim Sondieren alle möglichen Adressen abklappern.

##### Lineares Sondieren
Suchen wir einfach nach links, also ans Adresse $h(k), h(k)-1, h(k)-2,...$ nennt man dies *lineares Sondieren* mit $s(j,k) = j$.

SEARCH(x)
	i := h(x) - s(0,x)
	j := 0
	while T[i] nicht frei und j < n do
		if T[i] = x:
			return "x gefunden"
		else 
			j := j + 1
			i := h(x) - s(j,x)
	return "nicht gefunden"

Beispiel: $m = 7$, $h(k) = (k \bmod 7)$ und $k=\{12, 53, 5, 15, 2, 19,43\}$ ergibt

| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|----|----|---|---|----|----|----|
| 19 | 15 | 2 | 5 | 53 | 12 | 43 |

Wie gut funktioniert dieses Sondieren? Man kann folgende mittleren Laufzeiten fürs lineare Sondieren zeigen: $\frac {1}{2} \cdot \left( 1 + \frac{1}{(1-\alpha)^2}\right)$ Vergleiche im erfolglosen Fall und $\frac{1}{2} \cdot \left(1 + \frac{1}{1-\alpha} \right)$ Schritte im erfolgreichen Fall.

Als Beispiel: Bei einem Belegungsfaktor von $\alpha = 0.95$ ist $C_n' > 200$, eine erfolglose Suche betrachtet also im Mittel über $200$ Einträge.

Das Problem: es kommt schnell zur Klumpenbildung, da sich die Schlüssel schnell aufsammeln und die Ketten so lokal immer zusammenwachsen. Wenn dann irgendwo in diesen Block gehasht wird, wird die Kette um eines länger. Diese Problem nennt man *primäre Häufung*.

##### Quadratisches Sondieren

Was können wir dagegen tun? Die Abstände Schritt für Schritt grösser machen, also $h(k), h(k)-1, h(k)+1, h(k)-4, h(k)+4, h(k)-9, ...$ was man quadratisches Sondieren nennt. Wir benutzen also $s(j, k) = (\lc j/2 \rc )^2(−1)^j$.

Natürlich springen wir auch so modulo $m$ rum, aber erreichen wir so überhaupt noch alle Positionen im Array?^[Als Fingerübung: Für $m$ prim der Form $4^j + 3$ werden beim quadratischen Sondieren immer alle Plätze angeschaut.]

Ein Beispiel: $m=7$ und $K=\{12, 53, 5, 15, 2, 19\}$

| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|----|----|---|---|----|----|---|
| | 15 | 2 | 19 | 53 | 12 | 5 |

Das Problem der primären Häufung lässt sich so beheben. Doch für alle Schlüssel mit dem selben Hashwert klappern wir genau die selben Pätze ab, da die Sondierungsfolge immer die selbe ist. Dies nennt man *sekundäre Häufung*.

##### Double-Hashing

Wunsch: Jede Permutation der anderen $m-1$ Pläte sollte gleich wahrscheinlich als Sondierfolge auftreten, was man *uniformes Sondieren* nennt. In der Praxis wird das oft nicht erreicht, mit zufälligen Sondiermethoden kann man aber sehr nahe herankommen. Dies wollen wir hier aber nicht weiter anschauen.

Was wir hingegen anschauen wollen ist folgende Sondierfunktion, welche eine zweite Hashfunktion $h'$ verwendet, um zu sondieren mit $h(k), h(k)-h'(k), h(k)-2h'(k), ...$ also $s(j,k)=j\cdot h'(k)$. Davon erhoffen wir uns nun, dass für zwei Schlüssel mit $h(k) = h(k')$ die Sondierfolgen unterschiedlich sind und wir so in wenigen Sondierschritten einen freien Platz finden. Dieses Verfahren nennt man *double hashing*. Was ist eine gute solche zweite Hashfunktion $h'$?
* $h'(k)$ darf nicht $0$ werden
* $h'(k)$ muss unabhängig von $h(k)$ sein
* $h'(k)$ darf $m$ nicht teilen

Wenn $m$ und $m-2$ zwei Primzahlen sind, dann sind die Funktionen $h(k) = k \bmod m$ und $h'(k) = 1 + k \bmod (m-2)$ eine gute Wahl.

### Entfernen von Elementen
Wenn wir beim Entfernen von Elementen einfach den Platz freigeben, dann kann die Sondierung bei einer späteren Suche zu früh abbrechen und dementsprechend ein Element nicht mehr finden obwohl es noch in der Hashtabelle ist. Um das zu beheben, sollten wir gelöschte Elemente nicht einfach als freie Plätze hinterlassen sondern als *gelöschte Elemente* markieren. Ein solches gelöschtes Element können wir bei einer Einfügeoperation wieder belegen (überschreiben) aber müssen wir beim Sondieren unbedingt als belegt betrachten und weitersondieren bis wir einen leeren Platz finden.

Zusammenfassend: Wir haben noch keine Datenstruktur die im Worst Case alle Operationen effizient machen kann. Wir haben einfach die Effizienz gemittelt und so effiziente Operationen erzielen können.