22.05.2000
Universität Dortmund, Lehrstuhl Informatik [email protected]
EINI IIEinführung in die Informatik
für Naturwissenschaftler und Ingenieure II
Prof. Dr. Gisbert Dittrich
18-2
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Gliederung
Hashing• das Problem: Alternatives Suchverfahren
– bisheriges Vorgehen– geänderte Randbedingungen -->
• die Idee• die Lösung• ein Beispiel: Intliste
– deren Implementierung
• Hash1: festverdrahtete Hashfunktion• Hash2: rein virtuelle Hashfunktion
18-3
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Suchen
Erinnerung:
Suche mit binären Suchbäumen• Ein binärer Suchbaum ist ein binärer Baum, dessen Knoten mit z.B. ganzen Zahlen gefüllt sind, so daß gilt:
– linker und rechter Unterbaum sind binäre Suchbäume,– die Beschriftung der Wurzel ist größer als die Beschriftung der Wurzel des linken, kleiner als die Beschriftung des rechten Unterbaums.
18-4
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Binäre Suchbäume: Suchen
17
4 36
2 8
6
7
19 40
Suche nachdem Element 5
Suche nachdem Element 19
18-5
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Warum ein neues Suchverfahren?
• Voraussetzung für Binäre Suchbäume:• (totale) Ordnung auf der Nutzinformation
• Ordnung nicht immer kanonisch verfügbar: • Beispiele:
– komplexe Zahlen,– Einträge in einer Datenbank (Kundendaten etc.).
• Also: Alternativen notwendig.
18-6
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Idee
Es geht immer:• Suchen in einer Menge U
– z. B. realisiert über verkettete Liste
Variation dieser Idee:• Suchen in einer Menge von Teilmengen (disjunkt)
– 1.Schritt: Bestimme (Teil)-Menge, in der zu suchen ist.
– 2. Schritt: Durchsuche diese Menge nach gegebenem Element
• Randbedingung:– Möglichst gleich große Teilmengen.
18-7
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Idee Fortsetzung
• Formaler:• Sei U die (endliche) Menge aller Objekte, für die die Suchoperationen definiert werden sollen. • h: U -> {0, ..., m-1} sei eine Funktion.• U‘: Menge aller Elemente, die bereits verarbeitet sind.• U‘(j) := h -1(j) U‘ : Menge aller Elemente in U‘, die von h auf j abgebildet werden.
• Aufgabe: t U schon in U‘ ?
18-8
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Idee Fortsetzung
• Schritte zur Lösung der Aufgabe:– Berechne h(t),– sieh nach, ob t ein Element von U‘(h(t)) ist.
Also : Statt ganz U‘ zu durchsuchen, durchsuche nur einen Teil, nämlich U‘(h(t)).
• h heißt Hashfunktion – to hash: mischen, zerhacken.– h erfülle: die U‘(j) sollten etwa gleich groß sein.
• Repräsentation? • Jede Teilmenge U‘(j) als verkettete Liste •U‘ als Feld verketteter Listen
18-9
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Idee Fortsetzung
0
1
2
3
4
Listen
einFeld
18-10
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Was ist zu tun?
• Wähle Universum• Hier: (zunächst ganze) Zahlen
• Formulierung von Listen ganzer Zahlen• (Datentyp IntListe, (erneute) Wiederholung).
• Datentyp HashTafel • auf der Grundlage von IntListe.
• Kritisch: Hashfunktion. • Wird gleich betrachtet.
18-11
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Der Datentyp IntListe
int Element; // Element der Liste; Nutzinformation
IntListenEl * weiter;/* Verkettung: Zeiger auf das nächste Element */
Zunächst: IntListenEl(ement)
void NutzinfoDruck(){cout << Element;};
Attribute:
Methode:
Nutzinfo weiter
18-12
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
IntListe
Attribut:
IntListenEl * DieIntListe;
Methoden:IntListe() //Konstruktor
IntListe(int r) //Konstruktor
bool Testen(int r)
void Entfernen(int r)
void Einfuegen(int r)
void Druck()
18-13
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Hilfsmethoden:bool IstDa(IntListenEl *, int)
/* IstDa (Liste, r) überprüft(rekursiv), ob das Elementr in der Liste Listebereits vorhanden ist */
IntListenEl * WegDamit (IntListenEL *,int)
/* WegDamit(Liste, r) entfernt das Element r aus der Liste Liste und gibt einen Zeiger auf die modifizierte Liste zurück*/
IntListe
18-14
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Der Datentyp IntListe (Forts.)
Hilfsmethode:void ListenDruck(IntListe *);
/* ListenDruck(Liste) druckt die Liste Liste aus; durch einen rekursiven Durchlauf.*/
Hilfsfunktionen --> private/protected
18-15
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Der Datentyp IntListe (Forts.)
IntListe() {DieIntListe = NULL;}
IntListe(int r) {DieIntListe = new IntListenEl;DieIntListe -> Element = r;DieIntListe -> weiter = NULL;}
Zwei Konstruktoren:
18-16
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Ausgewählte Methoden
bool Testen(int r) { return IstDa(DieIntListe, r);}
void Entfernen(int r) {DieIntListe = WegDamit(DieIntListe, r);}
void Einfuegen(int);void Druck(){
ListenDruck(DieIntListe);}
Methoden inline formulierbarAusnahme: Einfuegen.
18-17
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Ausgewählte Methoden: IstDa
bool IntListe::IstDa(IntListenEl * Liste, int r){if (Liste == NULL)
return false;else {
if (Liste->Element == r)return true;
elsereturn IstDa(Liste->weiter, r);
}}
18-18
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Ausgewählte Methoden: WegDamit
IntListenEl * IntListe::WegDamit(IntListenEl * Liste, int r) {
if (Liste == NULL)return Liste;
else {if (Liste->Element == r)
return Liste->weiter;else {
Liste->weiter = WegDamit(Liste->weiter, r);return Liste;
}}}
18-19
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Ausgewählte Methoden: Einfuegen
void IntListe::Einfuegen(int r) {if(!Testen(r)) {
IntListenEl * neu = new IntListenEl;
neu->Element = r;neu->weiter = DieIntListe;DieIntListe = neu;
}}
18-20
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Ausgewählte Methoden ListenDruck
void IntListe::ListenDruck(IntListenEl * Liste) {static int t = 1;if (Liste != NULL) {
Liste->NutzinfoDruck ();// Verbindungcout << (t++%8==0 ? "\n" : "\t");ListenDruck(Liste->weiter);
}else {
t = 1; cout << "(Ende)" << endl;
}}// Nur harter Kern dieser Methode !!
18-21
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Hashing
• Sei t U.
• Aufgaben• Speichere t
– Element t wird in der Liste zu h(t) abgespeichert.
• Suche t– Schaue in der Liste zu h(t) nach und suche dort.
• Lösche t– Lösche t in der Liste zu h(t).
18-22
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Hashing (Forts.)
• Zentral: Hashfunktion h• Muß einfach zu berechnen sein• Sollte die Elemente gleichmäßig verteilen.
• Setze • h(x) = x%m,
wobei m die Anzahl der einzelnen Listen.
• Die Listen heißen Konfliktlisten (clash lists) oder Körbe (buckets).
18-23
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Vereinbarung
• Die Datenstruktur heißt Hashtafel.
• Vereinbare also (m sei gegeben) • die Hashtafel als Feld mit m verketteten Listen vom Typ IntListe,• definiere Operationen darauf.
18-24
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Der ADT HashTafel
• hT sei ein Feld aus m verketteten Listen.• Merke mir in der Variablen maxBucket die Größe
m des Feldes. • Die Größe der Hashtafel (also von hT) soll erst zur
Laufzeit festgelegt werden können.
18-25
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Der ADT HashTafel (Forts.)
• Operationen für das Element t U:• Überprüfen,
ob t in der Hashtafel vorhanden ist:
Aufruf von hT[h(t)].Testen(t)(. oder -> ??)
• Einfügen: Füge t ein, indem ich hT[h(t)].Einfuegen(t) aufrufe, falls das Element t nicht in der Tafel ist
• Entfernen: Entferne t durch Aufruf von hT[h(t)].Entfernen(t).
18-26
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Die Klasse HashTafel
• Für jeden Eintrag hT[j] in der Tafel gilt:• hT[j] ist ein Zeiger auf IntListe, also:
IntListe * hT[j]
• Damit Vereinbarung: IntListe ** hT.
• Allokation einer Tafel mit m Elementen: hT = new IntListe * [m]
• Nach der Allokation der Tafel: • Allokation der einzelnen Elemente, also:
for (int i = 0; i < m; i++) hT[i] = new IntListe();
18-27
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Die Klasse HashTafel (Forts.)
class HashTafel {private:
IntListe ** hT;int maxBucket;
public:HashTafel(int);int h(int r){return r%maxBucket;}int Testen(int r)
{return hT[h(r)]->Testen(r);}void Einfuegen(int r)
{hT[h(r)]->Einfuegen(r);}void Entfernen(int r)
{hT[h(r)]->Entfernen(r);}void Druck();
};
18-28
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Muß noch weiter diskutieren:• Konstruktor• Methode Druck
(stützt sich vollständig auf die entsprechende Methode für IntListe ab).
Die Klasse HashTafel (Forts.)
18-29
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Die Klasse HashTafel (Konstruktor; Druck)
HashTafel::HashTafel(int m) {maxBucket = m;hT = new IntListe *[m];for (int i = 0; i < m; i++)
hT[i] = new IntListe();}
void HashTafel::Druck() {int i;for (i = 0; i < maxBucket; i++) {
cout << "\nBucket für i = " << i << ":\n";hT[i]->Druck();
}} // Harter Kern der Methode
18-30
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Beispielprogramm
int main() {int maxAnzahl = 17;int Treffer = 0;int j;HashTafel * dieTafel = new HashTafel(maxAnzahl);for (int i = 0; i < 2000; i++) { j=rand(); if (dieTafel->Testen(j) == true) Treffer++;
dieTafel->Einfuegen(j);}
cout << "Anzahl der Treffer: " << Treffer << endl;cout << "Durchlauf durch die Tafeln\n";dieTafel->Druck();// + zusätzl. Ausdruck !!return 0;}
Hash 1
18-31
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Implementierung Hash 1
// Hashing von Integern über IntListen, 1// alt: hash1 von Doberkat, EINI II, SS 99// von GD+ JW angepaßt#include <iostream.h>#include <stdlib.h> // nötig für rand()int GesamtAnzahlEintraege = 0;
class IntListenEl { public:
int Element;IntListenEl * weiter;void NutzinfoDruck(){
cout << Element;};};
18-32
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Implementierung Hash 1
// Hashing von Integern über IntListen, 2class IntListe { protected:
IntListenEl * DieIntListe;bool IstDa(IntListenEl *, int);
/* Testet, daß der int-Wert in der Liste von IntListenEl enthalten ist*/
IntListenEl * WegDamit (IntListenEl *, int); /* Entfernt das Listenelement mit dem Eintrag int-Wert aus der Liste von IntListenEl., sofern vorhanden */ void ListenDruck(IntListenEl *); public:
IntListe() {DieIntListe = NULL;}IntListe(int r) { DieIntListe = new IntListenEl;
DieIntListe -> Element = r;DieIntListe -> weiter = NULL;}
18-33
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Implementierung Hash 1
// Hashing von Integern über IntListen, 3 public:// Fortsetzung
...bool Testen(int r) { return
IstDa(DieIntListe, r);}void Entfernen(int r) { DieIntListe = WegDamit(DieIntListe, r);}void Einfuegen(int);void Druck(){ListenDruck(DieIntListe);}
};bool IntListe::IstDa(IntListenEl * Liste, int r) {
if (Liste == NULL) return false;else {if (Liste->Element == r)
return true;else
return IstDa(Liste->weiter, r);}}
18-34
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Implementierung Hash 1
// Hashing von Integern über IntListen, 4IntListenEl * IntListe::
WegDamit(IntListenEl * Liste, int r) {if (Liste == NULL)
return Liste;else {if (Liste->Element == r)
return Liste->weiter;else {Liste->weiter = WegDamit(Liste->weiter, r);
return Liste;}}}void IntListe::Einfuegen(int r) {
if(!Testen(r)) {IntListenEl * neu = new IntListenEl;neu->Element = r;neu->weiter = DieIntListe;DieIntListe = neu;}}
18-35
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Implementierung Hash 1
// Hashing von Integern über IntListen, 5void IntListe::ListenDruck(IntListenEl * Liste) {
static int t = 1, AnzEintraege = 0;if (Liste != NULL) {
Liste->NutzinfoDruck();cout << (t++%8==0 ? "\n" : "\t");AnzEintraege++;ListenDruck(Liste->weiter);}
else {t = 1;cout << endl<< "Anzahl der Einträge: \t" << AnzEintraege << " (Ende)" << endl;GesamtAnzahlEintraege += AnzEintraege;AnzEintraege = 0;}
}Zurück Zu Hash 2
18-36
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Implementierung Hash 1
// Hashing von Integern über IntListen, 6class HashTafel { private:
IntListe ** hT;int maxBucket;
public:HashTafel(int);int h(int r){return r%maxBucket;}int Testen(int r) {return hT[h(r)]->Testen(r);}void Einfuegen(int r) {hT[h(r)]->Einfuegen(r);}void Entfernen(int r){hT[h(r)]->Entfernen(r);}void Druck();};
HashTafel::HashTafel(int m) {maxBucket = m;hT = new IntListe *[m];
for (int i = 0; i < m; i++) hT[i] = new IntListe();}
18-37
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Implementierung Hash 1
// Hashing von Integern über IntListen, 7void HashTafel::Druck() {
int i;for (i = 0; i < maxBucket; i++) {
char jn = 'j';if (i > 0) {
cout << "\nweiter? (j = ja): ";cin >> jn;
}if (jn != 'j') {
cout << "Ciao" << endl;break;}
cout << "\nBucket für i = " << i << ":\n";hT[i]->Druck();}
}
18-38
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Implementierung Hash 1
// Hashing von Integern über IntListen, 8int main() {
int maxAnzahl = 17;int Treffer = 0;int j;HashTafel * dieTafel = new HashTafel(maxAnzahl);for (int i = 0; i < 2000; i++) { j=rand(); if (dieTafel->Testen(j) == true) Treffer++;
dieTafel->Einfuegen(j);}cout << "Anzahl der Treffer: " << Treffer << endl;cout << "Durchlauf durch die Tafeln\n";dieTafel->Druck();cout << " Insgesamt verarbeitete Einträge:\t" << GesamtAnzahlEintraege;return 0;}
18-39
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Beispielprogramm
• Treffer: 71. • Bedeutet: Bei 2000 erzeugten Zufallszahlen werden 71 doppelt erzeugt.
• Statistik: • Mißt die Längen der einzelnen Listen
18-40
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Statistik
0
20
40
60
80
100
120
140
1 3 5 7 9 11 13 15 17
Reihe1
18-41
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Rein virtuelle Hashfunktion eröffnet Parametrisierung derselben:
Sei IntListe wie in Hash 1.
Verallgemeinerung
class AbstrakteHashTafel {private:
IntListe ** hT;protected:
int maxBucket; // nötig für Unterklassen public:
AbstrakteHashTafel(int);virtual int h(int) = 0;// Rest wie vorhin
};
18-42
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
verhindere arithmetischen
Überlauf
Neue Hash-Funktion
class NeueHashTafel : public AbstrakteHashTafel {public:
NeueHashTafel(int m) : AbstrakteHashTafel(m) {}
int h(int);};
int NeueHashTafel::h(int r) {long int rl = (long int) r;long int l = rl * rl;long int maxx = (long int) maxBucket;return l % maxx;}
Hash2„cast“
18-43
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
// Abstrakt formuliertes Hashing, 1// Die ersten Zeilen überein mit Hash 1Vgl. dazu Hash 1, Seite 1 - Seite 5
class AbstrakteHashTafel { private:
IntListe ** hT; protected: // wohl nötig, um
int maxBucket; // Unterklassen zu bilden public:
AbstrakteHashTafel(int);virtual int h(int) = 0;
// erst in Unterklassen zu definieren
Implementierung Hash 2
Zurück Zu Hash 1
18-44
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
// Abstrakt formuliertes Hashing, 2 // public Fortsetzung:
int Testen(int r) {return hT[h(r)]->Testen(r);}void Einfuegen(int r) {hT[h(r)]->Einfuegen(r);}void Entfernen(int r){hT[h(r)]->Entfernen(r);}void Druck();
};
AbstrakteHashTafel::AbstrakteHashTafel(int m) {maxBucket = m;hT = new IntListe *[m];for (int i = 0; i < m; i++)
hT[i] = new IntListe();}
Implementierung Hash 2
18-45
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
// Abstrakt formuliertes Hashing, 3void AbstrakteHashTafel::Druck() {
int i;for (i = 0; i < maxBucket; i++) { char jn = 'j';
if (i > 0) {cout << "\nweiter? (j = ja): ";cin >> jn;}
if (jn != 'j') {cout << "Ciao" << endl; break;}
cout << "\nBucket für i = " << i << ":\n";hT[i]->Druck();}}
Implementierung Hash 2
18-46
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
// Abstrakt formuliertes Hashing, 4class NeueHashTafel : public AbstrakteHashTafel {
public:NeueHashTafel(int m) :
AbstrakteHashTafel(m) {}int h(int);
};
int NeueHashTafel::h(int r) {long int rl = (long int) r;long int l = rl * rl;long int maxx = (long int) maxBucket;return l % maxx;}
Implementierung Hash 2
18-47
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
// Abstrakt formuliertes Hashing, 5int main() {
NeueHashTafel * dieTafel = new NeueHashTafel(17);
int j; int Treffer = 0;for (int i = 0; i < 2000; i++) {
j = rand();if (dieTafel->Testen(j) == true)
Treffer++;dieTafel->Einfuegen(j);}
Implementierung Hash 2
18-48
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
// Abstrakt formuliertes Hashing, 6// int main() Fortsetzung
cout << "Anzahl der Treffer: " << Treffer << endl;
cout << "Durchlauf durch die Tafeln\n";dieTafel->Druck();cout << " Insgesamt verarbeitete"
<< "Einträge:\t" << GesamtAnzahlEintraege;
return 0;}
Implementierung Hash 2
Hash2
18-49
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Messung
0
50
100
150
200
250
1 3 5 7 9 11 13 15 17
Reihe1
Oh!Oh!
18-50
Prof. Dr. G. Dittrich22.05.2000
EINI II Kap. 18: Hashing
Was lernen wir daraus?
• Die Hash-Funktion ist verantwortlich für die
Länge der einzelnen Listen.• Je länger die Listen sind, desto länger sind die Suchzeiten, desto schlechter kann also das Verfahren insgesamt sein • Extremfall: nur eine Liste,
– dann hat sich der Aufwand nicht gelohnt.