Dobbelt hashing

Når metoden med dobbelt spredningsværdi eller dobbelt hashing ( engelsk dobbelt hashing ) er en metode til at realisere en lukket hash-metode . I lukkede hash procedurer, gøres der forsøg på at rumme afhoppere i den hashtabel stedet for at lagre dem i cellen (fx som en liste). (Åbne hash-procedurer kan tildele poster to gange og kræver derfor ikke sondering.) OBS: Som det er i artiklen hash-tabel under "Varianter af hash-proceduren", anvendes udtrykkene "åben" eller "lukket hashing" på nøjagtig den modsatte måde.

For at gøre dette bruger dobbelt hashing en sonderingsfunktion, der inkluderer en sekundær hash-funktion, f.eks. B. , og som bruges, hvis indekset beregnet af den primære hash-funktion allerede er optaget. ${\ displaystyle \; s (j, k): = j \ cdot h '(k)}$${\ displaystyle \; h (k)}$

Den komplette hash-funktion læser derefter :, hvor j er antallet af allerede "prøvede" indekser, dvs. Dette betyder, at j øges med 1, hver gang et indeks allerede bruges. ${\ displaystyle \; h (k) -s (j, k)}$

Sonderingsfunktionen formodes at danne en permutation af indekserne i hash-tabellen. ${\ displaystyle \; s (j, k)}$

Sekvensen af ​​hash-funktioner, der nu er dannet ved hjælp af og ser sådan ud: ${\ displaystyle h}$${\ displaystyle h '}$

${\ displaystyle h_ {j} (k) = (h (k) + h '(k) \ cdot j) ~ {\ bmod {~}} m}$

Omkostningerne ved denne metode er tæt på omkostningerne ved ideel hashing.

Hash-funktionernes uafhængighed

Dobbelt hashing bruger to uafhængige hash-funktioner og . Disse kaldes uafhængige, hvis sandsynligheden for en såkaldt dobbelt kollision, dvs. H. , er mindre end eller lig med og derfor minimal, hvor er arrayets størrelse. ${\ displaystyle h}$${\ displaystyle h '}$${\ displaystyle h (k) = h (y) \ land h '(k) = h' (y)}$${\ displaystyle 1 / m ^ {2}}$${\ displaystyle m}$

Eksempler

Eksempel på funktioner

Matrixens størrelse: m

Indeks: {0; m-1}

Primær hashfunktion: ( metode til deling af resten ) ${\ displaystyle h (k): = k \; {\ bmod {\;}} m}$

Sekundær hash-funktion: ${\ displaystyle \; h '(k): = k \; {\ bmod {\;}} (m-2) +1}$

Forklarende funktion: ${\ displaystyle \; s (j, k): = j \ cdot (k \; {\ bmod {\;}} (m-2) +1)}$

Fuld dobbelt hash-funktion: ${\ displaystyle \; h_ {j} (k): = (k \; {\ bmod {\;}} m + j \ cdot (k \; {\ bmod {\;}} (m-2) +1 )) {\ bmod {m}}}$

Beregningseksempel

Matrixens størrelse: m = 7

Hash-funktioner

${\ displaystyle h (k): = k \; {\ bmod {\;}} 7}$

${\ displaystyle h '(k): = k \; {\ bmod {\;}} 5 + 1}$

Undersøgende funktion

${\ displaystyle h_ {j} (k): = (h (k) + j \ cdot h '(k)) \; {\ bmod {\;}} m}$

Hash-bord:

Arrayet fyldt ved hjælp af hash-tabel og probe-funktion:

Forklaring ved hjælp af eksemplet : ${\ displaystyle k = 31}$

${\ displaystyle k = 10}$og genererer ikke en kollision og har derfor ikke brug for dobbelt hash-funktionen . Indekset for hash-funktionen kan aflæses her. skaber en kollision i arrayet på det punkt , hvorfor du nu bruger dobbelt hash-funktionen med : ${\ displaystyle k = 19}$${\ displaystyle h_ {j}}$${\ displaystyle h}$${\ displaystyle k = 31}$${\ displaystyle 3}$${\ displaystyle h_ {j}}$${\ displaystyle j = 1}$

${\ displaystyle h_ {1} (31) = (h (31) +1 \ cdot h '(31)) \; {\ bmod {\;}} 7 \ ​​equiv (3 + 1 \ cdot 2) \; { \ bmod {\;}} 7 \ ​​equiv 5 \; {\ bmod {\;}} 7 \ ​​equiv 5}$

Pointen skaber en kollision igen, hvorfor følgende nu kaldes: ${\ displaystyle 5}$${\ displaystyle h_ {j}}$${\ displaystyle j = 2}$

${\ displaystyle h_ {2} (31) = (h (31) +2 \ cdot h '(31)) \; {\ bmod {\;}} 7 \ ​​equiv (3 + 2 \ cdot 2) \; { \ bmod {\;}} 7 \ ​​equiv 7 \; {\ bmod {\;}} 7 \ ​​equiv 0}$

Stillingen er ledig og modtager således indholdet . ${\ displaystyle 0}$${\ displaystyle 31}$

Weblinks

• Lukket hashing
• Åben hashing