ADS – Vorlesung zu Hashing
Prof. Dr. W. Conen
FH Gelsenkirchen
Hashing - Ausgangssituation


Datenstruktur „Dictionary“: Insert, Delete, Member/Search
Bisher: Der Schlüssel selbst konnte „unmittelbar“ als Index in einem Array
zur Speicherung der Daten verwendet werden
T
U
4
0
6
7
K
2K
5
Nutzlasten
1
1
9
0
8
3
2
3
4
5
6
7
8
9
U = Universum möglicher Keys (=Schlüssel);
K = Tatsächlich auftretende Keys; T = Direkt-addressierte Tabelle
Hashing - Ausgangssituation




Datenstruktur „Dictionary“: Insert, Delete, Member/Search
Jetzt: U ist sehr groß (z.B. Strings!) und |K| << |U|, d.h. die Anzahl
tatsächlich genutzter Schlüssel ist eher klein.
Selbst, wenn unser T genug Platz für die möglichen Schlüssel hätte, wäre
das unschön: es würde sehr viel Platz nicht verwendet!
Also Annahme: |U| >> |T| ¸ |K|
T
0
1
U
2 = h(k1)
3
K
kK
1
k3
k2
k4
4
5 = h(k2) = h(k3)
6
7 = h(k4)
8
h = Hashfunktion: U ! {0,...,m-1}
m-1
Kollision!
Hashing - Ausgangssituation



Annahme: |U| >> |T| ¸ |K|

K kann auch größer, als T werden, dann gibt es aber natürlich auf jeden
Fall gewisse Probleme...
Lösung: Wir bilden mit einer Hashfunktion h : U ! {0,...,m-1} die
(möglichen und tatsächlichen) Schlüssel auf die Einträge in T ab
Hauptproblem: es können Kollisionen auftreten

Worst-Case: bei „ungünstiger“ Hashfunktion können alle
tatsächlichen Werte auf einen Index abgebildet werden

Und das selbst dann, wenn die Hashfunktion „im Prinzip“, also
gemessen an U, z.B. bei Annahme einer Gleichverteilung der
Auftretenswahrscheinlichkeit, „gut“ zu sein scheint!
Hashing

Was hätten wir gern?
 Eine Hashfunktion, die wenigstens im Prinzip alle Werte in
[0,...,m-1] treffen kann (also surjektiv ist)
 Eine Hashfunktion, die die tatsächlich auftretenden Werte (also
K) möglichst gut über T „streut“

also Kollisionen so weit wie möglich vermeidet
 Bei der Konstruktion von h weiß man eventuell bereits etwas
über die Auftretenswahrscheinlichkeit der möglichen Schlüssel

Wenn es um z.B. um Namen geht, dann sind manche
Buchstabenkombination häufiger („Schmidt“, „Weber“),
manche eher selten („Xyzmick“)
 Die Hashfunktion sollte „Schmidt“ und „Weber“ möglichst
auf verschiedene Indices abbilden
 Wo „Xyzmick“ landet, ist eher nicht so wichtig...
Hashing

Ursache von Kollisionen:



„Unvermeidbar 1“: Wenn Keywerte mehrfach auftreten können

z.B. mehrere Personen mit Namen „Weber“

Randbemerkung: manchmal hilft dann natürlich, die Schlüssel zu
„vergrößern“, z.B. „Vorname Nachname“ zu verwenden
„Unvermeidbar 2“: Wenn K größer als T ist (aber selbst dann ist eine
Minimierung von Kollisionen hilfreich!)
„Vermeidbar“: Wenn |K| <= |T|, dann könnte h | K ( also „h
eingeschränkt auf K“, s. GIN1b) im Prinzip injektiv sein...

wenn es aber dann nicht injektiv ist, dann gibt es „unnötige“
Kollisionen!
Hashing

Wichtige Fragen:

Frage 1:
Wie „designed“ man eine Hashfunktion so, dass sie „möglichst“ injektiv
ist, also „vermeidbare“ Kollisionen vermeidet? (Übungsaufgabe)


Frage 2:
Wie geht man mit Kollisionen um, wenn sie denn auftreten?
Wir schauen uns zunächst Frage 2 an.
Hashing: Umgang mit Kollisionen (1)



Kollisionen treten auf
Die Daten jeder „Kollisionsklasse“ werden in einer Liste hinter dem
berechneten Indexwert für ihren Schlüssel abgelegt.
Das nennt man „Chaining“, also Verkettung
T
0
U
k1
K
k1K
k3
k2
k2
k4
k4
h
m-1
k3
Hashing: Umgang mit Kollisionen (2)




Kollisionen treten auf
Für jeden Datensatz wird ein Platz direkt in T gesucht
Verschiedene Strategien möglich (z.B. Re-Hashing, Sondieren)
Nebenproblem: Was passiert, wenn T überläuft
T
0
Nutzlasten
U
k1
K
kK
1
k3
„Sondieren“ in der
Nachbarschaft oder
zweites (drittes, ...)
Hashing
k3
k2
k2
k4
k4
h
[s. auch Übungsaufgaben zu Hashing]
m-1
Hashing: Kollisionsbehandlung (3)



„Chaining“
Insert(d), Datensatz d hat den
Schlüssel k

Kosten: O(1) (+ Kosten für die
Berechnung von h(k) – h sollte
also möglichst effizient
berechenbar sein! Wir nehmen
O(1) an)
Delete(d)/Member(d):

Best Case: O(1)

Worst Case: O(|K|)...Aua!

Mittlerer Fall, O(|K|/2) –

auch nicht schön

Man kann eine bessere
Datenstruktur, als eine
ungeordnete Liste wählen und hier
die Werte verbessern...aber
eigentlich wollte man ja die
Position über die Hashfunktion
direkt ausrechnen und eben NICHT
weitere Datenstrukturen für das
Suchen/Finden implementieren





„Platz in T suchen“
Insert(d):

Kosten je nach
Kollisionsbehandlung

Best Case: O(1)

Worst Case: O(min(|T|,|K|))
Delete(d): wie Insert
Member(d): wie Insert
Warum min(|T|,|K|) –

wenn T bereits (fast) voll ist,
merken wir das erst nach
O(|T|) Ausführungen der
Hash-Funktion(en)

wenn |K| < |T| und unsere
Hashfunktionen alle Einträge
in T ohne Wiederholungen
prüfen, dann muß nach
spätesten |K|-1-Aufrufen ein
Platz gefunden sein
Literatur

Hashing z.B. in

Cormen et al. „Introduction to Algorithms“ oder

Owsnicki-Klewe „Algorithmen und Datenstrukturen“ (s. auch frühere
Literaturempfehlungen)
Perfektes Hashing...ein kleines Beispiel




In einem berühmten Buch von Knuth findet sich folgendes
Beispiel:
Gegeben ist die folgende Menge W von 31 Wörtern, die als
Schlüssel verwendet werden.
A
HAD OF
AND HAVE ON
ARE
HE
OR
AS
HER
THAT
AT
HIS
THE
BE
I
THIS
BUT
IN
TO
BY
IS
WAS
FOR
IT
WHICH
FROM NOT
WITH YOU
Sie haben ein Array T mit 41 Einträgen zur Verfügung, um
die Schlüssel (und die zugehörigen Satellitendaten) in
diesem Array abzulegen. Diese Einträge sind von 0 bis 40
indiziert.
Perfektes Hashing...ein kleines Beispiel



Ihre Aufgabe ist es nun, eine Funktion h anzugeben, die eine Zuordnung der
Schlüssel zu Einträgen in das Array vornimmt}, also W auf [0..40] abbildet. Diese
Zuordnung soll injektiv sein (es darf also nicht zu Kollisionen kommen: jeder
Schlüssel soll auf einen anderen Arrayeintrag abgebildet werden – deshalb nennen
wir es perfektes Hashing).
Um sinnvoll rechnen zu können, ist es eine gute Idee, zunächst die Buchstaben auf
numerische Codes zu mappen, z.B. in dem sie die ASCII-Werte der Buchstaben
verwenden. Sie können aber auch ein anderes sinnvolles Mapping versuchen, z.B. A
auf 0, B auf 1, oder ähnlich. Vergessen sie nicht, dieses Mapping auch anzugeben!
Klar sein sollte, was so eine Funktion dann machen kann: sie kann z.B.
Buchstabenkodes addieren, oder auch positionsabhängig gewichten und dann
addieren, also z.B. Code-des-Zeichens-an-Position-0 + 261*Code-des-Zeichens-anPosition-1 + ..., und/oder Modulo bilden usw. -- Hauptsache, zum Schluss kommt
eine Zahl zwischen 0 und 40 (inklusive) heraus!

Anmerkung: Es ist nicht erlaubt, einfach ein explizites Mapping zwischen Wörtern und
Indices anzugeben, also die geordneten Paare direkt aufzuschreiben!

Versuchen Sie es, eine injektive Funktion h: W -> [0..40] zu finden!
Diese kleine Aufgabe...

stammt aus Knuth: The Art of Computer Programming, Volume 3

Wir wollen 31 Strings auf den Bereich [0..40] bijektiv abbilden (im Original auf
[-10..30])

Es gibt 4131, ungefähr also 1050 Funktionen, die 31 Werte auf 41 Werte
verteilen

Es gibt 41*40*...*11 = 41!/10!, ungefähr also 1043 injektive Funktion

Das sieht nach vielen aus...aber es ist nur 1 aus ungefähr 10 Millionen der
„möglichen“ Funktionen!

Aber sie sehen: sie hatten eine große Auswahl bei der Lösung der Aufgabe! ;-)

Für die Klausur ist diese Beispielaufgabe nicht relevant!

Aber sie zeigt hoffentlich, wie schwer es werden kann, eine kompakte Funktion
zu finden, die Kollisionen vermeidet, OBWOHL sie vorab wissen, welche
Schlüssel vorkommen werden...und das wissen sie normalerweise
nicht...normalerweise haben sie bestenfalls begründete Erwartungen zur
Verteilung der vorkommenden Schlüsselwerte K über den Raum der möglichen
Schlüsselwerte U.
Knuths Lösung



















Ein MIX-Programm
LD1N
LD2
INC1
J1P
INC1
LD2
J2Z
INC1
J1P
INC1
LDA
JAZ
DEC1
-5,2
J1N
INC1
9F: LDA K
CMPA
JNE
K(1:1)
K(2:2)
-8,2
*+2
16,2
K(3:3)
9F
-28,2
9F
11,2
K(4:4)
9F
9F
10
TABLE,1
FAILURE
Beispiel-Ablauf für BE
-2 (in rI1)
5 (in rI2)
-2-8+5 = -5
-5+16+5 = 16
Kommentar
Wert(B)=2,Position(B)=1
Sprung, wenn 1 positiv
Sprung, wenn 2 leer/null
Sprung, wenn Accu leer
(Sprungziel eigentlich 9H)
(versteht aber niemand... ;)
Wenn Sie noch kein h gefunden haben, dann suchen sie noch ein wenig weiter!
Literatur zum Beispiel

Zum MIX-Computer von Knuth können sie direkt bei Knuth schauen („The Art
of Computer Programming“ – auch die Quelle für das Beispiel) oder einen der
Emulatoren ausprobieren:


http://www.recreationalmath.com/mixal/ (Emulator in HTML mit
Javaskript realisiert)
http://www.gnu.org/software/mdk/mdk.html, der GNU-MIXDevelopment-Kit (mit Doku:
http://www.gnu.org/software/mdk/manual/mdk.html)

PPT