Hashtabellen - Zusammenfassung VL PDF

Preview

Summary

Zusammenfassung VL ...

Description

Mittwoch, 27. März 2019

11 Hashtabellen Zusammenfassung ! Hashtabelle ist effektive Datenstruktur für Implementierung von Wörterbüchern. Ausgesprochen leistungsfähig. Unter vernünftigen Voraussetzungen ist die Laufzeit im Mittel für die Suche nach einem Element in einer Hashtabelle in O(1): Hashtabelle verwendet typischerweise ein Feld, dessen Grösse proportional zur Anzahl der tatsächlich gespeicherten Schlüssel ist. Kollision liegt vor, wenn mehr als ein Schlüssel auf denselben Index abgebildet wird. Datenstruktur zur effizienten Implementation der Wörterbuchoperationen: Insert, Search, Delete. Elemente enthalten Schlüssel und Satellitendaten Einfachste Lösung: Feld; Schlüssel werden als Indizes verwendet, direkter Zugriff: gegeben Schlüssel k, gesuchtes Element steht an Position k im Feld. 11.1 ADRESSTABELLEN MIT DIREKTEM ZUGRIFF

- direkte Adressierung einfache Methode, wenn Universalmenge U der Schlüssel einigermassen klein ist

- Dynamische Menge darstellen: Feld, das auch direkt adressierbare Tabelle mit T[0… m-1], jeder Slot entspricht einem Schlüssel der Universalmenge U.

Jede dieser Operationen benötigt nur Zeit O(1).

1

Mittwoch, 27. März 2019

11.2 HASHTABELLEN

Nachteil direkter Adressierung: Speicherung der Tabelle T der Grösse |U| kann unpraktikabel oder gar unmöglich sein. Wenn Menge K der Schlüssel, die in einem Wörterbuch gespeichert wird, viel kleiner ist als U der möglichen Schlüssel, dann erfordert eine Hashtabelle viel weniger Speicherplatz. Speicherverbrauch auf ! Θ(|K|) reduzieren. Vorteil: das Suchen nach einem Element in der Hashtabelle benötigt auch nur Zeit O(1). (Average Case O(1), leider nicht worst-case) Beachte aber: Diese Schranke gilt für die Zeit im Mittel. Bei der direkten Adressierung für die Zeit im schlechtesten Fall!!). Grösse der Hashtabelle ist normalerweise proportional zur Anzahl gespeicherter Elemente - und nicht zur Anzahl gespeicherter Schlüssel. Wir verwenden eine Hashfunktion h, um den Slot für den Schlüssel k zu berechnen. H bildet somit die Universalmenge U der Schlüssel in die Menge der Slots eine Hashtabelle T[0…m-1] ab: "

!h

: U → {0,1,m − 1}

Grösse m der Hashtabelle üblicherweise viel kleiner als |U|. h(k) ist der Hashwert des Schlüssels k. Das Feld hat nun Grösse m. Wenn zwei Schlüssel auf den gleichen Slot abgebildet werden, nennt man das Kollision. ! h(k1)

= h(k 2)

Fehlerbehebung: h scheinbar zufällig machen und so Kollisionen vermeiden. (h muss jedoch deterministisch sein, dass für einen gegebenen Eingabewert k immer dieselbe Ausgabe h(k) erzeugt). Kollisionen ganz zu vermeiden ist unmöglich: |U|>m - es braucht mind. Zwei Schlüssel, die den gleichen Hashwert haben. Kollisionsauflösung durch Verkettung Alle Elemente, die auf den gleichen Slot abgebildet werden, werden bei der Verkettung in eine verkettete Liste gespeichert. Bsp. Slot j enthält einen Zeiger auf den Kopf der Liste aller gespeicherten Elemente, die auf j abgebildet werden. Gibt es keine solche Elemente, so enthält Slot j den Wert NIL. Listen enthalten Elemente mit gleichem Hashwert.

2

Mittwoch, 27. März 2019

Worst Case Laufzeit O(1). Unter Annahme, dass Schlüssel nicht schon existiert in Hashtabelle. Sonst muss zusätzlich mittels Suchen geprüft werden, ob der Schlüssel schon in der Liste vorkommt. Keine Suche nötig, wenn Zeiger auf Element x gegeben ist. Worst -Case Laufzeit mit doppelt verketteten Listen ist O(1). Einfach verkettete Listen erfordern Traversieren wie beim Suchen (brauchen Vorgänger von x um dessen next Zeiger anzupassen). Chained-Hash-Search(T,k) 1 suche in der Liste T[h(k)] nach einem Element mit dem Schlüssel k

Gegeben Schlüssel, was ist der Aufwand, um Element mit dem Schlüssel zu finden, oder zu entscheiden, dass Schlüssel nicht existiert? Abhängig vom Belegungsfaktor! Siehe unten. Analyse des Hashings mit Verkettung Zu einer gegebenen Hashtabelle T mit m Slots, die n Elemente speichert, definieren wie den Belegungsfaktor ! α als n/m, Anzahl Elemente in Hashtabelle n, Grösse der Hashtabelle m, d.h. als die mittlere Anzahl der Elemente, die in einer Kette der Hashtabelle gespeichert sind. !α kann kleiner, gleich oder grösser als 1 sein. Worst Case: Die Zeit für das Suchen ist im schlechtesten Fall ! Θ(n) zzgl. Der Zeit für die Berechnung der Hashfunktion. Alle n Schlüssel belegen den gleichen Slot. Eine Liste der Länge n. Die mittlere Laufzeit hängt davon ab, wie gut die Hashfunktion h die Menge der zu Speicherenden Schlüssel im Mittel auf die m Slots verteilt. Voraussetzung: jedes beliebige element mit gleicher Warhcheinlichkeit und unabhängig von den anderen Elementen auf einen der m Slots abgebildet wird. —> einfaches gleichmässiges Hashing. Annahme: Hashfunktion h berechnet in konstanter Zeit. Theorem 11.1 In einer Hashtabelle, in der Kollisionen durch Verkettung aufgelöst werden, benötigt eine erfolglose Suche (Hashtabelle enthält gesuchten Schlüssel nicht) unter der Annahme des einfachen gleichmässigen Hastings eine Laufzeit im Mittel von ! Θ(1+!α).

3

Mittwoch, 27. März 2019

Theorem 11.2 In einer Hashtabelle, Inder Kollisionen durch Verkettung aufgelöst werden, benötigt eine erfolgreiche Suche unter der Annahme des einfachen gleichmässigen Hastings eine Laufzeit im Mittel von ! Θ(1+! α). (Beweis in der Vorlesung mittels Erwartungswert.) Die Suche benötigt also im Mittel konstante Zeit.

11.3 HASHFUNKTIONEN

Was macht eine gute Hashfunktion aus? Jeder Schlüssel wird mit der gleichen Wahrscheinlichkeit auf einen der m Slots abgeildet, unabhängig davon, wie irgendein anderer Schlüssel abgebildet wurde. Ein guter Ansatz leitet den Hashwert in einer Weise ab, von dem wir erwarten können, dass dieser unabhängig von jeglichen Mustern ist, die möglicherweise in den Daten existieren. Die Schlüssel ls natürlicher Zahlen interpretieren Die meisten Hashfunktionen setzten voraus, dass die Universalmenge der Schlüssel die natürlichen Zahle bildet. Wenn sie keine natürlichen Zahlen sind, dann müssen wir sie als ebendiese interpretieren. (ASCII-Zeichenansatz). Die Divisionsmethode Bei der Divisionsmethode zum Erzeugen von Hashfunktionen bilden wir einen Schlüssel k auf einen von m Schlüsseln ab, indem wir k durch m teilen und den Rest dieser Division als Hashwert nehmen. Die Hashfunktion lautet also ! h(k)

= k mod m .

Nur eine einzige Division erforderlich, ist das Hashing recht schnell. Eine Primzahl, welche nicht zu nahe an einer Potenz von 2 liegt, ist oftmals eine gute Wahl für m. Beispiel: Hashtabelle anlegen, um ungefähr n = 2000 Zeichenketten abzulegen, wobei ein Zeichen aus 8 bit besteht, und in der Kollisionen durch Verkettung aufgelöst werden. Daher legen wir eine Hashtabelle der Grösser m = 701 an. 701 ist in der Nähe von 2000/3, jedoch nicht in der Nähe irgendeiner Potenz von 2. ! h(k)

= k mod 701 . (Siehe Bild S. 266 in Kap11).

Die Multiplikationsmethode

4

Mittwoch, 27. März 2019

2 Schritte: 1. Multiplizieren wir den Schlüssel k mit einer Konstanten A aus dem Bereich 0 < A < 1 und extrahieren den gebrochenen Teil von kA. 2. Dieser Wert wird mit m multipliziert und das abgerundete Ergebnis wird ausgewählt. …. 11.4 OFFENE ADRESSIERUNG

Offene Adressierung bedeutet, alle Elemente in der Hastabelle werden direkt gespeichert. Jeder Tabelleneintrag enthält also entweder ein Element der dynamischen Menge oder NIL. Bei der Suche nach Element, überprüfen wir systematisch die Tabellenslots, bis wir entweder das Element gefunden haben oder wir uns davon überzeugt haben, dass das Element nicht in der Tabelle gespeichert ist. Bei offener Adressierung kann sich die Tabelle „füllen“, bis schliesslich keine weiteren Einfügeoperationen mehr ausgeführt werden können. Belegungsfaktor α ! kann daher nie grösser als 1 ein. Zeiger werden vermeidet in der offenen Adressierung. Wir berechnen die Folge der Slots, die zu überprüfen sind. ! →zusätzlicher Speicher wird somit gewonnen, ermöglicht für die Hashtabelle eine grössere Anzahl von Slots bei gleicher Speichergrösse, potentiell weniger Kollisionen und schnelleres Wiederauffinden der Daten. Einfügen mithilfe offener Adressierung: Hashtabelle sukzessive überprüfen oder sondieren, bis wir leeren Slot finden, wo wir Schlüssel speichern können. Die Reihenfolge, in der wir die Slots besuchen, hängt von dem einzufügenden Schlüssel ab. Um Slots zu bestimmen, erweitern wir die Hashfunktion um einen zusätzlichen Eingabeparameter, übern den eine Sondierungszahl (mit 0 beginnend) übergeben wird. Die Hashfunktion wird damit zu "

"

"

!h

: U × {0,1,…, m − 1} → {0,1,…m − 1}

Bei der offenen Adressierung fordern wir, dass die Sondierungssequenz ⟨h(k,0), h (k,1), …, h (k, m

− 1)⟩

Für jeden schlüssel k eine Permutation von !⟨0,1,…m

− 1⟩ ist, sodass letztendlich

jede Position der Hashtablle als Slot für einen neuen Schlüssel berücksichtigt wird, wenn die Tabelle sich füllt. Hash-Insert hat als Eingangsparameter eine Hashtabelle T und einen Schlüssel k. Gibt Nummer des Slots zurück, ind das sie den Schlüssel k speichert, oder setzt einen Fehlerflag, um anzuzeigen, dass die Hashtabelle bereits voll ist. 5

Mittwoch, 27. März 2019

Die Suche kann erfolglos abbrechen, wenn ein leerer Slot gefunden wird, denn k wäre an dieser Stelle, und nicht weiter hinten, in der Sondierungssequenz einfügt worden.

Entfernen eines Elements aus einer Tabelle mit offener Adressierung ist schwierig. Verkettung als Methode zur Kollisionsauflösung gewählt, wenn Schlüssel entfernt werden müssen. Bei unserer Analyse setzen wir gleichmässiges Hashing voraus: Jede der m! Permutationen von (0, 1, …m-1) ist mit gleicher Wahrscheinlichkeit die Sondierungssequenz eines Schlüssels.

Lineares Sondieren Zu einer gegebenen normalen Hashfunktion h′ ! :

U → {0,1,…m − 1} , die wir als

Hilfshashfunktion bezeichnen wollen, verwendet die Methode des linearen Sondieren

i) die Hashfunktion h(k, !

= (h′( k) + i ) mod m (i = 0, 1, …m-1).

Zu einem gegebenen Schlüssel k sondieren wir zuerst T ! [h′( k)], d.h. denjenigen Slot, der durch die Hilfshashfunktion vorgegeben wird. Dann !T [h′( k) + 1] bis zum Slot T[m-1], um dann zu den Slots T[0],T[1] bis T[h’(k) -1] erreicht ist. Es gibt nur m verschiedenen Sondierungsseqenzen. Problem: primäres Clustern. Bilden sich lange Folgen besetzter Slots, wodurch sich die Suchzeit erhöht. Cluster entstehen, weil ein leerer Slot, der auf i besetzte Slots folgt, mit der Wahrscheinlichkeit (i+1)/m als nächstes belegt wird. Lange Folgen besetzter Slots haben daher die Tendenz, noch länger zu werden, wodurch sich die mittlere Suchzeit erhöht. Hohe durchschnittliche Suchzeit.

6

Mittwoch, 27. März 2019

Quadratisches Sondieren Beim quadratischen Sondieren verwenden wir eine Hashfunktion der Form : ! h(k, i ) = (h′( k) + c1i + c2i 2) mod m Wobei h’ eine Hilfshasfunktion ist und c ! 1, c2 positive HIlfskonstanten. Dieses Verfahren arbeitet wesentlich besser als lineares Sondieren. Zwei Sondierungssequenzen sind gleich, wenn die Anfangsslots die gleichen sind. Diese Eigenschaft führt zu einer abgeschwächten Form der Clusterbildung, die als sekundäres Clustern bezeichnet wird.

Doppeltes Hashing Eine der besten für offene Adressierung verfügbaren Verfahren, da die erzeugten Permutationen viele Charakteristika zufällig ausgewählter Permutationen aufweisen. !h(k, i )

= (h1(k) + ih 2(k)) mod m

Wobei h ! 1, h 2 Hilfshashfunktionen sind. Sondierungsseqenze hängt in zweifacher Hinsicht vom Schlüssel k ab, da die Anfangsposition, die Verschiebung oder beide variieren können. Der Wert h! 2(k) muss teilerfremd zur Länge m der Hashtabelle sein, damit die gesamte Hashtabelle durchsucht wird. Wähle somit m als Potenz von 2 und die Funktion h ! 2 so konstruieren, dass sie immer eine ungerade Zahl erzeugt. Andere Möglichkeit: h ! 2 so wählen, dass sie immer eine positive ganze Zahl kleiner als m ergibt. Wenn m eine Primzahl oder eine Potenz von 2 ist, dann ist doppeltes Hashing gegenüber linearem oder quadratischem in der Hinsicht besser, dass Θ( ! m 2) Sondierungssequenzen verwendet werden, anstatt nur Θ(m) ! , denn jedes mögliche Paar liefert eine andere Sondierungssequenz.

7

Mittwoch, 27. März 2019

Analyse des Hastings mit offener Adressierung Für eine Hashtabelle mit offener Adressierung und dem Belegungsfaktor ! = n /m < 1 ist unter der Voraussetzung gleichmässigen Hashings die Anzahl der α Sondierungen bei einer erfolglosen Suche höchstens ! 1/(1 − α). Das Einfügen eines Elements in einer Hashtabelle mit offener Adressierung mit dem Belegungsfaktor α ! erfordert unter der Voraussetzung gleichmässigen Hastings im Mittel höchstens ! 1/(1 − α) Sondierungen. Für eine Hashtabelle mit offener Adressierung und dem Belegungsfaktor α ! ist die erwartete Anzahl der Sondierungen bei einer erfolgreichen Suche unter Voraussetzung

!

gleichmässigen Hashings höchstens

1 1 wenn vorausgesetzt wird, dass nach jedem Schlüssel mit der gleichen ln α (1 − α) Wahrscheinlichkeit gesucht wird.

11.5 PERFEKTES HASHING

Hashing kann auch ein exzellentes Verhalten im schlechtesten Fall vorweisen, wenn die Menge der Schlüssel statisch ist: sind die sChlüssel einmal in der Tabelle gespeichert, so verändert sich die Menge der Schlüssel nie mehr. Wir bezeichnen ein Hashverfahren als perfektes Hashing, wenn im schlechtesten Fall O(1) viele Speicherzugriffe zum Suchen notwendig sind. Theorem 11.9 Nehmen Sie an, wir würden n Schlüssel in eine Hashtabelle der Grösse m !

= n 2 unter

Verwendung einer zufällig aus einer universellen Klasse von Hashfunktionen ausgewählten Funktion h speichern. Dann ist die Wahrscheinlichkeit, dass eine Kollision vorkommen kann, kleiner als 1/2.

8

Mittwoch, 27. März 2019

ZUSAMMENFASSUNG

• Wörterbuchoperationen Insert, Search, Delete • Hastabelle T[0,1,…m-1] ‣ Anzahl Elemente 1 möglich

• Einfügen O(1) • Löschen O(1) unter gew. Voraussetzungen • Suchen: ! n) ‣ WorstCase: Θ(

+ α) ! ‣ AverageCase: Θ(1 • Offene Adressierung • T[k] enthält Schlüssel • Belegungsfaktor ! α

≤1

• Suche freie Plätze durch Sondierung h(k, i) • Idealfall: gleichmässiges Hashing. Erwartete Anzahl Sondierungen: ‣ Einfügen und erfolglose Suche: ! ‣ Erfolgreiche Suche: !

≤

≤

1 1−α

1 1 ln α 1−α

• Sondierungsmethoden ! ‣ Lineares Sondieren: h(k)

= (h′( k) + i )modm

! i) ‣ Quadratisches Sondieren h(k, ‣ Doppeltes Hashing ! h(k, i )

= (h′( k) + c1i + c2i 2) mod m

! = (h1(k) + ih 2(k)) mod m wobei ! h 2(k) tellerfremd zu m

• Hashfunktion ! ‣ Divisionsmethode: h(k)

= k mod m schnell, gewisse Werte von m ungünstig.

! = ⌊m(k A ‣ Multiplikationsmethode: h(k) langsamer als Divisionsmethode ‣ 9

mod m)⌋ Wert von m nicht kritisch,...