ADS – Vorlesung zu Hashing, Juni 2006
Prof. Dr. W. Conen
FH Gelsenkirchen
SS 2006
Hashing - Ausgangssituation



[Einstieg: s. auch ihr Mitschrieb aus der letzten Woche]
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?


Frage 2:
Wie geht man mit Kollisionen um, wenn sie denn auftreten?
Wir schauen uns zunächst Frage 2 an.
Antworten zur Frage 1 finden Sie in ihrem Mitschrieb.
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): O(1)
Member(d):

Best Case: O(1)

Worst Case: O(|K|)...Aua!

Mittlerer Fall, s. Mitschrieb





„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
weitere Details s. Mitschrieb
Unsere Übungsaufgabe...

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
Übungsaufgabe! ;-)
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
Kommentar
-2 (in rI1)
5 (in rI2)
-2-8+5 = -5
-5+16+5 = 16
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


Hashing z.B. in

Cormen et al. „Introduction to Algorithms“ oder

Owsnicki-Klewe „Algorithmen und Datenstrukturen“ (s. auch frühere
Literaturempfehlungen)
Zum MIX-Computer von Knuth können sie direkt bei Knuth schauen („The Art
of Computer Programming“) 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