Hashing - Technische Fakultät

Algorithmen und Datenstrukturen II
Peter Steffen
AG Praktische Informatik
Technische Fakultät
Universität Bielefeld
Vorlesung Sommer 2009
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Teil I
Hashing
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Einführendes Beispiel
Ein Pizza-Lieferservice in Bielefeld speichert die Daten seiner
Kunden: Name, Vorname, Adresse und Telefonnummer. Wenn ein
Kunde seine Bestellung telefonisch aufgibt, um dann mit der Pizza
beliefert zu werden, dann muss er seine Telefonnummer angeben,
da er über diese Nummer eindeutig identifiziert werden kann.
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Telefonnummer
00000000
00000001
00000002
...
99999997
99999998
99999999
Peter Steffen
A&D II, Vorlesung 2009
Name
Müller
Schmidt
Schultz
...
Meier
Neumann
Schröder
Strategien zur Behandlung von Kollisionen
Vorname
Heinz
Werner
Hans
...
Franz
Herbert
Georg
PLZ
33615
33615
33602
...
33609
33612
33647
Klasse Hashtable
Straße
Unistraße 15
Grünweg 1
Arndtstraße 12
...
Kirchweg 4
Jägerallee 15
Mühlweg 2
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Bielefeld hat ca. 300.000 Einwohner, dann gibt es vielleicht
200.000 Telefonnummern. Davon bestellt jeder fünfte eine Pizza –
bleiben 40.000 potentielle Einträge, verteilt auf mehrere
Pizza-Lieferservices. Optimistisch geschätzt wird unsere Pizzeria
also ca. 10.000 Kunden haben.
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Da stellt sich folgende Frage: Wir wissen doch gar nicht, welche
Telefonnummern bestellen werden – wie sollen denn dann die
Zeilen benannt werden?
Unsere Aufgabe ist es, alle 100 Millionen Telefonnummern (denn
jede einzelne könnte ja theoretisch bestellen) so abzubilden, dass
sie in eine 10.000 Zeilen große Tabelle passen.
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Modulo
Hierzu machen wir uns jetzt eine mathematische Operation
zunutze, die Modulo-Operation:
x mod y
liefert als Ergebnis den Rest der ganzzahligen Division x/y .
Beispielsweise ergibt 117 mod 20 = 17, da 117 = 5 · 20 + 17.
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Hash-Funktion
Beispiel
h(Telefonnummer) = Telefonnummer mod Tabellenlänge
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Hash-Funktion
Beispiel
h(Telefonnummer) = Telefonnummer mod Tabellenlänge
oder allgemein:
Beispiel
h(k) = k mod m
mit h für Hashfunktion, k für key und m für Tabellenlänge.
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Kollisionen
Wir benutzen also diese Hashfunktion, um jedem Schlüssel einen
Index (hier eine Zahl zwischen 0 und 9999) in einer verkleinerten
Tabelle (der sogenannten Hashtabelle) zuzuordnen und damit eine
Menge Platz zu sparen.
Leider kann es allerdings passieren, dass in ungünstigen Fällen zwei
oder mehr Schlüssel (Telefonnummern) auf denselben Index in der
Hashtabelle abgebildet werden,
Beispiel
z.B. ist 01063852 mod 10000 = 08153852 mod 10000 = 3852.
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Allgemeine Definitionen
Formal gesehen ist Hashing ein abstrakter Datentyp, der die
Operationen insert, delete und search auf (dynamischen)
Mengen effizient unterstützt.
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Direkte Adressierung
Hashing ist im Durchschnitt sehr effizient – unter vernünftigen
Bedingungen werden obige Operationen in O(1) Zeit ausgeführt
(im worst-case kann search O(n) Zeit benötigen).
Wenn die Menge U aller Schlüssel relativ klein ist, können wir sie
injektiv auf ein Feld abbilden; dies nennt man direkte Adressierung
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Direkte Adressierung
0
U
(Universum der Schl"ussel)
0
9
6
2
7
4
1
1
3
4
K
(Aktuelle Schl"ussel)
2
5
3
6
5
7
8
8
9
T
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Hashing
Ist die Menge U aller Schlüssel aber sehr groß (wie im obigen
Beispiel des Pizza-Services), so können wir nicht mehr direkt
adressieren. Unter der Voraussetzung, dass die Menge K aller
Schlüssel, die tatsächlich gespeichert werden, relativ klein ist
gegenüber U, kann man die Schüssel effizient in einer Hashtabelle
abspeichern. Dazu verwendet man allgemein eine Hashfunktion
Definition
h : U → {0, 1, . . . , m − 1},
die Schlüssel abbildet auf Werte zwischen 0 und m − 1 (dabei ist m
die Größe der Hashtabelle).
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Hashing
0
U
h(k1)
(Universum der Schl"ussel)
h(k4)
k1
K
(Aktuelle Schl"ussel)
h(k2) = h(k5)
k4
k2
h(k3)
k5
k3
m−1
T
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Typische Hashfunktion
Eine typische Hashfunktion h für U = N ist
Beispiel
h(k) = k mod m.
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Kollisionen
da Hashfunktionen nicht injektiv sind, tritt das Problem der
Kollision auf: zwei Schlüsseln wird der gleiche Platz in der
Hashtabelle zugewiesen.
Kollisionen sind natürlich unvermeidbar, jedoch wird eine
“gute”Hashfunktion h die Anzahl der Kollisionen gering halten.
D.h. h muss die Schlüssel gleichmäßig auf die Hashtabelle
verteilen.
Außerdem sollte h einfach zu berechnen sein.
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Strategien zur Behandlung von Kollisionen
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Direkte Verkettung
k4
k4
k2
k2
k5
k5
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
worst-case Laufzeiten
insert: O(1) (neues Element vor die Liste hängen)
search: O(n) (n = Länge der Liste)
delete: O(1) (vorausgesetzt, man verwendet doppelt verkettete Listen
und hat das Element schon gefunden)
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Open Hashing
Beim Open Hashing werden alle Einträge in der Hashtabelle
gehalten. Ist eine Komponente der Tabelle schon belegt, so wird
ein freier Platz für einen weiteren Eintrag gesucht.
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Open Hashing, lineare Verschiebung
k4
k2
k5
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Lineare Verschiebung
Falls h(k) bereits durch einen anderen Schlüssel besetzt ist, wird
versucht, k in den Adressen h(k) + 1, h(k) + 2, . . . unterzubringen
Präziser gesagt, wird folgende Hashfunktion verwendet:
h0 (k, i) = h(k) + i mod m mit i = 0, 1, 2, . . . , m − 1.
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Hash-Insert mit linearer Verschiebung
Hash-Insert(T , k)
1 i ←0
2 repeat
3
j ← h0 (k, i)
4
if T [j] = NIL then
5
T [j] ← k
6
return j
7
i ←i +1
8 until i = m
9 error “hash table overflow”
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Hash-Search mit linearer Verschiebung
Hash-Search(T , k)
1 i ←0
2 repeat
3
j ← h0 (k, i)
4
if T [j] = k then
5
return j
6
i ←i +1
7 until T [j] = NIL or i = m
8 error NIL
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Quadratische Verschiebung
Es wird die Hashfunktion
h0 (k, i) = (h(k) + c1 i + c2 i 2 ) mod m
mit i = 0, 1, 2, . . . , m − 1
verwendet. Dabei sind c1 , c2 ∈ N und c2 6= 0 geeignete Konstanten
(s. Cormen et al. [2]).
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Double Hashing
Die Hashfunktion h0 wird definiert durch
h0 (k, i) = (h1 (k) + i · h2 (k)) mod m
mit i = 0, 1, 2, . . . , m − 1,
wobei h1 und h2 Hashfunktionen sind. Die Verschiebung wird dabei
durch eine zweite Hashfunktion realisiert. D.h. es wird zweimal,
also doppelt, gehasht.
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Beispiel lineare Verschiebung
0
1
0
1
0
insert 11
2
-
1
2
0
1
11
0
insert 10
-
1
2
3
3
3
4
4
4
Peter Steffen
A&D II, Vorlesung 2009
0
1
11
10
0
delete 1
-
1
2
3
0
d
11
10
search 10
-
4
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Man erkennt: Gelöschte Felder müssen markiert werden, so dass
ein Suchalgorithmus nicht abbricht, obwohl das Element doch in
der Liste gewesen wäre. Natürlich kann in die gelöschten Felder
wieder etwas eingefügt werden. Dieses Problem muss in der obigen
Implementierung zusätzlich berücksichtigt werden.
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Ladefaktor
n
Der Ladefaktor α für eine Hashtabelle T ist definiert als m
, wobei
n die Anzahl der gespeicherten Schlüssel und m die Kapazität der
Tabelle sind.
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Ladefaktor
n
Der Ladefaktor α für eine Hashtabelle T ist definiert als m
, wobei
n die Anzahl der gespeicherten Schlüssel und m die Kapazität der
Tabelle sind. Theoretische Untersuchungen und praktische
Messungen haben ergeben, dass der Ladefaktor einer Hashtabelle
den Wert 0.8 nicht überschreiten sollte (d.h. die Hashtabelle darf
höchstens zu 80% gefüllt werden). Ist der Ladefaktor ≤ 0.8, so
treten beim Suchen im Durchschnitt ≤ 3 Kollisionen auf. Bei
einem höheren Ladefaktor steigt die Zahl der Kollisionen rasch an.
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Die Klasse Hashtable in Java
Die Klasse java.util.Hashtable implementiert alle Methoden
der abstrakten Klasse java.util.Dictionary. Außerdem enthält
Hashtable noch folgende Methoden
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
public synchronized boolean containsKey(Object key)
Es wird true zurückgegeben gdw. die Hashtabelle ein Element
unter key verzeichnet hat.
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
public synchronized boolean containsKey(Object key)
Es wird true zurückgegeben gdw. die Hashtabelle ein Element
unter key verzeichnet hat.
public synchronized boolean contains(Object element)
Gdw. das angegebene element ein Element der Hashtabelle ist,
wird true zurückgegeben. Diese Operation ist teurer als die
containsKey-Methode, da Hashtabellen nur beim Suchen nach
Schlüsseln effizient sind.
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
public synchronized boolean containsKey(Object key)
Es wird true zurückgegeben gdw. die Hashtabelle ein Element
unter key verzeichnet hat.
public synchronized boolean contains(Object element)
Gdw. das angegebene element ein Element der Hashtabelle ist,
wird true zurückgegeben. Diese Operation ist teurer als die
containsKey-Methode, da Hashtabellen nur beim Suchen nach
Schlüsseln effizient sind.
public synchronized void clear()
Alle Schlüssel in der Hashtabelle werden gelöscht. Wenn es
keine Referenzen mehr auf die Elemente gibt, werden sie vom
Garbage-Collector aus dem Speicher entfernt.
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
public synchronized boolean containsKey(Object key)
Es wird true zurückgegeben gdw. die Hashtabelle ein Element
unter key verzeichnet hat.
public synchronized boolean contains(Object element)
Gdw. das angegebene element ein Element der Hashtabelle ist,
wird true zurückgegeben. Diese Operation ist teurer als die
containsKey-Methode, da Hashtabellen nur beim Suchen nach
Schlüsseln effizient sind.
public synchronized void clear()
Alle Schlüssel in der Hashtabelle werden gelöscht. Wenn es
keine Referenzen mehr auf die Elemente gibt, werden sie vom
Garbage-Collector aus dem Speicher entfernt.
public synchronized Object clone()
Es wird ein Klon der Hashtabelle erzeugt. Die Elemente und
Schlüssel selbst werden aber nicht geklont.
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Konstruktoren der Klasse Hashtable
public Hashtable()
Es wird eine neue, leere Hashtabelle mit einer voreingestellten
Anfangskapazität von 11 und einem Ladefaktor von 0.75
erzeugt.
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Konstruktoren der Klasse Hashtable
public Hashtable()
Es wird eine neue, leere Hashtabelle mit einer voreingestellten
Anfangskapazität von 11 und einem Ladefaktor von 0.75
erzeugt.
public Hashtable(int initialCapacity)
Eine neue, leere Hashtabelle mit der Anfangskapazität
initialCapacity und dem Ladefaktor 0.75 wird generiert.
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Konstruktoren der Klasse Hashtable
public Hashtable()
Es wird eine neue, leere Hashtabelle mit einer voreingestellten
Anfangskapazität von 11 und einem Ladefaktor von 0.75
erzeugt.
public Hashtable(int initialCapacity)
Eine neue, leere Hashtabelle mit der Anfangskapazität
initialCapacity und dem Ladefaktor 0.75 wird generiert.
public Hashtable(int initialCapacity, float loadFactor)
Es wird eine neue, leere Hastabelle erzeugt, die eine
Anfangskapazität der Größe initialCapacity und einen
Ladefaktor von loadFactor besitzt. Der Ladefaktor ist eine
Zahl zwischen 0.0 und 1.0 und definiert den Beginn eines
rehashings der Tabelle in eine größere.
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Beispiel (Name-Wert-Paare)
class Pair {
private String name;
private Object value;
public Pair(String name, Object value) {
this.name = name;
this.value = value;
}
public String name() {
return name;
}
public Object value() {
return value;
}
public Object value(Object newValue) {
Object oldValue = value;
value = newValue;
return oldValue;
}
}
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Interface Dic
Beispiel
interface Dic {
void add(Pair newPair);
Pair find(String pairName);
Pair delete(String pairName);
}
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
Beispiel (Implementierung von Dic)
import java.util.Hashtable;
class DicImpl implements Dic {
protected Hashtable pairTable = new Hashtable();
public void add(Pair newPair) {
pairTable.put(newPair.name(), newPair);
}
public Pair find(String name) {
return (Pair) pairTable.get(name);
}
public Pair delete(String name) {
return (Pair) pairTable.remove(name);
}
}
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld
Einführendes Beispiel
Allgemeine Definitionen
Strategien zur Behandlung von Kollisionen
Klasse Hashtable
K. Arnold, J. Gosling: JavaTM - Die Programmiersprache.
Addison-Wesley, 1996.
T.H. Cormen, C.E. Leierson, R.L. Rivest: Introduction to
Algorithms. MIT Press, 1990.
D. Flanagan: Java in a Nutshell. O’Reilly & Associates Inc.,
1996.
F. Jobst: Programmieren in Java. Hanser Verlag, 1996.
H. Klaeren: Vom Problem zum Programm. 2.Auflage,
B.G. Teubner Verlag, 1991.
K. Echtle, M. Goedicke: Lehrbuch der Programmierung mit
Java. dpunkt-Verlag, 2000.
Peter Steffen
A&D II, Vorlesung 2009
Universität Bielefeld

Download Report