Algoritmer og Datastrukturer 1 Hashing [CLRS, kapitel 11.1-11.4]Gerth Stølting Brodal Aarhus Universitet
Algoritmer og Datastrukturer 1 Hashing [CLRS, kapitel 11.1-11.4]
Gerth Stølting Brodal Aarhus Universitet
Ordbogen.com hash (Engelsk-Dansk)
1. (sb) (ret med kød og kartofler) biksemad (fx a meat and potato hash); (fig.) kludder; noget værre rod; ¤ make a ~ of forkludre; udføre på en elendig (el. kikset) måde; settle somebody’s ~ ordne nogen; få nogen ned med nakken;
2. (sb) (narko) hash (fx smoke hash);
3. (vb) hakke; skære i stykker; (fig.) forkludre; slippe (rigtigt) dårligt fra; ¤ ~ over diskutere; drøfte (fx we can hash it over later); ~ up forkludre; slippe dårligt fra.
Før vi starter – lad os lige slå fast hvad ordet ”hash” betyder
Abstrakt Datastruktur: Ordbog
Delete(S,x) Insert(S,x) Search(S,x) Kan vi udnytte at x for alle praktiske formål er en sekvens af bits? JA !
Alle nøgler er tal...
”Sko” = 01010011.01101011.011011112 = 546699110
I det følgende antages at alle er nøgler er tal – det er dog ingen begrænsning da alle strenge, bitvectorer etc kan opfattes som et tal.
Direkte Adressering : Nøgler {0,1,2,...,m-1}
+ Godt ved små nøgle universer
+ Selv kan generere nøglerne som 1,2,3,...
– Stort plads overforbrug når kun få nøgler brugt
Hash Funktion
+ Nemt at jævne nøglerne jævnt ud
– Flere nøgler kan hashes til samme værdi
– Næsten ens nøgler kan være vilkårligt spredt 5 25964 5 24123 6 12002 1 12001 0 3409 2 1231 6 746 5 519 4 257 0 7 h(x) x h(x)=5·x mod 7 Nøgler U
Hash funktion
h : U → {0,1,...,m-1}
(m<<|U| og m|U| mulige valg af h)
h vælges så den er nem at beregne uden at skulle gemme en tabel over alle funktionsværdier
Spørgsmål: Hvor mange funktioner kan beskrives 6 bogstaver? (Den valgte hash funktion er valgt bevidst til at være kort at beskrive – dem er der ikke mange af - men
vi forsøger alligevel at finde en funktion der ”spreder godt”)
Hash Tabel : Kollisionslister
5 25964 5 24123 6 12002 1 12001 0 3409 2 1231 6 746 5 519 4 257 0 7 h(x) x h(x)=5·x mod 7 Gem mængde af nøgler K
Vælg tilfældig hash funktion h : U → {0,1,...,m-1}
Gem nøglerne i tabel efter hash værdi
Kollisionslister til nøgler med sammehash værdi
Hash Tabel : Kollisionslister
Vælg en uniform tilfældig hash funktion:
Forventet antal nøgler i en indgang i tabellen |K|/m
Insert, Delete, Search forventet tid O(|K|/m),
dvs. tid O(1) hvis m=Ω(|K|) m
Hvad er en god Hash Funktion?
– For enhver funktion findes en dårlig mængde nøgler der hasher til samme værdi
+ For enhver mængde nøgler findes en god hash funktion der jævner godt ud (om den kan beskrives kompakt er et andet spørgsmål)
Mål Find en lille mængde af hash funktioner hvor en tilfældig funktion virker rimmelig godt på en given mængde
Hash Funktioner : Eksempler
h(x) = x mod m (typisk m et primtal) m=28-1 ignorerer alle ombytninger af tegn:
h(”c3c2c1”) = h(”c1c3c2”) h(x) =└s·x/2w-k┘mod 2k (x = w-bit, h(x)=k-bit) h(0101000010101010) = 01000
0101000010101010 · 1001111000110111
= 00110001110110100100000010000110 m=28 ignorerer alt på nær de 8 sidste bit:
h(...x3x2x110101111)=h(...y3y2y110101111)
Fornuftig valg af m er et primtal forskelligt fra 2p-1, helst langt fra en 2er potens.
Knuth foreslår at bruge s=2^w*(sqrt(5)-1)/2
Ingen af eksemplerne giver nogen guarantier.
Universelle Hash Funktioner
Find primtal p ≥ |U|.
Definer p·(p-1) hash funktioner ha,b, hvor 1≤a
ha(x) = xs/w-1·as/w-1+xs/w-2·as/w-2+···+x1·a1+x0 mod p (a·b) mod p=((a mod p)·b) mod p
(a+b) mod p=((a mod p)+b) mod p x = (bs-1bs-2...b2b1b0)2
= xs/w-1·2w(s/w-1) + xs/w-2·2w(s/w-2) + ··· + x1·2w + x0 ys/w-1 := xs/w-1 mod p
yi := (yi+1·a+xi) mod p (for i = s/w-2...0)
ha(x) = y0
Hash funktionen er taget fra CLRS, Exercise 11.3-6. p et primtal>2^w.
Åben Adressering
Bruger kun et array
Åben Adressering : Analyse Uniform hashing
h(k,1), h(k,2), h(k,3),... er en uniform tilfældig rækkefølge
(urealistisk)
Sætning
Ved uniform hashing er det forvente antal lookups 1/(1-α)
hvor α=|K|/m er belastningsfaktoren
Liniær Probing
6 20 4 19 7 12 5 11 1 9 12 6 10 5 6 3 4 2 h(x) x h’(x)=2·x mod 17 Eksempel :
Indsæt 9, 3, 20, 6, 12, 2, 19, 11, 5 Indsæt x på første ledige plads
h(k,i) = h’(x)+i mod m
for i = 0,1,2...
Deletions – er en opgave i CLRS
Kvadratisk Probing
Indsæt x på første ledige plads
h(k,i) = h’(x)+c1·i+c2·i2 mod m
for i = 0,1,2, ... hvor c1 og c2≠0 er konstanter Dobbelt Hashing Indsæt x på første ledige plads
h(k,i) = h1(x)+i·h2(x) mod m
for i = 0,1,2, ... hvor h1 og h2 er hash funktioner h’(x) h1(x) c1=0
c2=1 h2(x)=3
Dobbelt hashing bedre til at fordele jævnt ud end liniær og kvadratisk probing da den bruger flere probe sekvenser end linieær og kvadratisk probing der hver kun bruger 1 probe sekvens
Kapitel 11.4 giver også en analyse af uniform hashing hvor hver probe sekvens er en tilfældig permutation (urealistisk) – og viser så en forventet søgetid på 1/(1- |K|/m)
Comments