Dynamisches Hashing a) Erweiterbares Hashing Aufgabe

Algorithmen und Datenstrukturen 2
Seminar
Thomas Wittig
Dynamisches Hashing
a) Erweiterbares Hashing
Aufgabe:
In einen anfangs leeren Hashbereich sollen folgende Schlüssel mittels Erweiterbarem
Hashing eingefügt werden:
Elbe, Ilse, Mulde, Parthe, Saale, Spree, Unstrut
Die Bucketgröße betrage 3. Die globale Tiefe des Digitalbaumes (bzw. Indexes) beträgt
anfangs 0 Bit. Es soll mit einem einzigen Bucket begonnen werden.
Lösung:
Umwandlung der Zeichenketten der Schlüssel in Zahlen/Bitfolgen
z.B.:
- von jedem Schlüssel wird erster Buchstabe genommen und
- dessen Nummer im Alphabet mit 5 Bits kodiert.
Elbe
Ilse
Mulde
Parthe
Saale
Spree
Unstrut
=
=
=
=
=
=
=
00101
01001
01101
10000
10011
10011
10101
Anfangssituation: Index mit 0 Bit
keine Unterscheidung zwischen Schlüsseln
alle Schlüssel k im gleichen Bucket
Schlüsselanfang Index
*
Buckets
(leer)
h(k) = *
Buckets
Elbe
h(k) = *
Buckets
Elbe, Ilse
h(k) = *
Buckets
Elbe, Ilse, Mulde
h(k) = *
nach Einfügen von Elbe:
Schlüsselanfang Index
*
nach Einfügen von Ilse:
Schlüsselanfang Index
*
nach Einfügen von Mulde:
Schlüsselanfang Index
*
Einfügen von Parthe:
Schlüsselanfang Index
Buckets
Elbe, Ilse, Mulde, Parthe
*
h(k) = *
Bucket übergelaufen
Bucket splitten
Schlüssel des Buckets unterscheiden sich im 1. Bit das erste mal voneinander
Index erweitern auf 1 Bit
Seminar 2
1
dynamische Hashverfahren
Algorithmen und Datenstrukturen 2
Seminar
Thomas Wittig
nach Einfügen von Parthe:
Schlüsselanfang Index
0
1
Buckets
Elbe, Ilse, Mulde
Parthe
h(k) = 0*
h(k) = 1*
Buckets
Elbe, Ilse, Mulde
Parthe, Saale
h(k) = 0*
h(k) = 1*
Buckets
Elbe, Ilse, Mulde
Parthe, Saale, Spree
h(k) = 0*
h(k) = 1*
nach Einfügen von Saale:
Schlüsselanfang Index
0
1
nach Einfügen von Spree:
Schlüsselanfang Index
0
1
Einfügen von Unstrut:
Schlüsselanfang Index
0
1
Buckets
Elbe, Ilse, Mulde
Parthe, Saale, Spree,
Unstrut
h(k) = 0*
h(k) = 1*
Bucket übergelaufen
Bucket splitten
Schlüssel des Buckets unterscheiden sich im 3. Bit das erste mal voneinander
Index erweitern auf 3 Bit
nach Einfügen von Unstrut:
Schlüsselanfang Index
000
001
010
011
100
101
110
111
Buckets
Elbe, Ilse, Mulde
h(k) = 0*
Parthe, Saale, Spree
Unstrut
(leer)
h(k) = 100*
h(k) = 101*
h(k) = 11*
Bemerkungen:
a) Schlüsselanfang = Adresse in der Indextabelle
also: 000* Adresse 0
001*
Adresse 1
...
111* Adresse 7
b) Oberstes Bucket bleibt unverändert. Es enthielt/enthält alle Schlüssel k mit h(k) = 0...
Damit müssen auch im neuen Index alle Einträge von Schlüsseln, die mit 0 beginnen,
auf dieses eine Bucket verweisen.
c) Das zweite und dritte Bucket enthalten jeweils Schlüssel, die mit 10 beginnen. Schlüssel,
die mit 11 beginnen, dürfen nicht in diesen Buckets abgespeichert werden. Für solche
Schlüssel ist ein eigenes, noch leeres Bucket anzulegen.
Seminar 2
2
dynamische Hashverfahren
Algorithmen und Datenstrukturen 2
Seminar
Thomas Wittig
zu c) Was wäre wenn...
- Werden als nächstes ein Schlüssel mit 110* sowie ein Schlüssel mit 111*
eingefügt, kommen nun beide in das gleiche, vorher leere Bucket.
- Würde man, anstatt ein leeres Bucket zu erzeugen, die Referenzen im Index von
den Adressen 6 (=110) und 7 (=111) einfach auf ‚null’ setzen, und fügt man jetzt
einen Schlüssel mit 110* sowie einen Schlüssel mit 111* ein, lässt sich nur
schwer nachvollziehen, daß diese in ein gemeinsames Bucket gehören.
(Bei Darstellung des Indexes als Digitalbaum soll gelten, dass die Digitalbaumadressierung abbricht, sobald ein Bucket den ganzen Teilbaum aufnehmen kann.
Dies wäre bereits bei 11* gegeben, da nur 2 Schlüssel in diesem Teilbaum
existieren.)
verwendete Strategien:
- Dynamik von B-Bäumen (Split-/Mischoperationen): vgl. Bsp. oben
- Adressierungstechnik von Digitalbäumen: obiges Beispiel entspricht
*
*
Elbe
Elbe
Ilse
Mulde
...
0
1
0*
1*
Elbe
Ilse
Mulde
...
0
0*
1
0
1*
Elbe
Ilse
Mulde
Parthe
1
0*
Parthe
Saale
Spree
Elbe
Ilse
Mulde
0
0
100*
Parthe
Saale
Spree
-
1
1
11*
101*
Unstrut
Hashing: gestreute Speicherung mit möglichst gleichmäßiger Werteverteilung
im obigen Beispiel ??
⇒ vorherige Schlüsseltransformation (durch Hashfunktion) verteilt die Daten besser
im Beispiel etwa h(k) = k-1
⇒ kleinerer Index, weniger Speicherverbrauch
Seminar 2
3
dynamische Hashverfahren
Algorithmen und Datenstrukturen 2
Seminar
Thomas Wittig
b) Lineares Hashing
Aufgabe:
In einen anfangs leeren Hashbereich sollen folgende Schlüssel mittels Linearem Hashing
eingefügt werden:
Elbe, Ilse, Mulde, Parthe, Saale, Spree, Unstrut, Fulda,
Bode, Lippe, Havel, Chemnitz, Ilm, Oder, Ucker
Parameter:
- max. 3 Datensätze pro Bucket
- Schwellwert für Belegungsfaktor = 0,8
- m=3
- Folge der Hashfunktionen sei durch hj(k) = k mod m*2j bestimmt
Lösung:
Umwandlung der Zeichenketten der Schlüssel in Zahlen/Bitfolgen
z.B.:
- von jedem Schlüssel wird erster Buchstabe genommen und dessen Nummer im Alphabet
betrachtet
Elbe
Ilse
Mulde
Parthe
Saale
Spree
Unstrut
=
=
=
=
=
=
=
5
9
13
16
19
19
21
Fulda
Bode
Lippe
Havel
Chemnitz
Ilm
Oder
=
=
=
=
=
=
=
6
2
12
8
3
9
15
Ucker
= 21
Anfangssituation:
L = 0 Anzahl Verdopplungen des Hashbereiches
p = 0 nächstes zu splittendes Bucket
h(k) = hL(k) = h0(k) = k mod 3*20 = k mod 3
0
1
2
0
Ilse
1
2
Mulde Elbe
Parthe
Saale
β = 5/9
⇒
β = 0/9
h(Spree) = hL(Spree) = h0(Spree) = 19 mod 3 = 1
⇒ voll
⇒ in Überlaufbereich
0
Ilse
Seminar 2
1
2
0
Mulde Elbe
Parthe
Saale
β = 6/9
↓
Spree
⇒
4
1
2
Ilse
Mulde Elbe
Unstrut Parthe
Fulda Saale
↓
β = 8/9
Spree
dynamische Hashverfahren
Algorithmen und Datenstrukturen 2
Seminar
Thomas Wittig
β > 0,8; p = 0; L = 0
⇒ Bucket 0 splitten
⇒ neues Bucket anfügen
⇒ Schlüssel verteilen mit h(k) = hL+1(k) = h1(k) = k mod 3*21 = k mod 6
⇒ p = p+1 = 1
h(Ilse) = hL+1(Ilse) = h1(Ilse) = 9 mod 3*21 = 9 mod 6 = 3
h(Unstrut) = hL+1(Unstrut) = 21 mod 6 = 3
h(Fulda) = hL+1(Fulda) = 6 mod 6 = 0
0
1
2
Mulde Elbe
Parthe
Saale
↓
Spree
Fulda
3
Ilse
Unstrut
β = 8/12
h(Bode) = hL(Bode) = h0(Bode) = 2 mod 3 = 2 ≥ p ⇒ ok
h(Lippe) = hL(Lippe) = h0(Lippe) = 12 mod 3 = 0 < p ⇒ gesplitteter Bucket
⇒ h(Lippe) = hL+1(Lippe) = h1(Lippe) = 12 mod 3*21 = 12 mod 6 = 0
0
Fulda
Lippe
1
2
Mulde Elbe
Parthe Bode
Saale
↓
Spree
3
Ilse
Unstrut
β = 10/12
β > 0,8; p = 1; L = 0
⇒ Bucket 1 splitten
⇒ neues Bucket anfügen
⇒ Schlüssel verteilen mit h(k) = hL+1(k) = h1(k) = k mod 3*21 = k mod 6
⇒ p = p+1 = 2
h(Mulde) = hL+1(Mulde) = h1(Mulde) = 13 mod 3*21 = 13 mod 6 = 1
h(Parthe) = hL+1(Parthe) = 16 mod 6 = 4
h(Saale) = hL+1(Saale) = 19 mod 6 = 1
h(Spree) = hL+1(Spree) = 19 mod 6 = 1
0
Fulda
Lippe
1
2
Mulde Elbe
Saale Bode
Spree
3
4
Ilse
Parthe
Unstrut
β = 10/15
Seminar 2
5
dynamische Hashverfahren
Algorithmen und Datenstrukturen 2
Seminar
Thomas Wittig
h(Havel) = hL(Havel) = h0(Havel) = 8 mod 3 = 2 ≥ p ⇒ ok
h(Chemnitz) = hL(Chemnitz) = h0(Chemnitz) = 3 mod 3 = 0 < p ⇒ gesplitteter Bucket
⇒ h(Chemnitz) = hL+1(Chemnitz) = h1(Chemnitz) = 3 mod 3*21 = 3 mod 6 = 3
h(Ilm) = hL(Ilm) = h0(Ilm) = 9 mod 3 = 0 < p ⇒ gesplitteter Bucket
⇒ h(Ilm) = hL+1(Ilm) = h1(Ilm) = 9 mod 3*21 = 9 mod 6 = 3
0
Fulda
Lippe
1
Mulde
Saale
Spree
2
Elbe
Bode
Havel
3
4
Ilse
Parthe
Unstrut
Chemnitz
↓
β = 13/15
Ilm
β > 0,8; p = 2; L = 0
⇒ Bucket 2 splitten
⇒ neues Bucket anfügen
⇒ Schlüssel verteilen mit h(k) = hL+1(k) = h1(k) = k mod 3*21 = k mod 6
⇒ p = p+1 = 3
h(Elbe) = hL+1(Elbe) = h1(Elbe) = 5 mod 3*21 = 5 mod 6 = 5
h(Bode) = hL+1(Bode) = 2 mod 6 = 2
h(Havel) = hL+1(Havel) = 8 mod 6 = 2
1
0
Fulda
Lippe
Mulde
Saale
Spree
2
3
4
Ilse
Parthe
Unstrut
Chemnitz
↓
Ilm
Bode
Havel
5
Elbe
β = 13/18
p = m * 2L ⇒ vollständige Verdopplung des Hashbereichs
⇒ p = 0; nächstes zu splittendes Bucket = 0
⇒ L = L+1 = 1
h(Ucker) = hL(Ucker) = h1(Ucker) = 21 mod 3*21 = 21 mod 6 = 3 ≥ p ⇒ ok
0
Fulda
Lippe
Seminar 2
1
Mulde
Saale
Spree
2
Bode
Havel
3
Ilse
Parthe
Unstrut
Chemnitz
↓
Ilm
Ucker
6
4
5
Elbe
β = 14/18
dynamische Hashverfahren

Download Report