View
216
Download
0
Category
Preview:
Citation preview
Hashing
Algorithmen und Datenstrukturen II 1
Einführendes Beispiel
Ein Pizza-Lieferservice in Bielefeld speichert die Daten seiner Kunden: Name,Vorname, Adresse und Telefonnummer. Wenn ein Kunde seine Bestellungtelefonisch aufgibt, um dann mit der Pizza beliefert zu werden, dann muss er seineTelefonnummer angeben, da er über diese Nummer eindeutig identifiziert werdenkann.
Algorithmen und Datenstrukturen II 2
Telefonnummer Name Vorname PLZ Straße
00000000 Müller Heinz 33615 Unistraße 15
00000001 Schmidt Werner 33615 Grünweg 1
00000002 Schultz Hans 33602 Arndtstraße 12
. . . . . . . . . . . . . . .
99999997 Meier Franz 33609 Kirchweg 4
99999998 Neumann Herbert 33612 Jägerallee 15
99999999 Schröder Georg 33647 Mühlweg 2
Algorithmen und Datenstrukturen II 3
Bielefeld hat ca. 300.000 Einwohner, dann gibt es vielleicht 200.000Telefonnummern. Davon bestellt jeder fünfte eine Pizza – bleiben 40.000potentielle Einträge, verteilt auf mehrere Pizza-Lieferservices. Optimistisch geschätztwird unsere Pizzeria also ca. 10.000 Kunden haben.
Algorithmen und Datenstrukturen II 4
Modulo
x mod y liefert als Ergebnis den Rest der ganzzahligen Division x/y.
Beispielsweise ergibt 117 mod 20 = 17, da 117 = 5 · 20 + 17.
Algorithmen und Datenstrukturen II 5
Hash-Funktion
h(Telefonnummer) = Telefonnummer mod Tabellenlänge,
oder allgemein:
h(k) = k mod m
mit h für Hashfunktion, k für key und m für Tabellenlänge.
Algorithmen und Datenstrukturen II 6
Kollisionen
z.B. ist 01063852 mod 10000 = 08153852 mod 10000 = 3852.
Algorithmen und Datenstrukturen II 7
Allgemeine Definitionen
Formal gesehen ist Hashing ein abstrakter Datentyp, der die Operationen insert,delete und search auf (dynamischen) Mengen effizient unterstützt.
Algorithmen und Datenstrukturen II 8
Direkte Adressierung
Algorithmen und Datenstrukturen II 9
Algorithmen und Datenstrukturen II 10
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
ppppppppppppppppppppppppppppppppppppp
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
qqqq
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq qqqq
v vvv
v
v
vv v
vppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
U
2
8
5
3
0
1
2
3
4
5
7
8
9
6
1
4
0
7
6
(Universum der Schlussel)
K
T
(Aktuelle Schlussel)
9
Algorithmen und Datenstrukturen II 11
Hashing
Algorithmen und Datenstrukturen II 12
Algorithmen und Datenstrukturen II 13
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
ppppppppppppppppppppppppppppppppppppp
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
v
vqqqq
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qqqqv
vv
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
ppppppppppppppppppppppppppppppppppppppppp
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
h(k1)
h(k4)
h(k2) = h(k5)
h(k3)
(Aktuelle Schlussel)K
T
(Universum der Schlussel)U
m− 1
0
k1
k4
k3
k2k5
Algorithmen und Datenstrukturen II 14
Typische Hashfunktion
h(k) = k mod m.
Algorithmen und Datenstrukturen II 15
Strategien zur Behandlung von Kollisionen
Algorithmen und Datenstrukturen II 16
Direkte Verkettung
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
vv
v u
upppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp........................................
........................................
........................................
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqqqqqqq
k4
k5
k2k2 k5
k4
Algorithmen und Datenstrukturen II 17
worst-case Laufzeiten
insert: O(1) (neues Element vor die Liste hängen)search: O(n) (n = Länge der Liste)delete: O(1) (vorausgesetzt, man verwendet doppelt verkettete Listen und hat das
Element schon gefunden)
Algorithmen und Datenstrukturen II 18
Open Hashing
Beim Open Hashing werden alle Einträge in der Hashtabelle gehalten. Ist eineKomponente der Tabelle schon belegt, so wird ein freier Platz für einen weiterenEintrag gesucht.
Algorithmen und Datenstrukturen II 19
Open Hashing, lineare Verschiebung
...................................................................................................................................................
...................................................................................................................................................v
vvpppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp p p p p p p p p p p p p p ppppppppppppppppppppppppppppppppppppppppp
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq
qqqqqqqqqqqqqqqqqqqqqqqqqpppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
k4
k5
k2
Algorithmen und Datenstrukturen II 20
Lineare Verschiebung
Falls h(k) bereits durch einen anderen Schlüssel besetzt ist, wird versucht, k in denAdressen h(k) + 1, h(k) + 2, . . . unterzubringen (Abbildung ??). Präziser gesagt,wird folgende Hashfunktion verwendet:
h′(k, i) =(h(k) + i
)mod m mit i = 0, 1, 2, . . . ,m− 1.
Algorithmen und Datenstrukturen II 21
Hash-Insert mit linearer Verschiebung
Hash-Insert(T, k)
1 i← 02 repeat
3 j ← h′(k, i)4 if T [j] = NIL then
5 T [j]← k
6 return j
7 i← i + 18 until i = m
9 error “hash table overflow”
Algorithmen und Datenstrukturen II 22
Hash-Search mit linearer Verschiebung
Hash-Search(T, k)
1 i← 02 repeat
3 j ← h′(k, i)4 if T [j] = k then
5 return j
6 i← i + 17 until T [j] = NIL or i = m
8 error NIL
Algorithmen und Datenstrukturen II 23
Quadratische Verschiebung
Es wird die Hashfunktion
h′(k, i) = (h(k) + c1i + c2i2) mod m mit i = 0, 1, 2, . . . ,m− 1
verwendet. Dabei sind c1, c2 ∈ N und c2 6= 0 geeignete Konstanten (s. Cormen etal. [?]).
Algorithmen und Datenstrukturen II 24
Double Hashing
Die Hashfunktion h′ wird definiert durch
h′(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 einezweite Hashfunktion realisiert. D.h. es wird zweimal, also doppelt, gehasht.
Algorithmen und Datenstrukturen II 25
Beispiel lineare Verschiebung
01
0
1
2
3
4
-insert 11
01
11
0
1
2
3
4
-insert 10
01
1110
0
1
2
3
4
-delete 1
0d
1110
0
1
2
3
4
-search 10
Algorithmen und Datenstrukturen II 26
Man erkennt: Gelöschte Felder müssen markiert werden, so dass einSuchalgorithmus nicht abbricht, obwohl das Element doch in der Liste gewesenwäre. Natürlich kann in die gelöschten Felder wieder etwas eingefügt werden.Dieses Problem muss in der obigen Implementierung zusätzlich berücksichtigtwerden.
Algorithmen und Datenstrukturen II 27
Ladefaktor
Der Ladefaktor α für eine Hashtabelle T ist definiert als nm , wobei n die Anzahl der
gespeicherten Schlüssel und m die Kapazität der Tabelle sind. TheoretischeUntersuchungen und praktische Messungen haben ergeben, dass der Ladefaktoreiner Hashtabelle den Wert 0.8 nicht überschreiten sollte (d.h. die Hashtabelle darfhöchstens zu 80% gefüllt werden). Ist der Ladefaktor ≤ 0.8, so treten beim Suchenim Durchschnitt ≤ 3 Kollisionen auf. Bei einem höheren Ladefaktor steigt die Zahlder Kollisionen rasch an.
Algorithmen und Datenstrukturen II 28
Die Klasse Hashtable in Java
Die Klasse java.util.Hashtable implementiert alle Methoden der abstraktenKlasse java.util.Dictionary (vgl. Aufgabe ??). Außerdem enthält Hashtablenoch folgende Methoden
Algorithmen und Datenstrukturen II 29
public synchronized boolean containsKey(Object key)
Es wird true zurückgegeben gdw. die Hashtabelle ein Element unter keyverzeichnet hat.
public synchronized boolean contains(Object element)
Gdw. das angegebene element ein Element der Hashtabelle ist, wird true
zurückgegeben. Diese Operation ist teurer als die containsKey-Methode, daHashtabellen nur beim Suchen nach Schlüsseln effizient sind.
public synchronized void clear()Alle Schlüssel in der Hashtabelle werden gelöscht. Wenn es keine Referenzenmehr auf die Elemente gibt, werden sie vom Garbage-Collector aus demSpeicher entfernt.
Algorithmen und Datenstrukturen II 30
public synchronized Object clone()Es wird ein Klon der Hashtabelle erzeugt. Die Elemente und Schlüssel selbstwerden aber nicht geklont.
Algorithmen und Datenstrukturen II 31
Konstruktoren der Klasse Hashtable
public Hashtable()Es wird eine neue, leere Hashtabelle mit einer voreingestellten Anfangskapazitätvon 11 und einem Ladefaktor von 0.75 erzeugt.
public Hashtable(int initialCapacity)
Eine neue, leere Hashtabelle mit der Anfangskapazität initialCapacity unddem Ladefaktor 0.75 wird generiert.
public Hashtable(int initialCapacity, float loadFactor)
Es wird eine neue, leere Hastabelle erzeugt, die eine Anfangskapazität derGröße initialCapacity und einen Ladefaktor von loadFactor besitzt. DerLadefaktor ist eine Zahl zwischen 0.0 und 1.0 und definiert den Beginn einesrehashings der Tabelle in eine größere.
Algorithmen und Datenstrukturen II 32
Name-Wert-Paare
Algorithmen und Datenstrukturen II 33
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;
}
Algorithmen und Datenstrukturen II 34
public Object value(Object newValue) {
Object oldValue = value;
value = newValue;
return oldValue;
}
}
Algorithmen und Datenstrukturen II 35
Interface Dic
interface Dic {
void add(Pair newPair);
Pair find(String pairName);
Pair delete(String pairName);
}
Algorithmen und Datenstrukturen II 36
Implementierung von Dic
Algorithmen und Datenstrukturen II 37
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) {
Algorithmen und Datenstrukturen II 38
return (Pair) pairTable.remove(name);
}
}
Algorithmen und Datenstrukturen II 39
Recommended