Transcript
Kapitel 4 Streuen Wir behandeln nun Implementationen ungeordneter Wörterbücher, in denen die Schlüssel ohne Beachtung ihrer Sortierreihenfolge gespeichert werden dürfen, verlangen aber, dass es sich bei den Schlüsseln um Zahlen handelt. Dies ist keine starke Voraussetzung, weil sich die Elemente anderer Schlüsseluniversen als Zahlen codieren lassen.
typisch in JAVA: Speicheradresse
Bezeichnungen: (Schlüssel-) Universum Schlüsselmenge Hashtabelle
Object.hashCode
U ⊆ N0 K ⊆ U, |K| = n H[0, . . . , m − 1] (Array von Zeigern auf Datenelemente)
h : U → {0, . . . , m − 1} wird jedem zulässigen hash (engl.): streuen Schlüssel k ∈ U seine Speicherstelle H[h(k)] in der Hashtabelle H zugewiesen. Durch eine Hashfunktion
Im Idealfall gilt für die Menge
K⊆U
der vorkommenden Schlüssel
k1 6= k2 ∈ K =⇒ h(k1 ) 6= h(k2 )
(h|K injektiv)
weil Einfügen, Suchen und Löschen dann jeweils in können.
4.1 Beispiel (Hashfunktionen)
1. h(k) = k mod m für Primzahl m (Divisions- oder Kongruenzmethode) 60
Θ(1)
realisiert werden
Algorithmen und Datenstrukturen (WS 2008/09)
61
√
≈ 0, 61803 2. h(k) = bm · (kα − bkαc)c z.B. für α = φ−1 = 5−1 2 (Multiplikationsmethode) Die n+1 Intervalle nach Einfügen von 1, . . . , n haben nur 3 verschiedene Gröÿen; bei α = φ−1 am ähnlichsten.
4.1
Kollisionen
4.1
h(k1 ) = h(k2 ) für einige h1 , h2 ∈ K . Kollisionen, k1 , k2 heiÿen Synonyme.
Im Allgemeinen ist allerdings bezeichnen wir mit
Dies
pm,n := P (keine Kollisionen) = 1· m−1 · m−2 · . . . · m−n+1 , falls Schlüssel durch m m m h gleichmäÿig gestreut werden, d.h. alle Positionen gleichwahrscheinlich sind.
4.2 Beispiel (Geburtstagsparadoxon)
p365,22 > 0.5 > p365,23
Anschauliche Deutung: bei 23 oder mehr Personen ist die Wahrscheinlichkeit, dass zwei am gleichen Tag Geburtstag haben, gröÿer als die Wahrscheinlichkeit, dass alle an verschiedenen Tagen Geburtstag haben. Herleitung: pm,n =
Qn−1 i=0
m−i m
Qn−1 = (1 − mi ) Qi=1 n 1 Pn−1 n−1 −i/m ≈ = e− m i=1 i = e−( 2 )/m i=1 e
Für welches n ist pm,n ≈ 1/2? n e−( 2)/m = 12 ⇔ − n2 /m = ln 21 n ⇔ = m ln 2 2 q
n(n−1) 2
⇒
n
≈
p
2(ln 2) · m (≈ 22.49 für m = 365)
goldener Schnitt
Algorithmen und Datenstrukturen (WS 2008/09) Erwartete Anzahl Kollisionen
Xij =
1 0
falls
Sei
h(ki ) = h(kj ) (Kollision E(Xij ) = 1/m
für
! X
Xij
=
i 1. Positionen in der Hashtabelle zu füllen. Dann ist β = m
4.2.2
Idee
Open Hashing
In jedem Feld der Hashtabelle (daher
H
wird nur ein Element gespeichert
β ≤ 1). Füge Schlüssel
Füge Schlüssel
Wähle eine Folge
k2
Für die Folge
k1
(di )i=1,2,... , di ∈ Z
(di )i
h(k1 ) = i, H[i] = k1 . h(k2 ) = i, H[i] besetzt. y freien Platz in H .
ein:
ein (Kollision):
H[(h(k) + di )
lineares Sondieren: double Hashing:
und teste
mod m],
i = 1, 2, 3, . . .
di = i di = i2 di = i · h0 (k), sollte
m
h0 : U → {1, . . . , m − 1} 0 ist mit h (k) 6= 0 ∀k ∈ U .
wobei
zweite Hashfunktion
prim sein! Warum?
Einfügen und Suchen ist damit klar, Löschen ist aber ein Problem.
4.7 Beispiel
Sei h(k) = h(k0 ) = i und füge k, k 0 ein: H:
k
k0
i i+1 k. y
Anschlieÿend versagt die Suche nach
Lösung: markiere gelöschte Schlüssel als gelöscht
eine Hier Index h0 ?
4.6 Problem
Lösche dann
Finde
gibt es verschiedene Wahlen:
quadratisches Sondieren:
•
m
k0!
bei
Algorithmen und Datenstrukturen (WS 2008/09)
66
•
bei Suche werden sie behandelt wie belegte Felder
•
beim Einfügen wie freie Felder
•
ungünstig, wenn oft Elemente gelöscht werden, da die Suche verteuert.
4.8 Problem
Clusterbildung
4.9 Beispiel (lineares Sondieren)
H:
···
··· i i+1
Nächster einzufügender Schlüssel:
P (h(k) = i + 1) = P (h(k) = i) =
1 m 5 m
k∈U
⇒
Cluster wachsen tendentiell
Analyse lineares Sondieren
double Hashing
1 A ≈ 12 (1 + 1−β ) 1 1 0 A ≈ 2 (1 + (1−β)2 )
1 A ≈ β1 ln( 1−β ) 1 0 A ≈ 1−β
Beweis.
lineares Sondieren: schwer, s. Schöning S.140-141.
double Hashing: (idealisierende) Annahme: Sondierungen erfolglosen Suche von
k
Referenz
h1 (k), h2 (k), . . . zur
mit
n =1−β P (H[hi (k)] ist frei) = 1 − m E[Anzahl Sondierungen bis freies Feld
gefunden]
=
1 1−β
Algorithmen und Datenstrukturen (WS 2008/09) Also
A0 (n, m) =
67
1 . 1−β
A(n, m) = = ≈ =
Pn−1 0 Pn−1 1 Pn−1 1 1 m 1 i=0 A (m, i) = n i=0 1− i = n i=0 m−i n m 1 1 1 1 ( + · · · + m ) = β (Hm − Hm−n ) β m−n+1 m 1 (ln m − ln(m − n)) = β1 ln m−n β 1 1 ln 1−β β
4.3
Kollisionsvermeidung
4.3.1
Ziel
Streufunktionen
gleichmäÿige Streuung durch Hashfunktion, wie in der Berechnung der Kollisionswahrscheinlichkeiten unterstellt.
Problem
→
K ⊆ U h(k1 ) = H(k2 ) ∀k1 , k2 ∈ K
Wir wissen nicht, welche Schlüssel
Schlimmstenfalls ist
Sondieren bei Suche entspricht linearer Suche
Schlüsselmengen
K ⊆U
gespeichert werden.
O(n).
führen zu sehr verschiedenen Laufzeiten. Versuche
daher, die Wahrscheinlichkeit für schlechtes Laufzeitverhalten besser auf diese zu verteilen.
Idee
Wähle aus einer Menge von Hashfunktionen
H ⊆ {h : U → {0, . . . , m − 1}} zufällig eine aus.
4.3.2
Universelles Streuen
4.10 Def inition (universelles Streuen)
Eine Familie von Streufunktionen H ⊆ {h : U → {0, . . . , m − 1}} heiÿt universell, falls
|H| |{h ∈ H : h(k1 ) = h(k2 )}| ≤ m
∀k1 , k2 ∈ U.
Algorithmen und Datenstrukturen (WS 2008/09) Bei zufälliger Wahl
h∈H
sind wir dann berechtigt,
68
P (h(k1 ) = h(k2 )) =
1 m
anzunehmen.
4.11 Satz
Ist H universell, dann ist für k ∈ {k1 , . . . , kn } = K ⊆ U bei zufällig gewähltem h ∈ H die erwartete Anzahl Kollisionen gerade mn = β . Beweis.
Sei
Cij
eine Zufallsvariable mit
Cij = Da
H
1 0
h(ki ) = h(kj ) sonst
P (Cij = 1) = m1 , und es folgt für k = ki X X |K| = β. Cij = E(Cij ) ≤ m
universell ist, ist
E
kj ∈K\{ki }
kj ∈K\{ki }
Die erwartete Anzahl Kollisionen entspricht dann also wie erhot dem Belegungsfaktor
β.
4.12 Satz
Die Familie von Streufunktionen Hp = {(ak + b
mod p)
mod m :
0 < a < p, 0 ≤ b < p} , p prim, p > m
ist universell. Beweis.
Sei
ha,b ∈ Hp
Betrachte zunächst für
mit
ha,b (k) = (ak + b mod p) mod m.
0
k, k ∈ {0, . . . , p − 1} r = (ak + b) mod p s = (ak 0 + b) mod p
Dann ist
r − s ≡ |{z} a (k − k 0 ) mod p,
also
r 6= s
falls
k 6= k 0 ,
p
prim ist.
{0, . . . , p − 1},
sondern
weil
6=0
Es gibt also zunächst keine Kollisionen der Zahlen diese werden nur permutiert.
Algorithmen und Datenstrukturen (WS 2008/09) Auÿerdem liefert jede der denn gegeben
r 6= s
69
(p − 1) · p Wahlen für (a, b) ein anderes Paar r 6= s,
können wir nach
a = (r − s) · (k − k 0 )−1 | {z } Inverses bzgl.
b = (r − ak)
mod p
Zp
mod p
p(p − 1) Paare (r, s) mit r 6= s gibt, liegt a, b zufällig gewählt, dann erhalten wir also auch r= 6 s ∈ {0, . . . , p − 1} mit gleicher Wahrscheinlichkeit.
au ösen. Weil es aber auch nur eine Bijektion vor. Werden jedes Paar
k 6= k 0 ∈ U
Die Kollisionswahrscheinlichkeit von
entspricht damit der Wahr-
r ≡ s mod m für zufällig gewählte r 6= s ∈ {0, . . . , p − 1}. die Anzahl der s mit r 6= s und r ≡ s mod m höchstens
scheinlichkeit, dass Für festes
r
ist
lpm m
−1 ≤
p+m−1 p−1 −1 = m m
und wegen der zufälligen Wahl aus den p − 1 möglichen s 6= r ist die Kollisik 6= k 0 ∈ U höchstens m1 . Also ist Hp universell.
onswahrscheinlichkeit für
Wir wollen nun noch eine andere universelle Familie von Streufunktionen betrachten.
Annahme U Zerlege
K⊆U
besteht aus Bitstrings fester Länge in Blöcke der Länge
m, m
ist prim.
blog mc
···
k: kr
k1
y 0 ≤ ki < m,
k0
Wir de nieren die Menge von Hashfunktionen durch
ha (k) =
r X
i = 0, . . . , r
HB = {ha : U → {0, . . . , m − 1}}
! ai ki
mod m
i=0 wobei
a = (ar , . . . , a0 ) ∈ {0, . . . , m − 1}r+1 .
Damit gilt
|HB | = mr+1 .
Algorithmen und Datenstrukturen (WS 2008/09)
70
4.13 Satz
HB ist universell. Beweis.
i = 0.
k 6= k 0 ∈ U , dann ki 6= ki0 ha ∈ HB gilt dann
Seien
Für ein
0
ha (k) = ha (k ) ⇔
r X
ai ki ≡
i=0
r X
für ein
ai ki0
i ∈ {0, . . . , r}.
OBdA. sei
mod m
i=0
⇔ a0 (k0 − k00 ) ≡
r X
ai (ki0 − ki )
mod m
i=1
⇔ a0 ≡
k00 )−1
(k0 − | {z
mult. Inv. in
}
(Zm ,+,·)
r X
ai (ki0 − ki )
y Für alle Wahlen von (ar , . . . , a1 ) ∈ {0, . . . , m − 1}r a0 ∈ {0, . . . , m − 1} mit ha (k) = ha (k 0 ). Also gilt P (Kollision k 6= k 0 ) =
mod m
i=1
existiert genau ein
| {a : ha (k) = ha (k 0 )} | 1 mr = r+1 = . |HB | m m
4.4
Ausblick
•
viele andere Techniken zur Kollisionsbehandlung, z.B. Cuckoo-Hashing.
•
viele andere Techniken zur Konstruktion von Hashfunktionen, z.B. perfektes Hashing (für statische Schlüsselmengen).
•
viele andere Anwendungen, z.B. Bloom-Filter. .
s. Übung
