Dynamisches Hashing A) Erweiterbares Hashing Aufgabe

Transcript

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