9 Hash-Tabellen - TU Bergakademie Freibergernst/Lehre/AD/Folien/adKapitel9.pdf · Algorithmen und...

Algorithmen und Datenstrukturen 213

9 Hash-Tabellen

Viele Anwendungen erfordern dynamische Mengen, fur welche die sog.Worterbuch-Operationen INSERT, SEARCH und DELETE verfugbar sind.Beispiel: Symboltabelle in einem Compiler.

Eine Hash-Tabelle ist eine effiziente Datenstruktur zur Implementierungvon Worterbuchern (dictionaries).

• Die mittlere Zeit zum Auffinden eines Elements in einer Hash-Tabellebetragt, unter realistischen Annahmen, O(1).

• Im ungunstigsten Fall betragt sie jedoch O(n) (bei n Elementen).

9 Hash-Tabellen TU Bergakademie Freiberg, WS 2005/06


Eine Hash-Tabelle ist eine Verallgemeinerung eines gewohnlichen Feldes.

• Gewohnliches Feld: Element mit Schlussel k wird an Position k gespei-chert.

• Um ein Element mit Schlussel k wieder aufzufinden, muss lediglich anPosition k des Feldes nachgeschaut werden; man nennt dies direkteAdressierung.

• Direkte Adressierung kann immer dann eingesetzt werden, wenn derSpeicherbedarf eines Feldes – mit einem Eintrag fur jeden moglichenSchlussel – akzeptabel ist.



Eine Hash-Tabelle wird dagegen eingesetzt, wenn dieser Aufwand zu großist:

• Einsatz einer Hash-Tabelle ist dann angesagt, wenn die Anzahl dertatsachlich auftretenden Schlussel klein ist im Vergleich zu der dermoglichen Schlussel.

• Eine Hash-Tabelle ist ein Feld, dessen Speicherbedarf proportionalzur Anzahl tatsachlich gespeicherter Schlussel ist (anstelle der Anzahlmoglicher Schlussel).

• Bei gegebenem Schlussel k wird nicht einfach k als Feldindex verwen-det; der Index ergibt sich stattdessen aus einer Funktion angewandtauf k, der Hash-Funktion.



Themen dieses Kapitels:

• Entwurf geeigneter Hash-Funktionen (Multiplikations- und Divisions-verfahren)

• Kollisionsauflosung, d.h. geeignete Maßnahmen fur den Fall, dass dieHash-Funktion mehrere Schlussel auf denselben Feldindex abbildet(Chaining, offene Adressierung).



9.1 Tabellen mit direkter Adressierung

• Jedes Element besitzt einen Schlussel aus einer Grundmenge G ={0, 1, . . . ,m− 1}, wobei m nicht zu groß ist.

• Verschiedene Elemente besitzen verschiedene Schlussel.

• Fur Menge K tatsachlich auftretender Schlussel gilt |K| ≈ |G|.

Direkt-adressierte Tabelle implementiert durch Feld T [0 . . m− 1]:

• Jede Position entspricht einem Schlussel aus G

• Ist ein Element x mit Schlussel k vorhanden, so enthahlt T [k] einenZeiger auf x.

• Andernfalls ist T [k] unbesetzt, was durch den Wert NIL dargestellt wird.

9.1 Tabellen mit direkter Adressierung TU Bergakademie Freiberg, WS 2005/06


5

1

0

2

3

4

6

7

8

9

Schluessel

Nutzdaten

T

/

/

2

3

5

8

9

4

07

6

G (Grundmenge)

1

/

/

/

/5Schluessel)3

8

2(auftretende

K

Realisierung eines Worterbuchs durch eine direkt-adressierte Tabelle T . Jeder Schlussel der

Grundmenge G entspricht einem Index in die Tabelle. Die Menge auftretendender Schlussel

K bestimmt die Positionen von T , an denen Zeiger auf Elemente stehen.



Grundoperationen (allesamt O(1))

DIRECT-ADDRESS-SEARCH(T, k)

return T [k]

DIRECT-ADDRESS-INSERT(T, x)

T [key [x]]← x

DIRECT-ADDRESS-DELETE(T, x)

T [key [x]]← NIL



9.2 Hash-Tabellen

Betrachte nun Fall |G| sehr groß, aber |K| � |G|.

• In diesem Fall beansprucht eine Hash-Tabelle wesentlich weniger Spei-cherplatz, im Wesentlichen Θ(|K|).

• Suchzeit noch O(1) im Mittel, aber nicht mehr im ungunstigsten Fall.

Idee: Element mit Schlussel k wird nicht an Position k gespeichert, sondernan Position h(k) mit einer geeigneten Funktion h.

• h heißt Hash-Funktion.

• h : G → {0, 1, . . . ,m − 1}, d.h. fur alle k ∈ G ist h(k) eine zulassigePosition in T (T heißt jetzt Hash-Tabelle).

• Sprechweisen:”k wird nach Position h(k) gehasht“,

”h(k) ist der Hash-

Wert von k“.

9.2 Hash-Tabellen TU Bergakademie Freiberg, WS 2005/06


Kollision: mehrere Schlussel werden auf dieselbe Position gehasht (hnicht injektiv).

• moglich sobald |G| > m

• fur gegebene Schlusselmenge K mit |K| ≤ m ebenfalls moglich, trittsicherlich auf falls |K| > m

• Daher Strategie zur Kollisionsauflosung in allen Fallen erforderlich.

• Zwei Verfahren: Chaining und offene Adressierung (Chaining meistensbesser)

• Je besser die Hash-Funktion, desto seltener muß auf Kollisions-auflosung zuruckgegriffen werden.



h(k4)

0

T

m− 1

h(k3)

h(k2) = h(k5)

h(k1)

G (Grundmenge)

k1

k5

k2

k3

K

Schluessel)(auftretende

k4

Abbildung von Schlusseln nach Hash-Positionen. Die Schlussel k2 und k5 werden auf dieselbe

Position abgebildet, d.h. hier tritt eine Kollision auf.



9.2.1 Kollisionsaufl osung durch Chaining

Idee: Alle Elemente mit demselben Hash-Wert werden in einer verkettetenListe gehalten.

T

k5

k6 /

G (Grundmenge)/

/

/

/

/

/

k1 k4

k2 k7

k3

k8

/

/

/Schluessel)

k1

k2k3

k8k6

k7K

(auftretende

k4 k5



• Im der Abbildung werden einfach verkettete Listen verwendet; umElemente schnell loschen zu konnen sollte die Verkettung doppeltsein. (Dabei wird angenommen, dass die Loschprozedur einen Zeigerauf das zu loschende Element erhalt.)

• Position j der Hash-Tabelle enthalt einen Zeiger auf den Kopf der Listealler Elemente mit Hash-Wert j. (NIL, falls diese leer)

• Einfugen:

CHAINED-HASH-INSERT(T, x)

fuge x am Kopf der Liste T [h(key [x])] ein

◦ Worst-Case-Laufzeit ist O(1).

◦ Annahme: einzufugendes Element noch nicht in der Liste enthalten.

◦ Uberprufung dieser Annahme erfordert zusatzliches Suchen.



• Suchen:

CHAINED-HASH-SEARCH(T, k)

Suche Element mit Schlussel k in Liste T [h(k)]

Laufzeit proportional zu Lange der Liste an Position h(k).

• Loschen:

CHAINED-HASH-DELETE(T, x)

Losche x aus der Liste T [h(key [x])]

◦ Prozedur erhalt Zeiger auf zu loschendes Element x, daher keinSuchen erforderlich.

◦ Worst-Case-Laufzeit O(1) bei doppelt verketteten Listen

◦ Bei einfach verketteten Listen dauert Loschen so lange wir Suchen,da zur Aktualisierung der Verzeigerung zunachst der Vorganger vonx bestimmt werden muss.



9.2.2 Analyse von Hashen mit Chaining

Frage: wie lange dauert das Auffinden eines Elementes mit gegebenemSchlussel bzw. die Feststellung, ob ein solches Element vorhanden ist ?

• Analyse benutzt Begriff des Lastfaktors (load factor) α := n/m

(mittlere # Elemente pro Liste)

◦ n: # Elemente in der Tabelle

◦ m: # Positionen in der Tabelle= # (moglicherweise leerer) verketteter Listen

◦ α < 1, = 1 oder > 1 moglich

• Ungunstigster Fall: alle n Schlussel auf dieselbe Position abgebildet,d.h. eine verkettete Liste der Lange n ⇒ Worst-Case Laufzeit furSuchen ist Θ(n) plus Zeit fur Auswertung von h.

• Durchschnittlicher Aufwand hangt davon ab, wie gleichmaßig h dieSchlussel verteilt.



Wir betrachten den durchschnittlichen Aufwand von Hashen mit Chaining.

• Annahme: jedes Element wird mit gleicher Wahrscheinlichkeit in einesder m Positionen gehasht (einfaches, gleichmaßiges Hashen)

• Sei nj die Lange der Liste T [j], j = 0, . . . ,m−1, d.h. n = n0+· · ·+nm−1.

• Erwartungswert von nj gegeben durch E[nj ] = n/m = α.

• Annahme: Auswertung von h in O(1) Zeit moglich, d.h. Laufzeit furSuchen des Elements mit Schlussel k hangt ab von nh(k).

Zwei Falle:

• Hash-Tabelle enthalt kein Element mit Schlussel k, also Suche erfolglos

• Andernfalls Suche erfolgreich

In den folgenden Aussagen sei stets einfaches, gleichmaßiges Hashen mitKollisionsauflosung durch Chaining vorausgesetzt.



Erfolglose Suche:

Satz 9.1 In einer Hash-Tabelle mit Kollosionsauflosung durch Chainingbetragt der Erwartungswert der Laufzeit einer erfolglosen Suche Θ(1 + α).

Beweis: Ein noch nicht enthaltener Schlussel wird mit gleicher Wahrschein-lichkeit in eine der m Listen gehasht.

Erfolglose Suche nach Schlussel k erfordert vollstandiges Durchsuchenvon Liste T [h(k)]. Diese besitzt erwartete Lange E[nh(k)] = α. Somitbetragt die erwartete Anzahl bei einer erfolglosen Suche zu prufenderElemente α.

Zusammen mit Zeit fur die Auswertung der Hash-Funktion ergibt sichΘ(1 + α). �



Erfolgreiche Suche:

• Die mittlere Laufzeit einer erfolgreichen Suche ist ebenfalls Θ(1 + α).

• Die Umstande unterscheiden sich etwas vom erfolglosen Fall.

• Die Wahrscheinlichkeit, dass eine Liste durchsucht wird ist proportionalzu deren Lange.

Satz 9.2 Der Erwartungswert der Laufzeit einer erfolgreichen Suche be-tragt Θ(1 + α).

Beweis: Angenommen, das gesuchte Element ist mit gleicher Wahrschein-lichkeit eines der n in der Tabelle enthaltenen Elemente.



Die Anzahl bei einer erfolgreichen Suche nach x uberprufter Elementebetragt eins mehr als die Anzahl Vorganger von x in dessen Liste. DieseElemente wurden nach x eingefugt (da am Kopfende eingefugt wird).

Zu bestimmen ist somit die (uber die n Elemente x in der Tabelle) gemittelteAnzahl Elemente, welche nach x in dessen Liste eingefugt wurden.

Sei xi das i-te in die Tabelle eingefugte Element (i = 1, . . . , n) sowieki := key [xi].

Fur alle 1 ≤ i, j ≤ n definieren wir die Indikatorzufallsvariablen

Xi,j := I{h(ki) = h(kj)} =

{1 falls h(ki) = h(kj),

0 sonst.

Einfaches gleichmaßiges Hashen ⇒ Pr{h(ki) = h(kj)} = 1/m, d.h.E[Xi,j ] = 1/m.



Somit betragt die erwartete Anzahl uberprufter Elemente in einer erfolgrei-chen Suche

E

1n

n∑i=1

(1 +

n∑j=i+1

Xi,j

) =1n

n∑i=1

(1 +

n∑j=i+1

E[Xi,j ])

=1n

n∑i=1

(1 +

n∑j=i+1

1m

)= 1 +

1nm

n∑i=1

(n− i)

= 1 +1

nm

( n∑i=1

n−n∑

i=1

i

)= 1 +

1nm

(n2 − n(n + 1)

2

)= 1 +

n

m− n + 1

2m= 1 +

n− 12m

= 1 +α

2− α

2n.

Zusammen mit der Zeit zur Auswertung von h ergibt sich als mittlereGesamtzeit fur eine erfolgreiche Suche Θ(2 + α/2− α/2n) = Θ(1 + α). �



Interpretation: Ist n = O(m), so ist α = n/m = O(m)/m = O(1), d.h.Suchen benotigt im Durchschnitt O(1) Laufzeit.

Da Einfugen und (bei doppelt verketteten Listen) auch Loschen O(1)-Operationen sind, erhalten wir somit fur alle Worterbuch-Operationen imMittel Laufzeit O(1).



9.3 Hash-Funktionen

Gewunschte Eigenschaften:

• Idealerweise Annahme des einfachen, gleichmaßigen Hashens erfullt

• Dies ist in der Praxis deshalb nicht moglich, da die Wahrscheinlich-keitsverteilung der auftretenden Schlussel nicht im Voraus bekannt ist;ferner sind diese moglicherweise nicht unabhangig.

• Oft werden auf der Grundmenge der Schlussel basierende Heuristikeneingesetzt, um effiziente Hash-Funktionen zu konstruieren.

9.3 Hash-Funktionen TU Bergakademie Freiberg, WS 2005/06


Schlussel als naturliche Zahlen

• Hash-Funktionen sind fur naturliche Zahlen definiert.

• Anderswertige Schlussel mussen zuvor nach N abgebildet werden.

• Besipiel: Abbildung von ASCII-Zeichenketten auf naturliche Zahlen ineiner geeigneten Basis. Betrachte die Zeichenkette CLRS.

◦ Die zugehorigen ASCII-Codes lauten C=67, L=76, R=82, S=83.

◦ ASCII-Codes zwischen 0 und 127.

◦ Interpretiere daher die Zeichenkette CLRS als die Zahl (Basis 128)

(67 · 1283) + (76 · 1282) + (82 · 1281) + (83 · 1280) = 141 764 947.



9.3.1 Die Divisionsmethode

Schlussel k wird auf eine von m Positionen abgebildet durch Restbildungbezuglich Division durch m, d.h. h(k) = k mod m.

Beispiel: m = 20, k = 91,⇒ h(k) = 11.

Vorteil: Auswertung schnell, da nur eine Division erforderlich

Beachte: Bestimmte Werte von m sind zu vermeiden.

• Zweierpotenzen ungunstig. Bei m = 2p hangt h(k) nur von den p

niedrigstwertigen Bits von k ab. (Hash-Wert sollte von allen Bitsabhangen, es sei denn alle p-Bitmuster gleich wahrscheinlich.)

• Ist k eine Zeichenkette als Zahl zur Basis 2p dargestellt (s.o.), so istm = 2p − 1 insofern schlecht, als dann der Hash-Wert invariant istunter Permutationen der Zeichen.

Gute Wahl: Primzahl nicht allzu nahe an einer Zweierpotenz.



9.3.2 Die Multiplikationsmethode

Hier wird die Hash-Funktion wie folgt konstruiert:

1. Wahl einer Konstanten A im Intervall (0, 1)

2. Multiplikation des Schlussels k mit A

3. Bestimmung des gebrochenen (nichtganzzahligen) Anteils von kA

4. Multiplikation des gebrochenen Anteils mit m

5. Ergebnis nach unten abrunden

Insgesamt:h(k) = bm(kA mod 1)c. (9.1)

(kA mod 1 = kA− bkAc ist eine Schreibweise fur den gebrochenen Anteilvon kA.)



Nachteil: Auswertung langsamer als bei Divisionsmethode

Vorteil: Wahl von m nicht kritisch

Beispiel fur (relativ) einfache Implementierung:

• Wahle m = 2p fur ein p ∈ N.

• Die Wortlange der Maschine betrage w Bits.

• Annahme: k passt in ein Wort, ist also in ≤ w Bits darstellbar.

• Wahle A von der Form A = s/2w, wobei s ∈ N im Bereich 0 < s <

2w, (d.h. s ebenfalls durch w Bits darstellbar)

• Produkt ks ist dann 2w Bits breit, d.h. ks = r12w + r0, r0, r1 < 2w.

• Es gilt: r1 = bkAc, r0 = (kA− bkAc)2w.

• h(k) = bm(kA mod 1)c besteht aus den p = log2 m hochstwertigenBits von r0.



Beispiel: m = 8, d.h. p = 3; w = 5, k = 21.

Fur s im Bereich 0 < s < 25 wahlen wir s = 13, somit ist A = 13/32.

Berechnung nach Formel (9.1):

kA = 21 · 1332

=27332

= 8 +1732

⇒ kA mod 1 =1732

⇒ m(kA mod 1) = 8 · 1732

=174

= 4 +14

⇒ h(k) = bm(kA mod 1)c = 4.

Berechnung gemaß Implementierung:

ks = 21 · 13 = 273 = 8 · 25 + 17 ⇒ r1 = 8, r0 = 17.

In w-Bit-Darstellung: r0 = 100012, die p = 3 hochstwertigen Bits hiervonsind 1002 = 410, also h(k) = 4.



Wahl von A:

• Die Multiplikationsmethode funktioniert mit jedem zulassigen Wert vonA.

• In Abhangigkeit der zu hashenden Schlussel sind einige Werte effizi-enter als andere.

• Vorschlag von Knuth: A ≈ (√

5− 1)/2.



9.3.3 Universelles Hashen

Gedankenspiel: Einem Damon, dem die Hash-Funktion bekannt sei, ob-liege die Auswahl der zu hashenden Schlussel. Diese konnte er so wahlen,dass alle in dieselbe Position gehasht werden, womit die Worst-Case Kom-plexitat eintritt.

Moglicher Ausweg: In jedem Programmaufruf eine neue Hash-Funktionwahlen. Ist dem Damon die Folge der gewahlten Hash-Funktionen nichtbekannt, so kann er die Schlussel nicht mehr ungunstig wahlen.

Auswahl aus einer endlichen Menge H von Hash-Funktionen h : G →{0, 1, . . . ,m− 1}.

H heißt universell, falls fur jedes Schlusselpaar k, ` ∈ G, k 6= `, gilt:

|{h ∈H : h(k) = h(`)}| ≤ |H |/m.



Interpretation: H ist universell, falls fur jede zufallig ausgewahlte Hash-Funktion h ∈ H die Kollisionswahrscheinlichkeit fur zwei verschiedeneSchlussel hochstens 1/m betragt, also nicht großer ist als in dem Fall,dass die Hash-Werte fur k und ` gleichverteilt zufallig aus {0, 1, . . . ,m− 1}gewahlt werden.

Satz 9.3 Bei universellem Hashen mit Chaining angewandt auf einenSchlussel k gilt:

(a) Ist k nicht in der Tabelle enthalten, so gilt fur die erwartete LangeE[nh(k)] der Liste, in die k gehasht wird, E[nh(k)] ≤ α.

(b) Ist k in der Tabelle enthalten, so gilt fur die erwartete Lange der k

enthaltenden Liste E[nh(k)] ≤ 1 + α.



Korollar 9.4 Bei universellem Hashen mit Kollisionsauflosung durch Chai-ning ist zur Bearbeitung einer beliebigen Folge von n INSERT-, SEARCH-oder DELETE-Operationen, worunter sich insgesamt O(m) INSERT-Operatio-nen befinden, im Mittel Θ(n) Zeit erforderlich. Insbesondere betragt diemittlere Laufzeit der Suchoperation O(1).

Daruberhinaus sind universelle Familien von Hash-Funktionen einfach zukonstruieren; Details in [Cormen, Leiserson, Rivest & Stein].



9.4 Offene Adressierung

Idee:

• Alle Datensatze (hier: Schlussel) in der Hash-Tabelle gespeichert.

• An jeder Position steht entweder ein Schlussel oder NIL.

• Suchen nach Schlussel k:

◦ Prufe, ob k an Position h(k). Prufung heißt Sondierung (probe).

◦ Enthalt Position h(k) Schlussel k, ist die Suche erfolgreich; enthaltPosition h(k) den Wert NIL, ist sie erfolglos.

◦ Dritte Moglichkeit: Position h(k) enthalt anderen Schlussel ` 6= k. Indiesem Fall werden, abhangig von k und der aktuellen Sondierung,solange weitere mogliche Positionen fur k durchlaufen, bis an einerdieser entweder NIL oder der Schlussel k vorgefunden wird.

9.4 Offene Adressierung TU Bergakademie Freiberg, WS 2005/06


• Damit erforderlichenfalls alle Positionen sondiert werden und jede Posi-tion hochstens einmal sondiert wird, muss die Folge der Sondierungeneine Permutation der Zahlen {0, 1, . . . ,m− 1} sein.

• Die Hash-Funktion ist somit eine Abbildung

h : G× {0, 1, . . . ,m− 1}︸︷︷︸Sondierungsindex

→ {0, 1, . . . ,m− 1}︸︷︷︸Position

.

• Die Forderung, dass fur jeden Schlussel die Folge der generiertenPositionen eine Permutation von {0, 1, . . . ,m − 1} ist, bedeutet dieSondierungsfolge {h(k, 0), h(k, 1), . . . , h(k, m−1)} ist eine Permutationvon {0, 1, . . . ,m− 1}.

• Beim Einfugen geht man vor wie beim Suchen und fugt an der erstenNIL-Position der Sondierungsfolge ein.



Pseudocode fur Suchen: liefert Position des gesuchten Schlussels bzw.NIL.

HASH-SEARCH(T, k)

i← 0repeat j ← h(k, i)

if T [j] = k

then return j

i← i + 1until T [j] = NIL or i = m

return NIL

Annahme hierbei: es findet keine Loschung von Elementen statt.



Pseudocode fur Einfugen: liefert Position, an der Schlussel eingefugt wurdebzw. Fehlermeldung

”Hash-Tabellen Uberlauf“, falls keine freie Position

gefunden wurde.

HASH-INSERT(T, k)

i← 0repeat j ← h(k, i)

if T [j] = NIL

then T [j]← k

return j

else i← i + 1until i = m

error”Hash-Tabellen Uberlauf “



Loschen von Elementen: Es genugt nicht, die Position des zu loschendenSchlussels mit NIL zu uberschreiben.

Begrundung:

• Zu loschen sei Schlussel k an Position j.

• Nach Einfugen von k sei ein weiterer Schlussel k′ eingefugt worden,im Verlaufe dessen Einfugens Position j sondiert (und k vorgefunden)wurde.

• Angenommen wir loschen daraufhin Schlussel k durch Eintragen vonNIL an Position j.

• Wurde daraufhin nach Schlussel k′ gesucht, so wurde vor der k′ ent-haltenden Position zuerst Position j sondiert, NIL vorgefunden und dieSuche als erfolglos beendet werden.

• Dies obwohl k′ noch in der Tabelle enthalten ist.



Losung: Verwendung eines Sonderzeichens DELETED neben NIL.

• Beim Suchen werden Positionen mit Symbol DELETED behandelt alsenthielten diese vom gesuchten Schlussel verschiedene Schlussel.

• Beim Einfugen werden solche Positionen als frei erkannt und konnenerneut belegt werden.

Nachteil: Suchzeit hangt nun nicht mehr vom Lastfaktor α ab.



9.4.1 Berechnung von Sondierungsfolgen

Idealfall: Auf jeden Schlussel entfallt mit gleicher Wahrscheinlichkeit ei-ne der m! Permutationen von {0, 1, . . . ,m − 1} als Sondierungsfolge:gleichmaßiges Hashen. Dies stellt insofern eine Verallgemeinerung deseinfachen gleichmaßigen Hashens dar, als die Hash-Funktion jedemSchlussel anstelle einer Zahl eine Zahlenfolge (Permutation) zuordnet.

Echtes gleichmaßiges Hashen ist schwer zu realisieren, daher wird esapproximiert durch Techniken, welche zumindest garantieren, dass jedeSondierungsfolge eine Permutation von {0, 1, . . . ,m− 1} ist.

Keine dieser Techniken vermag alle m! Permutationen zu generieren.



Lineares Sondieren

Zu einer gegebenen Hash-Funktion h′ : G→ {0, 1, . . . ,m−1} (”Grundfunk-

tion“) verwendet lineares Sondieren die Hash-Funktion

h(k, i) = (h′(k) + i) mod m, i = 0, 1, . . . ,m− 1.

Zu gegebenem Schlussel k wird also zuerst T [h′(k)] sondiert gefolgt vonT [h′(k) + 1], . . . , T [m− 1], T [0], T [1], . . . , T [h′(k)− 1].

Die erste Sondierung bestimmt die gesamte Folge, es gibt genau m ver-schiedene Sondierungsfolgen.

Lineares Sondieren ist einfach zu implementieren, leidet aber unter derBildung von primaren Clustern: eine freie Position, welcher i besetztePositionen vorangehen, wird mit Wahrscheinlichkeit (i + 1)/m besetzt.

So neigen lange Folgen besetzter Positionen dazu, noch langer zu werden,womit die Suchzeit sich erhoht.



Quadratisches Sondieren

Beim quadratischen Sondieren lautet zu gegebener Grundfunktion h′ undKonstanten c1 sowie c2 6= 0 die Hash-Funktion

h(k, i) = (h′(k) + c1i + c2i2) mod m, i = 0, 1, . . . ,m− 1.

Wieder wird T [h′(k)] zuerst sondiert; die Inkremente zu den danach son-dierten Positionen hangen quadratisch von i ab.

Quadratisches Sondieren funktioniert deutlich besser als lineares Sondie-ren – es ist jedoch erforderlich, c1, c2 und m geeignet zu wahlen, um dasFeld moglichst gut auszunutzen.

Fur zwei Schlussel k1, k2 mit h(k1, 0) = h(k2, 0) gilt h(k1, i) = h(k2, i) furalle i; diese Eigenschaft fuhrt zur Bildung von sog. Sekundarclustern.

Wieder bestimmt die erste Sondierposition alle weiteren, es gibt also auchhier genau m verschiedene Sondierfolgen.



Doppeltes Hashen

Hier werden zwei Grundfunktionen h1 und h2 verwandt: h1 liefert die ersteSondierung, h2 bestimmt die weiteren:

h(k, i) = (h1(k) + ih2(k)) mod m.

h2(k) muss teilerfremd zu m sein, damit eine Sondierungsfolge voller Langeerreicht wird.

Moglichkeiten:

• m als Zweierpotenz wahlen und h2 > 1 stets ungerade.

• m eine Primzahl und 1 < h2(k) < m.

Verbesserung gegenuber linearer oder quadratischer Sondierung: Θ(m2)verschiedene Sondierungsfolgen (jedes Paar (h1(k), h2(k)) liefert andereFolge) anstelle von Θ(m).



Beispiel:

Einfugen des Schlussels k = 14 in eine Hash-Tabelle mit m = 13 Positionen bei Kollisions-auflosung durch doppeltes Hashen mit Hash-Funktionen

h1(k) = k mod 13

h2(k) = 1 + k mod 11.

Die endgultige Einfugeposition ist bei Position 9 er-reicht, nachdem Positionen 1 und 5 sondiert und alsbelegt erkannt wurden.

5

4

3

1

0

6

12

11

10

9

8

7

2

98

72

50

79

69



Beispiel:


h1(k) = k mod 13

h2(k) = 1 + k mod 11.


5

4

3

1

0

6

12

11

10

9

8

7

2

98

72

50

79

69

79



Beispiel:


h1(k) = k mod 13

h2(k) = 1 + k mod 11.


5

4

3

1

0

6

12

11

10

9

8

7

2

98

72

50

79

69

79

98

79



Beispiel:


h1(k) = k mod 13

h2(k) = 1 + k mod 11.


5

4

3

1

0

6

12

11

10

9

8

7

2

98

72

50

79

69

79

98

79

14

98



9.5 Analyse von offener Adressierung

Annahmen:

• Tabelle nie vollstandig belegt, d.h. Lastfaktor α = n/m < 1.

• Gleichmaßiges Hashen

• Keine Loschoperationen

• Bei erfolgreichen Suchoperationen wird jeder Schlussel mit gleicherWahrscheinlichkeit gesucht.

Satz 9.5 Bei einer Hash-Tabelle mit offener Adressierung und Lastfaktorα = n/m < 1 betragt die erwartete Anzahl Sondierungen bei erfolgloserSuche hochstens 1/(1− α) unter der Annahme gleichmaßigen Hashens.

9.5 Analyse von offener Adressierung TU Bergakademie Freiberg, WS 2005/06


Beweis: Bei erfolgloser Suche untersucht jede Sondierung eine belegtePosition bis auf die letzte, die eine leere Position pruft.

Definiere Zufallsvariable X := # Sondierungen bei einer erfolglosen Suche.

Definiere Ereignisse Ai, i = 1, 2, . . . durch

Ai := { i-te Sondierung wird durchgefuhrt und pruft eine belegte Position}.

Es gilt: X ≥ i falls Sondierungen 1, 2, . . . , i − 1 stattfinden und jeweilsbelegte Positionen prufen. m.a.W. {X ≥ i} = A1 ∩A2 ∩ · · · ∩Ai−1.

Ferner gilt (Ubung)

Pr(A1 ∩A2 ∩ · · · ∩Ai−1) = Pr(A1) · Pr(A2|A1) · Pr(A3|A1 ∩A2) · . . . ·Pr(Ai−1|A1 ∩A2 ∩ · · · ∩Ai−2).



Behauptung: es ist

Pr(Aj |A1 ∩A2 ∩ · · · ∩Aj−1) =

{Pr(A1) = n/m falls j = 1,n−j+1m−j+1 j = 2, . . . ,m− 1.

(9.2)

Im Fall j = 1 sind n aus m Positionen belegt, die erste Sondierung findetdaher mit Wahrscheinlichkeit n/m eine belegte Position vor.

Wurden j−1 Sondierungen, jeweils von belegten Positionen, durchgefuhrt,so pruft die nachste Sondierung eine bisher noch nicht geprufte Position(da jede Sondierungsfolge eine Permutation von 〈0, 1, . . . ,m− 1〉 ist).

Es verbleiben m − j + 1 Positionen von denen n − j − 1 belegt sind, d.h.die j-te Sondierung trifft mit Wahrscheinlichkeit (n− j + 1)/(m− j + 1) aufeine belegte Position, und (9.2) ist gezeigt.



Mit Hilfe von (9.2) erhalten wir

Pr(X ≥ i) =n

m· n− 1m− 1

· n− 2m− 2

· . . . n− i + 2m− i + 2︸︷︷︸

i−1 Faktoren

.

Da n < m folgt (n− j)/(m− j) ≤ n/m fur j ≥ 0, und somit

Pr(X ≥ i) ≤(

n

m

)i−1

= αi−1.

Wir erhalten

E[X] =∞∑

i=0

i · Pr(X = i) =∞∑

i=1

Pr(X ≥ i) ≤∞∑

i=1

αi−1 =∞∑

i=0

αi =1

1− α.

�



Interpretation:

• Eine Sondierung findet immer statt. Erste Sondierung trifft auf belegtePosition mit Wahrscheinlichkeit α. Mit Wahrscheinlichkeit α2 auch diezweite, usw.

• Ist α konstant, so besitzt erfolglose Suche Laufzeit O(1).

α = 0.5: erfolglose Suche erfordert im Mittel 1/(1− 0.5) = 2 Sondierun-gen.

α = 0.9: im Mittel 1/(1− 0.9) = 10 Sondierungen. �

Korollar 9.6 Die erwartete Anzahl Sondierungen beim Einfugen betragthochstens 1/(1− α).

Beweis: Unter der Annahme, dass keine Loschungen stattfinden, benutztdie Einfugeoperation dieselbe Sondierungsfolge wie erfolgloses Suchen.



Satz 9.7 Die erwartete Anzahl Sondierungen bei erfolgreichem Suchenbetragt hochstens 1

α log 11−α .

Beweis: Erfolgreiches Suchen nach Schlussel k geschieht nach derselbenSondierungsfolge wie beim Einfugen von k.

Nach Korollar 9.6: war k der (i + 1)-te eingefugte Schlussel, so hatte α

zu dieser Zeit den Wert i/m. Die erwartete Anzahl Sondierungen fur dieSuche nach k ist somit 1/(1− i/m) = m/(m− i).

Wir Mitteln dies uber alle Schlussel der Tabelle:

1n

n−1∑i=0

m

m− i=

m

n

n−1∑i=0

1m− i

=1α

(Hm −Hm−n),

wobei Hi :=∑i

j=1 1/j die i-te harmonische Zahl bezeichnet.



Wir schatzen ab:

1α

(Hm −Hm−n) =1α

m∑k=m−n+1

1k

≤ 1α

∫ m

m−n

1x

dx

=1α

(log m− log(m− n)

)=

1α

logm

m− n

=1α

log1

1− α.

�


Date post:	31-Aug-2019
Category:	Documents
Upload:	others
View:	6 times
Download:	0 times

9 Hash-Tabellen - TU Bergakademie Freibergernst/Lehre/AD/Folien/adKapitel9.pdf · Algorithmen und...

Documents